Submission #1357449

#TimeUsernameProblemLanguageResultExecution timeMemory
1357449AgageldiExamination (JOI19_examination)C++20
100 / 100
987 ms62336 KiB
#include <bits/stdc++.h>
using namespace std;

#define N 1000005
#define int long long
#define f first
#define s second

const int inf = 1e18;

int tc = 1, n, fy[N], fx[N], Q, ans[N], fn[N], q;
vector <tuple <int, int, int, int>> q2;
vector <tuple <int, int, int >> q1, v2;
map <int,int> vis;
pair <int,int> a[N];
void upd(int x,int vl) {
    for(; x > 0; x -= (x & (-x))) {
        fn[x] += vl;
    }
    return;
}
int find(int x) {
    int s = 0;
    for(; x < N; x += (x & (-x))) {
        s += fn[x];
    }
    return s;
}
void update(int x,int y) {
    for(; x < N; x += (x & (-x))) {
        fx[x]++;
    }
    for(; y < N; y += (y & (-y))) {
        fy[y]++;
    }
}
int solve(int x,int y) {
    int s = 0;
    for(; x > 0; x -= (x & (-x))) {
        s += fx[x];
    }
    for(; y > 0; y -= (y & (-y))) {
        s += fy[y];
    }
    return s;
}

int32_t main() {
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n >> Q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].f >> a[i].s;
        vis[a[i].f] = vis[a[i].s] = vis[a[i].f + a[i].s] = 1;
    }
    for(int i = 1; i <= Q; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        vis[x] = vis[y] = vis[z] = 1;
        if(x + y >= z) {
            q1.push_back({x, y, i});
        }
        else {
            q2.push_back({z, x, y, i});
        }
    }
    int inx = 1;
    for(auto [i, j] : vis) {
        vis[i] = inx++;
    }
    
    for(int i = 1; i <= n; i++) {
        int s = a[i].f + a[i].s;
        a[i].f = vis[a[i].f];
        a[i].s = vis[a[i].s];
        v2.push_back({vis[s], a[i].f, a[i].s});
    }

    sort(a + 1, a + n + 1);
    sort(q1.rbegin(),q1.rend());
    sort(q2.rbegin(),q2.rend());
    sort(v2.rbegin(),v2.rend());

    int i1 = n;
    for(auto [x, y, pos] : q1) {
        x = vis[x];
        y = vis[y];
        while(i1 >= 1 && a[i1].f >= x) {
            upd(a[i1].s, 1);
            i1--;
        }
        ans[pos] = find(y);
    }
    int i2 = 0;
    for(auto [sm, x, y, pos] : q2) {
        x = vis[x];
        y = vis[y];
        sm = vis[sm];
        while(i2 < n && get<0> (v2[i2]) >= sm) {
            update(get<1>(v2[i2]), get<2> (v2[i2]));
            i2++;
        }
        ans[pos] = i2 - solve(x - 1, y - 1);
    }
    for(int i = 1; i <= Q; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...