Submission #920839

#	Time	Username	Problem	Language	Result	Execution time	Memory
920839		Warinchai	Examination (JOI19_examination)	C++14	100 / 100	319 ms	25880 KiB

examination

#include<bits/stdc++.h>
using namespace std;
int n,q;
struct point{
    int i,x,y,z;
    point(int id=0,int a=0,int b=0,int c=0){
        i=id,x=a,y=b,z=c;
    }
    bool operator<(const point &t){
        return x==t.x?y>t.y:x<t.x;
    }
};
vector<point>v;
int ans[600005];
point temp[600005];
struct fenwick{
    int info[600005];
    void upd(int id,int val){
        for(int i=id;i<=600000;i+=i&-i)info[i]+=val;
    }
    int fsum(int id){
        int ans=0;
        for(int i=id;i>0;i-=i&-i){
            ans+=info[i];
        }
        return ans;
    }
}fw;
void solve(int st,int en){
    if(st==en)return;
    int m=(st+en)/2;
    solve(st,m);
    solve(m+1,en);
    //cerr<<st<<" "<<en<<"\n";
    int i=st,j=m+1;
    int id=st;
    //cerr<<"in solve work\n";
    while(i<=m||j<=en){
        if(j>en||(i<=m&&v[i].y>v[j].y)){
            temp[id++]=v[i];
            if(v[i].i<=n)fw.upd(v[i].z,1);
            i++;
        }else{
            temp[id++]=v[j];
            ans[v[j].i]+=fw.fsum(600000)-fw.fsum(v[j].z);
            j++;
        }
    }
    //cerr<<"in solve work\n";
    for(int i=st;i<=m;i++)if(v[i].i<=n)fw.upd(v[i].z,-1);
    for(int i=st;i<=en;i++)v[i]=temp[i];
}
vector<int>val;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        v.push_back(point(i,a,b,a+b));
        val.push_back(a);
        val.push_back(b);
        val.push_back(a+b);
    }
    for(int i=1;i<=q;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v.push_back(point(n+i,a,b,c));
        val.push_back(a);
        val.push_back(b);
        val.push_back(c);
    }
    sort(val.begin(),val.end());
    //for(auto x:val)cerr<<x<<" ";
    //cerr<<"\n";
    for(auto &x:v){
        //cerr<<lower_bound(val.begin(),val.end(),x.x)-val.begin()<<"+"<<1<<"\n";
        x.x=lower_bound(val.begin(),val.end(),x.x)-val.begin()+1;
        x.y=lower_bound(val.begin(),val.end(),x.y)-val.begin()+1;
        x.z=lower_bound(val.begin(),val.end(),x.z)-val.begin()+1;
        if(x.i>n)x.x--,x.y--,x.z--;
    }
    //cerr<<"work\n";
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    //for(auto x:v)cerr<<x.i<<" "<<x.x<<" "<<x.y<<" "<<x.z<<"\n";
    //cerr<<"work\n";
    solve(0,v.size()-1);
    //cerr<<"work\n";
    for(int i=n+1;i<=n+q;i++){
        cout<<ans[i]<<"\n";
    }
}

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