제출 #126887

#제출 시각아이디문제언어결과실행 시간메모리
126887Osama_AlkhodairyExamination (JOI19_examination)C++17
2 / 100
3002 ms168496 KiB
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long
 
const int N = 100001;
const int A = 200001;
const int INF = (int)1e9;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree <pair <int, int>, null_type, less <pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
struct query{
    int A, B, ind;
};
 
int n, m;
vector <pair <int, int> > a;
vector <query> q[A];
vector <int> sum[A];
ordered_set v[4 * N];
map <int, int> mp;
 
void insert(ordered_set &s, int v){
    auto it = s.upper_bound(make_pair(v, INF));
    if(it == s.begin()){
        s.insert(make_pair(v, 0));
        return;
    }
    it--;
    if(it == s.end() || (*it).first != v) s.insert(make_pair(v, 0));
    else s.insert(make_pair(v, (*it).second + 1));
}
void erase(ordered_set &s, int v){
    auto it = s.upper_bound(make_pair(v, INF));
    assert(it != s.begin());
    it--;
    assert((*it).first == v);
    s.erase(it);
}
void update(int l, int r, int node, int ind, int val){
    if(r < l || l > ind || r < ind) return;
    insert(v[node], val);
    if(l == r) return;
    int mid = (l + r) / 2;
    if(ind <= mid) update(l, mid, 2 * node, ind, val);
    update(mid + 1, r, 2 * node + 1, ind, val);
}
int query(int l, int r, int node, int s, int e, int val){
    if(r < l || r < s || l > e) return 0;
    if(s <= l && r <= e){
        return (int)v[node].size() - v[node].order_of_key(make_pair(val, -INF));
    }
    int mid = (l + r) / 2;
    return query(l, mid, 2 * node, s, e, val) + query(mid + 1, r, 2 * node + 1, s, e, val);
}
void erase(int l, int r, int node, int ind){
    if(r < l) return;
    erase(v[node], a[ind].second);
    if(l == r) return;
    int mid = (l + r) / 2;
    if(ind <= mid) erase(l, mid, 2 * node, ind);
    else erase(mid + 1, r, 2 * node + 1, ind);
}
int query(int suffix, int val){
    return query(0, n - 1, 1, suffix, n - 1, val);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    a.resize(n);
    for(auto &i : a) cin >> i.first >> i.second;
    sort(a.begin(), a.end());
    for(int i = 0 ; i < n ; i++){
        update(0, n - 1, 1, i, a[i].second);
    }
    for(int i = 0 ; i < n ; i++){
        mp[a[i].first + a[i].second];
    }
    vector <pair <pair <int, int>, pair <int, int> > > queries;
    for(int i = 0 ; i < m ; i++){
        int x, y, z;
        cin >> x >> y >> z;
        queries.push_back(make_pair(make_pair(x, y), make_pair(z, i)));
        mp[z];
    }
    int x = 0;
    for(auto &i : mp) i.second = ++x;
    for(auto &j : queries){
        int x = j.first.first;
        int y = j.first.second;
        int z = j.second.first;
        int i = j.second.second;
        q[mp[z]].push_back({x, y, i});
    }
    for(int i = 0 ; i < n ; i++){
        sum[mp[a[i].first + a[i].second]].push_back(i);
    }
    vector <int> ans(m);
    for(int i = 0 ; i < A ; i++){
        for(auto &j : q[i]){
            int suff = lower_bound(a.begin(), a.end(), make_pair(j.A, -INF)) - a.begin();
            if(suff == n) ans[j.ind] = 0;
            else ans[j.ind] = query(suff, j.B);
        }
        for(auto &j : sum[i]){
            erase(0, n - 1, 1, j);
        }
    }
    for(auto &i : ans) cout << i << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...