제출 #705867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
705867		Darren0724	Examination (JOI19_examination)	C++17	100 / 100	331 ms	19644 KiB

examination

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
const int N=600005;
struct D{
    int a,b,c,id,ans=0;
    D(){}
    D(int a1,int b1,int c1,int d1,int e1){
        a=a1,b=b1,c=c1,id=d1,ans=e1;
    }
};
vector<int> bit(N+1);
void add(int p,int x){
    //cout<<p<<' '<<x<<endl;
    for(int i=p;i<=N;i+=(i&-i)){
        bit[i]+=x;
    }
}
int ask(int p){
    int ans=0;
    for(int i=p;i>0;i-=i&(-i)){
        ans+=bit[i];
    }
    return ans;
}

vector<D> v;
void dc(int l,int r){
    if(r-l==1){
        return;
    }
    int m=(l+r)>>1;
    dc(l,m);
    dc(m,r);
    int ptr=0;
    vector<D> a(r-l);
    int ptr1=l,ptr2=m;
    while(ptr1<m&&ptr2<r){
        if(v[ptr1].b<=v[ptr2].b){
            if(v[ptr1].id==-1)add(v[ptr1].c,1);
            a[ptr++]=v[ptr1];
            ptr1++;
        }
        else{
            if(v[ptr2].id!=-1)v[ptr2].ans+=ask(v[ptr2].c);
            a[ptr++]=v[ptr2];
            ptr2++;
        }
    }
    while(ptr1<m){
        if(v[ptr1].id==-1)add(v[ptr1].c,1);
        a[ptr++]=v[ptr1];
        ptr1++;
    }
    while(ptr2<r){
        v[ptr2].ans+=ask(v[ptr2].c);
        a[ptr++]=v[ptr2];
        ptr2++;
    }
    for(int i=l;i<m;i++){
        if(v[i].id==-1)add(v[i].c,-1);
    }
    for(int i=0;i<r-l;i++){
        v[l+i]=a[i];
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    v.resize(n+m);
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        v[i]=D(a,b,a+b,-1,0);
    }
    for(int i=0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;
        v[i+n]=D(a,b,c,i,0);
    }
    vector<int> g;
    for(int i=0;i<n+m;i++){
        g.push_back(v[i].a);
        g.push_back(v[i].b);
        g.push_back(v[i].c);
    }
    sort(all(g));
    g.resize(unique(all(g))-g.begin());
    for(int i=0;i<n+m;i++){
        v[i].a=lower_bound(all(g),v[i].a)-g.begin()+1;
        v[i].b=lower_bound(all(g),v[i].b)-g.begin()+1;
        v[i].c=lower_bound(all(g),v[i].c)-g.begin()+1;
        v[i].a=N-v[i].a;
        v[i].b=N-v[i].b;
        v[i].c=N-v[i].c;
    }
    sort(all(v),[](D x,D y){return (x.a!=y.a?x.a<y.a:x.id<y.id);});
    dc(0,n+m);
    vector<int> ans(m);
    for(int i=0;i<n+m;i++){
        if(v[i].id!=-1){
            ans[v[i].id]=v[i].ans;
        }
    }
    for(int i=0;i<m;i++){
        cout<<ans[i]<<'\n';
    }

    return 0;
}

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