Submission #1050895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050895		MrAndria	Examination (JOI19_examination)	C++14	100 / 100	1108 ms	143764 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
  
#define ordered_set tree<pair <int,int> , null_type,less<pair <int,int> >, rb_tree_tag,tree_order_statistics_node_update> 
//#define int long long
int n,q,ans[200005];
vector <int> v;
map <int,int> mp;
pair < pair <int,int> , pair <int,int> > pr[200005];
ordered_set bit[200100];
int sum(int idx,int val) {
    // cout<<"START2"<<" "<<idx<<endl;
    int ret = 0;
    for (idx; idx > 0; idx -= idx & -idx){
        ret += bit[idx].order_of_key(make_pair(-val,n+q+2));
        // cout<<ret<<" "<<idx <<" "<<bit[idx].size()<<endl;
    }
        

    return ret;
}

int sum(int l, int r,int val) {
    // cout<<"START1"<<" "<<val<<endl;

    return sum(r,val) - sum(l - 1,val);
}

void add(int idx, int delta,int y) {
    // cout<<idx<<" "<<delta<<" "<<y<<" "<<n+q+1<<" THIS SHIT"<<endl;
    for (idx; idx <= n+q+1; idx += idx & -idx){
        bit[idx].insert(make_pair(-delta,y));
        // cout<<idx<<" "<<delta<<endl;
    }
    
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>pr[i].ff.ff>>pr[i].ff.ss;
        pr[i].ss.ff=pr[i].ff.ff+pr[i].ff.ss;
        pr[i].ss.ss=1;
    }
    for(int i=1;i<=q;i++){
        cin>>pr[i+n].ff.ff>>pr[i+n].ff.ss>>pr[i+n].ss.ff;
        pr[i+n].ss.ss=-i;
    }
    sort(pr+1,pr+n+q+1);
    for(int i=1;i<=n+q;i++){
        mp[pr[i].ff.ff]++;
        if(mp[pr[i].ff.ff]==1){
            v.pb(pr[i].ff.ff);
        }
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++){
        mp[v[i]]=i+1;
    }
    for(int i=1;i<=n+q;i++){
        pr[i].ff.ff=mp[pr[i].ff.ff];
    }
    v.clear();
    mp.clear();

    for(int i=1;i<=n+q;i++){
        mp[pr[i].ff.ss]++;
        if(mp[pr[i].ff.ss]==1){
            v.pb(pr[i].ff.ss);
        }
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++){
        mp[v[i]]=i+1;
    }
    for(int i=1;i<=n+q;i++){
        pr[i].ff.ss=mp[pr[i].ff.ss];
    }
    v.clear();
    mp.clear();
    for(int i=1;i<=n+q;i++){
        mp[pr[i].ss.ff]++;
        if(mp[pr[i].ss.ff]==1){
            v.pb(pr[i].ss.ff);
        }
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++){
        mp[v[i]]=i+1;
    }
    for(int i=1;i<=n+q;i++){
        pr[i].ss.ff=mp[pr[i].ss.ff];
    }
    // for(int i=1;i<=n+q;i++){
    //     cout<<pr[i].ff.ff<<" "<<pr[i].ff.ss<<" "<<pr[i].ss.ff<<" "<<pr[i].ss.ss<<endl;
    // }
    for(int i=n+q;i>=1;i--){
        if(pr[i].ss.ss==1){
            add(pr[i].ff.ss,pr[i].ss.ff,i);

        }else{
            ans[-pr[i].ss.ss]=sum(pr[i].ff.ss,n+q,pr[i].ss.ff);
        }
    }
    // for(int i=1;i<=n+q+1;i++){
    //     // cout<<i<<" "<<bit[i].size()<<endl;
    //     // cout<<endl;
    // }
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<" ";
        
    }
    cout<<endl;
}

Compilation message (stderr)

examination.cpp: In function 'int sum(int, int)':
examination.cpp:20:10: warning: statement has no effect [-Wunused-value]
   20 |     for (idx; idx > 0; idx -= idx & -idx){
      |          ^~~
examination.cpp: In function 'void add(int, int, int)':
examination.cpp:37:10: warning: statement has no effect [-Wunused-value]
   37 |     for (idx; idx <= n+q+1; idx += idx & -idx){
      |          ^~~
examination.cpp: In function 'int main()':
examination.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
examination.cpp:78:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
examination.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

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