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
Can you give the link to the question?
Sorry, haven't link. Can give only photo, but it on the russian language.
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.
The problem is exactly the same as "Fortune Telling 2" from JOI Open Contest 2014. There is a comment which described the solution.