Cod sursa(job #2058724)

Utilizator retrogradLucian Bicsi retrograd Data 6 noiembrie 2017 01:07:49
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
using namespace __gnu_pbds;

template<typename T>
using Tree = tree<T, null_type, less<T>, 
      rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    ifstream cin("zoo.in");
    ofstream cout("zoo.out");

    int n; cin >> n;
    
    vector<tuple<int, int, int, int>> q;
    for (int i = 0; i < n; ++i) {
        int x, y; cin >> x >> y;
        q.emplace_back(x, y, -2, i);
    }

    int m; cin >> m;
    for (int i = 0; i < m; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        q.emplace_back(x2, y2, 1, i);
        q.emplace_back(x1 - 1, y2, -1, i);
        q.emplace_back(x2, y1 - 1, -1, i);
        q.emplace_back(x1 - 1, y1 - 1, 1, i);
    }

    sort(q.begin(), q.end());
    Tree<pair<int, int>> ptree;
    vector<int> ans(m);

    for (auto elem : q) {
        int x, y, t, i; tie(x, y, t, i) = elem;
        if (t == -2) ptree.insert({y, i});
        else {
            ans[i] += t * ptree.order_of_key({y, 1e9});
        }
    }

    for (auto x : ans) cout << x << '\n';

    return 0;
}