Card Factory (Large)
Time limit3sMemory limit256 MB
Each of N cards shows its front initially; given M queries K that flip every card whose visible number is at most K, report the final visible sum.
- Level
Hard8 of 10
- Topics
- Sorting, Binary search, Segment tree, Implementation
- Solved
- No attempts yet
Problem
Jinseo works at the CTP card factory. The factory has N cards, and each card has a number written on its front and back. Following the orders of the factory manager Nojin, Jinseo must flip cards. The orders come M times, and each order is as follows.
"When the factory manager Nojin says a number K, Jinseo must flip every one of the N cards whose visible side is at most K."
When the manager's orders are finished, Jinseo must report to the manager the sum of the numbers on the visible sides of the cards.
An example is shown in the following figure.
All cards are set to show their front side at the start, and the numbers written on the cards are positive integers at most 1 billion.
Input
The first line gives N and M. (N and M are positive integers at most 200,000)
The next N lines give the front number Ai and the back number Bi of each card. (Ai and Bi are positive integers at most 1 billion)
The next M lines give the number K that the manager says. (K is a positive integer at most 1 billion)
Output
Print the sum of the cards' visible sides when the orders are finished.