Cod sursa(job #2618562)

Utilizator CraniXortDumitrescul Eduard CraniXort Data 25 mai 2020 13:54:46
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <bits/stdc++.h>
#define maxn 200005
std::ifstream fin ("zoo.in");
std::ofstream fout ("zoo.out");

struct str{
    int x, y, type, index;
};

std::vector <str> arr;
bool sort_cond (str a, str b){
    if (a.y != b.y) return a.y < b.y;
    return a.type > b.type;
}
bool sort_X (str a, str b){
    return a.x < b.x;
}

bool sort_Y (str a, str b){
    return a.y < b.y;
}


int bit[maxn];
void update (int pos, int val){
    while (pos < maxn){
        bit[pos] += val;
        pos = (pos | (pos+1));
    }
}
int query (int pos){
    int ans = 0;
    while (pos >= 0){
        ans += bit[pos];
        pos = (pos & (pos+1)) - 1;
    }
    return ans;
}

int ans[maxn];
int main()
{
    int n, i, Q;
    int x1, y1, x2, y2;
    int cnt, last;
    fin >> n;
    for (i=0; i<n; i++){
        fin >> x1 >> y1;
        arr.push_back ({x1, y1, 2, i});
    }
    fin >> Q;
    for (i=0; i<Q; i++){
        fin >> x1 >> y1 >> x2 >> y2;
        arr.push_back ({x2, y2, 1, i});
        arr.push_back ({x1-1, y1-1, 1, i});
        arr.push_back ({x2, y1-1, -1, i});
        arr.push_back ({x1-1, y2, -1, i});
    }

    std::sort (arr.begin(), arr.end(), sort_X);
    for (i=0, last=-2000000005, cnt=-1; i<arr.size(); i++){
        if (arr[i].x != last){
            cnt ++;
            last = arr[i].x;
        }
        arr[i].x = cnt;
    }


    //for (i=0; i<arr.size(); i++)
    //    fout << arr[i].x << ' ' << arr[i].y << ' ' << arr[i].type << ' ' << arr[i].index << '\n';

    std::sort (arr.begin(), arr.end(), sort_cond);
     for (i=0, last=-2000000005, cnt=-1; i<arr.size(); i++){
        if (arr[i].y != last){
            cnt ++;
            last = arr[i].y;
        }
        arr[i].y = cnt;
    }
    int my = cnt;

    for (int y=0, i=0; y<=my; y++){
        for (;arr[i].y == y and i < arr.size(); i++){
            if (arr[i].type == 2)
                update (arr[i].x, 1);
            else
                ans[arr[i].index] += arr[i].type * query (arr[i].x);
        }
    }

    for (i=0; i<Q; i++)
        fout << ans[i] << '\n';


    return 0;
}