Cod sursa(job #2838777)

Utilizator DordeDorde Matei Dorde Data 24 ianuarie 2022 16:34:00
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.36 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
typedef long long ll;
struct Node0{
    int nr = 0;
    Node0 *ls = 0x0 , *rs = 0x0;
};
struct aint0{
    Node0 *root = 0x0;
    void update(Node0 *&node , int st , int dr , int y){
        if(node == 0x0)
            node = new Node0;
        if(st == dr){
            ++ node->nr;
            return;
        }
        int m = (st + dr) >> 1;
        if(y > m)
            update(node->rs , m + 1 , dr , y);
        else
            update(node->ls , st , m , y);
        ++ node->nr;
    }
    int query(Node0 *&node , int st , int dr , int from , int to){
        if(node == 0x0)
            return 0;
        if(st >= from && dr <= to)
            return node->nr;
        if(st > to || dr < from)
            return 0;
        int m = (st + dr) >> 1;
        return query(node->ls , st , m , from , to) + query(node->rs , m + 1 , dr , from , to);
    }
};
struct Node1{
    int cnt = 0;
    aint0 arb;
    Node1 *ls = 0x0 , *rs = 0x0;
};
struct aint1{
    Node1 *Root = 0x0;
    void update(Node1 *&node , int st , int dr , int x , int y){
        if(node == 0x0)
            node = new Node1;
        int m = (st + dr) >> 1;
        if(st == dr){
            node->arb.update(node->arb.root , -2e9 , 2e9 , y);
            return;
        }
        if(x > m)
            update(node->rs , m + 1 , dr , x , y);
        else
            update(node->ls , st , m , x , y);
        node->arb.update(node->arb.root , -2e9 , 2e9 , y);
    }
    int query(Node1 *&node , int st , int dr , int x , int y , int z , int w){
        if(node == 0x0)
            return 0;
        if(st > z || dr < x)
            return 0;///[x , z] disj [st , dr]
        if(st >= x && dr <= z)
            return node->arb.query(node->arb.root , -2e9 , 2e9 , y , w);
        int m = (st + dr) >> 1;
        return query(node->ls , st , m , x , y , z , w) + query(node->rs , m + 1 , dr , x , y , z , w);
    }
}T;
int main()
{
    int n , q , a , b , c , d;
    fin >> n;
    for(int i = 1 ; i <= n ; ++ i){
        fin >> a >> b;
        T.update(T.Root , -2e9 , 2e9 , a , b);
    }
    fin >> q;
    for(int i = 1 ; i <= q ; ++ i){
        fin >> a >> b >> c >> d;
        fout << T.query(T.Root , -2e9 , 2e9 , a , b , c , d) << '\n';

    }
    return 0;
}