제출 #1299698

#제출 시각아이디문제언어결과실행 시간메모리
1299698anarch_yExamination (JOI19_examination)C++20
100 / 100
287 ms21240 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> 
using index_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct Pt{
    int t, x, y, id;
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, q; cin >> n >> q;
    vector<pair<int, int>> sc;
    for(int i=0; i<n; i++){
        int s, t; cin >> s >> t;
        sc.pb({s, t});
    }
    sort(all(sc), [](pair<int, int> a, pair<int, int> b){
        return a.first + a.second > b.first + b.second;
    });
    vector<vector<int>> qry;
    for(int i=1; i<=q; i++){
        int a, b, c; cin >> a >> b >> c;
        qry.pb({c, a, b, i});
    }
    sort(all(qry), greater<>());
    vector<Pt> v;
    int j1 = 0, t = 1;
    for(int i=0; i<q; i++){
        int c = qry[i][0], a = qry[i][1], b = qry[i][2], id = qry[i][3];
        while(j1 < n and sc[j1].first + sc[j1].second >= c){
            v.pb({t, sc[j1].first, sc[j1].second, 0});
            j1++; t++; 
        }
        v.pb({t, a, b, id});
        t++;
    }
    vector<int> ans(q+1);
    auto solve = [&](auto solve, int l, int r){
        if(l == r) return;
        int m = (l+r)/2;
        solve(solve, l, m);
        solve(solve, m+1, r);
        vector<Pt> w;
        index_set<pair<int, int>> ts;
        int i = l, j = m+1;
        while(i <= m and j <= r){
            if(v[i].x >= v[j].x){
                if(v[i].id == 0){
                    ts.insert({v[i].y, v[i].t});
                }
                w.pb(v[i]);
                i++;
            }
            else{
                if(v[j].id != 0){
                    ans[v[j].id] += sz(ts) - ts.order_of_key({v[j].y, 0});
                }
                w.pb(v[j]);
                j++;
            }
        }
        while(i <= m){
            w.pb(v[i]);
            i++;
        }
        while(j <= r){
            if(v[j].id != 0){
                ans[v[j].id] += sz(ts) - ts.order_of_key({v[j].y, 0});
            }
            w.pb(v[j]);
            j++;
        }
        for(int k=l; k<=r; k++){
            v[k] = w[k-l];
        }
        ts.clear();
    };
    solve(solve, 0, sz(v)-1);
    for(int i=1; i<=q; i++) cout << ans[i] << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...