제출 #623971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
623971		radal	Examination (JOI19_examination)	C++17	100 / 100	1929 ms	126016 KiB

examination

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 1e5+10,mod = 998244353,inf = 1e9+10,sq = 700;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k /= 2;
    } 
    return z; 
}
int a[N],b[N],ans[N],ind[N],c[N];
ordered_set seg[N*4];
pair<pll,pll> Q[N];
vector<int> vec,vea;

bool cmpc(int i,int j){
    return (c[i] > c[j]);
}

bool cmpa(int i,int j){
    return (a[i] < a[j]);
}

void upd(int l,int r,int p,int v = 1){
    seg[v].insert(b[vea[p]]);
    if (r-l == 1) return;
    int m = (l+r) >> 1,u = (v << 1);
    if (p < m) upd(l,m,p,u);
    else upd(m,r,p,u|1);
}
int que(int l,int r,int s,int e,int B,int v = 1){
    if (seg[v].empty() || l >= e || s >= r) return 0;
    if (s <= l && r <= e){
        return seg[v].size()-seg[v].order_of_key(B);
    }
    int m = (l+r) >> 1,u = (v << 1);
    return que(l,m,s,e,B,u)+que(m,r,s,e,B,u|1);
}
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);
    int n,q;
    cin >> n >> q;
    vector<pll> ub;
    rep(i,0,n){
        cin >> a[i] >> b[i];
        c[i] = a[i]+b[i];
        vec.pb(i);
        vea.pb(i);
        ub.pb({b[i],i});
    }
    sort(all(vec),cmpc);
    sort(all(vea),cmpa);
    rep(i,0,n) ind[vea[i]] = i;
    rep(i,0,q){
        cin >> Q[i].Y.X >> Q[i].Y.Y >> Q[i].X.X;
        Q[i].X.Y = i;
        ub.pb({Q[i].Y.Y,-n-i});
    }
    sort(all(ub));
    rep(i,0,n+q){
        if(ub[i].Y >= 0){
            b[ub[i].Y] = i;
        }
        else{
            Q[-ub[i].Y-n].Y.Y = i;
        }
    }
    sort(Q,Q+q);
    reverse(Q,Q+q);
    int po = 0;
    rep(i,0,q){
        int C = Q[i].X.X,A = Q[i].Y.X,B = Q[i].Y.Y;
        while (po < n && c[vec[po]] >= C){
            upd(0,n,ind[vec[po]],1);
            po++;
        }
        int l = -1,r = n,m;
        while (r-l > 1){
            m = (l+r) >> 1;
            if (A <= a[vea[m]]) r = m;
            else l = m;
        }
        ans[Q[i].X.Y] = que(0,n,r,n,B);
    }
    rep(i,0,q) cout << ans[i] << endl;
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57