Submission #1014329

#TimeUsernameProblemLanguageResultExecution timeMemory
1014329fryingducExamination (JOI19_examination)C++17
100 / 100
414 ms32240 KiB
#include "bits/stdc++.h"
using namespace std;

const int maxn = 1e5 + 5;
const int inf = 1e9;
int n, q, s[maxn], t[maxn];
int a[maxn], b[maxn];
int ord[maxn];
vector<int> bit[maxn];
int ans[maxn];

struct query {
    int x, y, z, id;
    bool operator<(const query &o) {
        return z > o.z;
    }
} que[maxn];

vector<int> cx, cy;
#define gb(x) (x) & (-x)
struct fenwick_tree {
    int n;
    vector<int> bit;
    fenwick_tree() {}
    fenwick_tree(int n) : n(n), bit(n + 5) {}
    inline void update(int x, int val) {
        for(int i = x; i <= n; i += gb(i)) bit[i] = bit[i] + val;
    }
    inline int get(int x) {
        int ans = 0;
        for(int i = x; i > 0; i -= gb(i)) ans = ans + bit[i];
        return ans;
    }
} tree[maxn];
vector<int> sz[maxn];
struct segment_tree {
    int n;
    segment_tree() {}
    segment_tree(int n) : n(n) {}
    
    inline void resize_tree(int pos, int fen_pos) {
        for(int i = pos; i <= n; i += gb(i)) {
            sz[i].push_back(fen_pos);
        }
    }
    inline void refine() {
        for(int ind = 1; ind <= n; ++ind) {
            if(sz[ind].empty()) continue;
            
            sort(sz[ind].begin(), sz[ind].end());
            sz[ind].erase(unique(sz[ind].begin(), sz[ind].end()), sz[ind].end());
            
            tree[ind] = fenwick_tree((int)sz[ind].size() + 2);
        }
    }
    inline void update(int pos, int fen_pos, int val) {
        int p;
        for(int i = pos; i <= n; i += gb(i)) {
            p = lower_bound(sz[i].begin(), sz[i].end(), fen_pos) - sz[i].begin() + 1;
            tree[i].update(p, val);
        }
    }
    inline int get(int pos, int fen_pos) {
        int ans = 0;
        int p;
        for(int i = pos; i > 0; i -= gb(i)) {
            p = upper_bound(sz[i].begin(), sz[i].end(), fen_pos) - sz[i].begin();
            if(p == 0) continue;
            ans = ans + tree[i].get(p);
        }   
        return ans;
    }
    int get(int l, int r, int pos) {
        return get(r, pos) - get(l - 1, pos);
    }
} st;
void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> s[i] >> t[i];
    }
    for(int i = 1; i <= q; ++i) {
        cin >> que[i].x >> que[i].y >> que[i].z;
        que[i].id = i;
    }
    iota(ord + 1, ord + n + 1, 1);
    sort(ord + 1, ord + n + 1, [](const int &x, const int &y) -> bool {
        return (s[x] + t[x]) > (s[y] + t[y]);
    });
    for(int i = 1; i <= n; ++i) {
        cx.push_back(s[i]);
        cy.push_back(t[i]);
    }
    sort(cx.begin(), cx.end());
    sort(cy.begin(), cy.end());
    cx.erase(unique(cx.begin(), cx.end()), cx.end());
    cy.erase(unique(cy.begin(), cy.end()), cy.end());
    st = segment_tree((int)cx.size());
    for(int i = 1; i <= n; ++i) {
        a[i] = lower_bound(cx.begin(), cx.end(), s[i]) - cx.begin() + 1;
        b[i] = lower_bound(cy.begin(), cy.end(), t[i]) - cy.begin() + 1;
        st.resize_tree(a[i], t[i]);
    }
    st.refine();
    sort(que + 1, que + q + 1);
    
    int j = 1;
    for(int i = 1; i <= q; ++i) {
        while(j <= n and s[ord[j]] + t[ord[j]] >= que[i].z) {
            st.update(a[ord[j]], t[ord[j]], 1);
            ++j;
        }
        int p = lower_bound(cx.begin(), cx.end(), que[i].x) - cx.begin() + 1;
        ans[que[i].id] = st.get(p, (int)cx.size(), inf);
        ans[que[i].id] -= st.get(p, (int)cx.size(), que[i].y - 1);
    }
    for(int i = 1; i <= q; ++i) {
        cout << ans[i] << '\n';
    }
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...