All submissions for this problem are available.
The storyteller is now tired of making up all the b***s**t stories in order to make you solve some questions. So taking inspiration from the lazy head clown, he has decided to take lite.Here is the question.No story. No fuss. Solve this and be done with the competition.
A pair of two vectors (A,B) on the X-Y plane is called an anticlockwise pair if B is on the anticlockwise side of A. If A and B have the same or opposite direction, even then (A,B) is anticlockwise.
A sequence of vectors is an anticlockwise sequence if every consecutive pair of vectors is an anticlockwise pair. More formally, [A0, A1, ..., An] is an anticlockwise sequence if (Ai , Ai+1) is an anticlockwise pair for all 1 ≤ i < n.
You are given an array A of vectors on the X-Y plane. You will be asked Q queries. There are 2 types of queries - the read query and the write query.
Each read query will consist of 2 integers L and R. Let AL,R be the subarray of A from the Lth vector (1-based indexing) to the Rth vector (both inclusive). For each query, you have to tell the number of anticlockwise subarrays of AL,R.
Each write query consists of 2 integers L and R and a vector (X, Y). You are supposed to set all elements of the array from index L to index R equal to (X, Y).
The first line contains an integer N, the number of elements in A.
The next N lines contain two integers per line, the X and Y components of vectors in A.
The next line contains an integer Q, the number of queries.
The next Q lines contain a query each. Each query starts with the character 'R' or 'W'. 'R' means that the query is a read query and 'W' means it is a write query.
After 'R' there are 2 integers on the line, L and R. It is a read query with parameters L and R.
After 'W' there are 4 integers on the line, L, R, X and Y. It is a write query with indexes L and R and vector (X, Y).
For each read query, output the number of anticlockwise subarrays of AL,R.
1 ≤ N ≤ 100000
-100000 ≤ X, Y ≤ 100000
(X,Y) ≠ (0,0)
1 ≤ Q ≤ 100000
1 ≤ L ≤ R ≤ N
8 0 -1 1 -1 1 0 1 1 0 1 1 0 1 -2 1 0 5 R 1 8 R 5 7 R 3 6 W 4 4 1 -1 R 3 6
11 0 3 1
Query 1: There are 5 subarrays of length 2, 3 subarrays of length 3, 2 subarrays of length 4 and 1 subarray of length 5.
Query 2: There are no anticlockwise subarrays.
Query 3: There are 2 subarrays of length 2 and 1 subarray of length 3.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, RUBY, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.