Crash It

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK113/hindi/CRSHIT.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK113/mandarin/CRSHIT.pdf), [Russian](http://www.codechef.com/download/translated/COOK113/russian/CRSHIT.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK113/vietnamese/CRSHIT.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK113/bengali/CRSHIT.pdf) as well. Roger recently built a circular race track with length $K$. After hosting a few races, he realised that people do not come there to see the race itself, they come to see racers crash into each other (what's wrong with our generation...). After this realisation, Roger decided to hold a different kind of "races": he hired $N$ racers (numbered $1$ through $N$) whose task is to crash into each other. At the beginning, for each valid $i$, the $i$th racer is $X_i$ metres away from the starting point of the track (measured in the clockwise direction) and driving in the direction $D_i$ (clockwise or counterclockwise). All racers move with the constant speed $1$ metre per second. The lengths of cars are negligible, but the track is only wide enough for one car, so whenever two cars have the same position along the track, they crash into each other and the direction of movement of each of these cars changes (from clockwise to counterclockwise and vice versa). The cars do not change the directions of their movement otherwise. Since crashes reduce the lifetime of the racing cars, Roger sometimes wonders how many crashes happen. You should answer $Q$ queries. In each query, you are given an integer $T$ and you should find the number of crashes that happen until $T$ seconds have passed (inclusive). ### Input  The first line of the input contains three spaceseparated integers $N$, $Q$ and $K$.  $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$th of these lines contains two spaceseparated integers $D_i$ and $X_i$, where $D_i = 1$ and $D_i = 2$ denote the clockwise and counterclockwise directions respectively.  Each of the next $Q$ lines contain a single integer $T$ describing a query. ### Output For each query, print a single line containing one integer — the number of crashes. ### Constraints  $1 \le N \le 10^5$  $1 \le Q \le 1,000$  $1 \le K \le 10^{12}$  $1 \le D_i \le 2$ for each valid $i$  $0 \le X_i \le K  1$ for each valid $i$  $X_1, X_2, \ldots, X_N$ are pairwise distinct  $0 \le T \le 10^{12}$ ### Example Input ``` 5 3 11 1 3 1 10 2 4 2 7 2 0 3 8 100 ``` ### Example Output ``` 4 10 110 ```Author:  kmaaszraa 
Editorial  https://discuss.codechef.com/problems/CRSHIT 
Tags  cook113, easymedium, kmaaszraa, kmaaszraa, sorting, twopointers 
Date Added:  17122019 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 