Submission #578352

#TimeUsernameProblemLanguageResultExecution timeMemory
578352OttoTheDinoExamination (JOI19_examination)C++17
43 / 100
3081 ms307172 KiB
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (int i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define aint(a)                      a.begin(), a.end()
#define len(a)                      (int)a.size()
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<int> vint;

unordered_map<int,int> seg_tree[2] = {};
unordered_map<int,int> lazy[2] = {};
 
void upd (int tp, int val, int l, int r, int bl, int br, int id) {
    seg_tree[tp][id] += val;
    if (l==bl && r==br) {
        lazy[tp][id] += val;
        return;
    }
    int mid = (bl+br)/2;
    if (r<=mid) upd (tp, val, l, r, bl, mid, 2*id);
    else if (l>mid) upd (tp, val, l, r, mid+1, br, 2*id+1);
    else {
        upd (tp, val, l, mid, bl, mid, 2*id);
        upd (tp, val, mid+1, r, mid+1, br, 2*id+1);
    }
} 
 
int query (int tp, int l, int r, int bl, int br, int id) {
    if (l==bl && r==br) return seg_tree[tp][id];
    if (bl!=br) {
        lazy[tp][2*id] += lazy[tp][id];
        lazy[tp][2*id+1] += lazy[tp][id];
        seg_tree[tp][2*id] += lazy[tp][id];
        seg_tree[tp][2*id+1] += lazy[tp][id];
        lazy[tp][id] = 0;
    }
    int mid = (bl+br)/2;
    if (r<=mid) return query (tp, l, r, bl, mid, 2*id);
    if (l>mid) return query (tp, l, r, mid+1, br, 2*id+1);
    return query (tp, l, mid, bl, mid, 2*id) + query (tp, mid+1, r, mid+1, br, 2*id+1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, q, x = 0; cin >> n >> q;

    vector<pair<int,ii>> peep;
    vector<pair<ii,ii>> ques;
    int ans[q+1];

    rep (i,1,n) {
        int a, b; cin >> a >> b;
        peep.pb({a+b,{a,b}});
    }

    rep (i,1,q) {
        int a, b, c; cin >> a >> b >> c;
        ques.pb({{max(a+b,c),i},{a,b}});
    }

    sort(aint(ques));
    reverse(aint(ques));
    sort(aint(peep));
    reverse(aint(peep));

    rep (i,0,q-1) {
        int c = ques[i].fi.fi, a = ques[i].se.fi, b = ques[i].se.se, u = ques[i].fi.se;
        while (x < n && peep[x].fi>=c) {
            upd (0, 1, peep[x].se.fi, peep[x].se.fi, 0, 1e9, 1);
            upd (1, 1, peep[x].se.se, peep[x].se.se, 0, 1e9, 1);
            x++;
        }
        ans[u] = query(0,a,1e9,0,1e9,1) + query(1,b,1e9,0,1e9,1) - x;
    }

    rep (i,1,q) cout << ans[i] << "\n";

    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...