Bayan's blog

By Bayan, 9 years ago, translation, In English

Problem:
Given N cards, on both sides of each card is written one number. If you put a card on the table face up, you can not see the number written on the other side.
    There are N cards on the table, let Ai be the number written on one side of the card i, a Bi be the number written on the other side of the map i. Cards are initially in a position that can be seen the number Ai.
Given K operations, for each j operation from 1 to K do the following: all cards with visible number less or equal to Tj are upended.
The result is the sum of the numbers that are visible on the cards after this operations.
1<=N,K<=200 000
1<=Ai,Bi,Tj<=1 000 000 000

Sample test:

    Input:     
 5 3 // N and K      
 4 6 // each N lines contains the numbers on the sides of the cards, Ai and Bi      
 9 1       
 8 8      
 4 2       
 3 7      
 8   // each K lines contain Tj        
 2          
 9     
    Output:
 18     
  • Vote: I like it
  • +14
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you give the link to the question?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, haven't link. Can give only photo, but it on the russian language.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When we were on a training camp for Bulgarian's junior and senior national teams one morning while we were having breakfast I heard Hristo Venev talking about this problem and he said that he has solved it for full score using BIT(indexes are T-s). I'm not sure about the constraints but the statement was the same. It was a couple of months ago and I still can't solve it and I really want to know the solution. I hope that this post will help someone to solve the problem.

»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

The problem is exactly the same as "Fortune Telling 2" from JOI Open Contest 2014. There is a comment which described the solution.