Cerinta completa

There are points on a plane. Each point is described by , where . There are three types of queries needed: 

  1. X i j Reflect all points in the inclusive range between points and along the -axis.
  2. Y i j Reflect all points in the inclusive range between points and  along the -axis.
  3. C i j Count the number of points in the inclusive range between points and in each of the quadrants. Then print a single line of four space-separated integers describing the respective numbers of points in the first, second, third, and fourth quadrants in that order.

As a reminder, the four quadrants of a graph are labeled as follows:

Given a set of points and queries, perform each query in order. For example, given points and . Initially the points are in quadrants and . The first query says to reflect points with indices from to along the -axis. After the query, and quadrants are and . The next query prints the number of points in each quadrant: 0 1 0 1. The third query says to reflect the point with index to along the -axis, so now . The points now lie in quadrants and , so the fourth query output is 0 1 1 0.

Note: Points may sometimes share the same coordinates.

Function Description

Complete the quadrants function in the editor below. It should print the results of each C type query on a new line.

quadrants has the following parameters:
– p[p[1]…p[n]]: a 2-dimensional array of integers where each element contains two integers and
– queries[queries[1]…queries[n]: an array of strings

Input Format

The first line contains a single integer, , that denotes the number of points.
Each line of the subsequent lines contains two space-separated integers that describe the respective and values for point .
The next line contains a single integer, , that denotes the number of queries.
Each of the subsequent lines contains three space-separated values that describe a query in one of the three forms defined above.

Constraints

  • No point lies on the or axes.
  • In all queries, .

Output Format

For each query of type C i j, print four space-separated integers that describe the number of points having indices in the inclusive range between and in the first, second, third, and fourth graph quadrants in that order.

Sample Input

4
1 1
-1 1
-1 -1
1 -1
5
C 1 4
X 2 4
C 3 4
Y 1 2
C 1 3

Sample Output

1 1 1 1
1 1 0 0
0 2 0 1

Explanation

Initially, so there is one point in each of the four quadrants. The first query results in printing 1 1 1 1.

The second query, X 2 4, reflects the points in the inclusive range between indices and along the -axis. Now .

The query C 3 4 requires that the number of points considering through be printed: 1 1 0 0

The third query, Y 1 2 requires reflection of along the -axis. Now .

The last query, C 1 3 requires that the number of points considering through be printed: 0 2 0 1

Limbajul de programare folosit: cpp14

Cod:

#include <bits/stdc++.h>
using namespace std;

int N, Q;
int X[100010];
int Y[100010];
int L, R;
char type;

struct Node 
{
    int count[4] = {0};

    int x_flip = 0;
    int y_flip = 0;

    Node() {}
    Node(int a, int b, int c, int d) 
    {
        count[0] = a;
        count[1] = b;
        count[2] = c;
        count[3] = d;
    }    

    void FlipX()
    {
        swap(count[0], count[3]);
        swap(count[1], count[2]);
    }

    void FlipY()
    {
        swap(count[0], count[1]);
        swap(count[2], count[3]);
    }
};

Node tree[1000010];

Node GetNode(int x, int y)
{
    Node res;

    if(y > 0)
    {
        res.count[(x < 0)]++;
    }
    else 
    {
        res.count[2 + (x > 0)]++;
    }
    return res;
}

Node Combine(Node a, Node b)
{
    Node res;
    
    for(int i = 0; i < 4; i++)
    {
        res.count[i] = a.count[i] + b.count[i];
    }
    return res;
}

Node Reflect(Node node)
{
    Node res;

    vector<pair<int, int>> indices = 
        (type == 'X') ? vector<pair<int, int>>({{0, 3}, {1, 2}, {2, 1}, {3, 0}})
                      : vector<pair<int, int>>({{0, 1}, {1, 0}, {2, 3}, {3, 2}});


    for(auto it : indices)
    {
        res.count[it.first] = node.count[it.second];
    }
    return res;
}

void Reflect(int node, int low, int high, int L, int R)
{
    if(low > high || high < L || low > R)
    {
        return;
    }
    // if(low == high)
    if(low >= L && high <= R)
    {
        // tree[node] = Reflect(tree[node]);

        tree[node].x_flip ^= (type == 'X');
        tree[node].y_flip ^= (type == 'Y'); 

        if(type == 'X') tree[node].FlipX();
        if(type == 'Y') tree[node].FlipY();
        
        return;
    }
    int mid = (low + high) / 2;
    
    Reflect(node * 2 + 1, low, mid, L, R);
    Reflect(node * 2 + 2, mid + 1, high, L, R);    

    int x_flip = tree[node].x_flip;
    int y_flip = tree[node].y_flip;

    tree[node] = Combine(tree[node * 2 + 1], tree[node * 2 + 2]);
    tree[node].x_flip = x_flip;
    tree[node].y_flip = y_flip;
    // if(type == 'X') tree[node].FlipX();
    // if(type == 'Y') tree[node].FlipY();

    if(tree[node].x_flip) tree[node].FlipX();
    if(tree[node].y_flip) tree[node].FlipY();
}

void Build(int node, int low, int high)
{
    if(low == high)
    {
        tree[node] = GetNode(X[low], Y[low]);

        return;
    }
    int mid = (low + high) / 2;

    Build(node * 2 + 1, low, mid);
    Build(node * 2 + 2, mid + 1, high);

    tree[node] = Combine(tree[node * 2 + 1], tree[node * 2 + 2]);
}

Node Count(int node, int low, int high, int L, int R, int flip_x = 0, int flip_y = 0)
{
    if(low > high || high < L || low > R)
    {
        return Node(0,0,0,0);
    }        

    if(low >= L && high <= R)
    {
        auto res = tree[node];

        if(flip_x) res.FlipX();
        if(flip_y) res.FlipY();
        
        return res;
    }

    int mid = (low + high) / 2;

    // if(R <= mid)
    // {
    //     return Count(node * 2 + 1, low, mid, L, R);
    // }
    // else if(L > mid)
    // {
    //     return Count(node * 2 + 2, mid + 1, high, L, R);
    // }

    // Node a = Count(node * 2 + 1, low, mid, L, min(R, mid));
    // Node b = Count(node * 2 + 2, mid + 1, high, max(mid + 1, L), R);

    flip_x ^= tree[node].x_flip;
    flip_y ^= tree[node].y_flip;

    Node a = Count(node * 2 + 1, low, mid, L, R, flip_x, flip_y);
    Node b = Count(node * 2 + 2, mid + 1, high, L, R, flip_x, flip_y);

    return Combine(a, b);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;

    for(int i = 0; i < N; i++)
    {
        cin >> X[i] >> Y[i];
    }
    Build(0, 0, N - 1);

    cin >> Q;

    for(int i = 0; i < Q; i++)
    {                
        cin >> type >> L >> R;
        
        L--; R--;

        switch(type)
        {
            case 'X':
            {
                Reflect(0, 0, N - 1, L, R);
                break;
            }
            case 'Y':
            {
                Reflect(0, 0, N - 1, L, R);
                break;
            }
            case 'C':
            {
                Node ans = Count(0, 0, N - 1, L, R);

                for(int i = 0; i < 4; i++)
                {
                    cout << ans.count[i] << " ";
                }
                cout << "\n";

                break;
            }
        }
    }
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464650120

Link challenge: https://www.hackerrank.com/challenges/quadrant-queries/problem

Quadrant Queries