Submission #210482

#	Time	Username	Problem	Language	Result	Execution time	Memory
210482		brcode	Examination (JOI19_examination)	C++14	100 / 100	646 ms	29272 KiB

examination

#include <iostream>
#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<
pair<int, int>,
null_type,
less_equal<pair<int, int>>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_set;



const long long MAXN = 5e5+5;
long long ans[MAXN];
long long seg[4*MAXN];
struct student{
    long long type,x,y,z;
};
student hold[MAXN];
long long n,q;
bool sortfirst(student a,student b){
    if(a.x==b.x){
        return a.type>b.type;
    }
    return a.x<b.x;
}
bool sortsecond(student a,student b){
    if(a.y==b.y){
        return a.type>b.type;
    }
    return a.y<b.y;
}
bool sortthird(student a,student b){
    if(a.z==b.z){
        return a.type>b.type;
    }
    return a.z<b.z;
}
vector<student> v1;

void f(long long l,long long r){
   
    v1.clear();
    long long mid =(l+r)/2;
    
    for(long long i=l;i<=mid;i++){
        if(hold[i].type != 1){
            
            v1.push_back(hold[i]);
        }
    }
    for(long long i=mid+1;i<=r;i++){
        if(hold[i].type == 1){
            v1.push_back(hold[i]);
        }
    }
    sort(v1.begin(),v1.end(),sortfirst);
    ordered_set s1; 
    int cnt = 0;
    for(long long i=v1.size()-1;i>=0;i--){
        if(v1[i].type == 1){
            s1.insert(make_pair(v1[i].y,cnt++));
            //cout<<v1[i].y<<endl;
        }else{
            ans[v1[i].type]+=s1.size()-s1.order_of_key(make_pair(v1[i].y,0));
           // cout<<l<<" "<<r<<" "<<" "<<v1[i].type<<" "<<ans[v1[i].type]<<endl;
        }
    }
    if(l!=mid){
        f(l,mid);
    }
    if(r!=mid+1){
        f(mid+1,r);
    }
    
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>q;
    //cout<<n<<" "<<q<<endl;
    for(long long i=1;i<=n;i++){
        long long s,t;
        cin>>s>>t;
        hold[i].type = 1;
        hold[i].x=s;
        hold[i].y=t;
        hold[i].z=s+t;
    }
    for(long long i=n+1;i<=n+q;i++){
        long long u,v,w;
        cin>>u>>v>>w;
        hold[i].type=i;
        hold[i].x=u;
        hold[i].y=v;
        hold[i].z=w;
        //queries.push_back(make_pair(make_pair(x,y),z));
    }
    sort(hold+1,hold+n+q+1,sortfirst);
    long long curr = 1;
    for(long long i=1;i<=n+q;i++){
        while(i<=n+q && hold[i].x==hold[i+1].x){
            hold[i].x=curr;
            i++;
        }
        hold[i].x = curr;
        curr++;
        
        
        
    }
   // cout<<curr<<endl;
    curr=1;
    sort(hold+1,hold+n+q+1,sortsecond);
    for(long long i=1;i<=n+q;i++){
        while(i<=n+q && hold[i].y==hold[i+1].y){
            hold[i].y=curr;
            i++;
        }
        hold[i].y=curr;
       // cout<<hold[i].y<<endl;
        curr++;
    }
    //cout<<curr<<endl;
    sort(hold+1,hold+n+q+1,sortthird);
    curr = 1;
    for(long long i=1;i<=n+q;i++){
        while(i<=n+q && hold[i].z==hold[i+1].z){
            hold[i].z=curr;
            i++;
        }
        hold[i].z = curr;
        //cout<<hold[i].z<<endl;
        curr++;
    }
   // cout<<curr<<endl;
    
    f(1,n+q);
    for(long long 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