제출 #1157709

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157709		AlgorithmWarrior	Examination (JOI19_examination)	C++20	100 / 100	591 ms	54200 KiB

examination

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>o_set;
int const MAX=1e5+5;
int n,q;
struct point{
    int x,y,z,id;
};

bool cmpx(point a,point b){
    return a.x>b.x;
}

bool cmpz(point a,point b){
    return a.z>b.z;
}

point pct[MAX];
point queries[MAX];
int answer[MAX];
int zs[MAX];

int ub(int x){
    return x&(-x);
}

struct AIB{
    o_set v[MAX];
    void add(int pos,int val){
        while(pos<=n){
            v[pos].insert(val);
            pos+=ub(pos);
        }
    }
    int prefix_larger(int pos,int val){
        int cnt=0;
        while(pos){
            cnt+=v[pos].size()-v[pos].order_of_key(val);
            pos-=ub(pos);
        }
        return cnt;
    }
}aib;

int bin_search(int val){
    /// [)
    int st=0,dr=n+1;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(zs[mij]>=val)
            st=mij;
        else
            dr=mij;
    }
    return st;
}

void read(){
    cin>>n>>q;
    int i;
    for(i=1;i<=n;++i){
        cin>>pct[i].x>>pct[i].y;
        pct[i].z=pct[i].x+pct[i].y;
    }
    sort(pct+1,pct+n+1,cmpz);
    for(i=1;i<=n;++i){
        pct[i].id=i;
        zs[i]=pct[i].z;
    }
    sort(pct+1,pct+n+1,cmpx);
    for(i=1;i<=q;++i){
        cin>>queries[i].x>>queries[i].y>>queries[i].z;
        queries[i].id=i;
    }
    sort(queries+1,queries+q+1,cmpx);
}

void solve(){
    int id=1;
    int i;
    for(i=1;i<=q;++i){
        while(id<=n && pct[id].x>=queries[i].x){
            aib.add(pct[id].id,pct[id].y);
            ++id;
        }
        answer[queries[i].id]=aib.prefix_larger(bin_search(queries[i].z),queries[i].y);
    }
}

void write(){
    int i;
    for(i=1;i<=q;++i)
        cout<<answer[i]<<'\n';
}

int main()
{
    read();
    solve();
    write();
    return 0;
}

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