Submission #616106

#	Time	Username	Problem	Language	Result	Execution time	Memory
616106		Iwanttobreakfree	Examination (JOI19_examination)	C++17	2 / 100	3049 ms	30640 KiB

examination

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <set>
using namespace std;
#define pii pair<int,int>
unordered_map<int,int> mp_m,mp_i,mp_a,av;
vector<int> BIT,cnt;
int sz=400;
int next(int x){return x + (x&(-x));}
int par(int x){return x - (x&(-x));}
bool cmp(pair<pii,pii>& a,pair<pii,pii>& b){
    if(a.first.first/sz!=b.first.first/sz)return a.first.first/sz<b.first.first/sz;
    return a.first.second<b.first.second;
}
int bin_find(int x,vector<int>& v){
    int l=0,r=v.size()-1,ans=v.size();
    while(l<=r){
        int mid=(r+l)/2;
        if(v[mid]<x)l=mid+1;
        else {
            ans=mid;
            r=mid-1;
        }
    }
    return ans;
}
void pupd(int x,int k){
    //cout<<x<<' '<<k<<'\n';
    for(int i=x;i<BIT.size();i=next(i))BIT[i]+=k;
}
int sum(int x){
    int ans=0;
    for(int i=x;i>0;i=par(i))ans+=BIT[i];
    return ans;
}
int val(int l,int r){
    return sum(r)-sum(l);
}
void add(int i,vector<vector<int>>& g,vector<int>& exam){
    //cout<<i<<' ';
    for(int x:g[i]){
        cnt[x]++;
        if(cnt[x]==2)pupd(mp_a[exam[x]]+1,1);
    }
    //cout<<i<<' '<<'\n';
}
void del(int i,vector<vector<int>>& g,vector<int>& exam){
    for(int x:g[i]){
        if(cnt[x]==2)pupd(mp_a[exam[x]]+1,-1);
        cnt[x]--;
    }
}
vector<vector<int>> math,info;
void MO(int q,vector<int>& m,vector<int>& in,vector<int>& av,vector<int>& exam){
    int x,y,z;
    vector<pair<pii,pii>> qu(q);
    vector<int> ans(q);
    for(int i=0;i<q;i++){
        cin>>x>>y>>z;
        qu[i]={{x,y},{z,i}};
    }
    sort(qu.begin(),qu.end(),cmp);
    int l_math=m.size(),l_info=in.size();
    for(int i=0;i<q;i++){
        int min_math=bin_find(qu[i].first.first,m),min_info=bin_find(qu[i].first.second,in),min_av=bin_find(qu[i].second.first,av);
        if(min_math==m.size()||min_info==in.size()||min_av==av.size()){
            ans[qu[i].second.second]=0;
            continue;
        }
        //cout<<l_math<<' '<<l_info<<'\n';
        while(l_math>min_math){
            l_math--;
            add(l_math,math,exam);
        }
        while(l_math<min_math){
            del(l_math,math,exam);
            l_math++;
        }
        //cout<<l_math<<' '<<l_info<<'\n';
        while(l_info>min_info){
            l_info--;
            //cout<<l_info<<' ';
            add(l_info,info,exam);
        }
        //cout<<l_info<<' ';
        while(l_info<min_info){
            del(l_info,info,exam);
            l_info++;
        }
        //cout<<l_math<<' '<<l_info<<' '<<qu[i].first.first<<'\n';
        ans[qu[i].second.second]=val(min_av,BIT.size()-1);
    }
    for(int i=0;i<q;i++)cout<<ans[i]<<'\n';
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n,q,x,y;
    cin>>n>>q;
    set<int> m,in,av;
    cnt=vector<int>(n);
    vector<int> exam_math(n),exam_info(n),exam_av(n),a,b,c;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        m.insert(x);
        in.insert(y);
        av.insert((x+y));
        exam_math[i]=x;
        exam_info[i]=y;
        exam_av[i]=(x+y);
    }
    mp_m.reserve(131072);
    mp_i.reserve(131072);
    mp_a.reserve(131072);
    int cntm=0,cnti=0,cnta=0;
    for(int x:m){
        mp_m[x]=cntm;
        cntm++;
        a.push_back(x);
    }
    for(int x:in){
        mp_i[x]=cnti;
        cnti++;
        b.push_back(x);
    }
    for(int x:av){
        mp_a[x]=cnta;
        cnta++;
        c.push_back(x);
    }
    BIT=vector<int> (cnta+1);
    math=vector<vector<int>> (cntm,vector<int>());
    info=vector<vector<int>> (cnti,vector<int>());
    for(int i=0;i<n;i++){
        math[mp_m[exam_math[i]]].push_back(i);
        info[mp_i[exam_info[i]]].push_back(i);
    }
    MO(q,a,b,c,exam_av);
}

Compilation message (stderr)

examination.cpp: In function 'void pupd(int, int)':
examination.cpp:31:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for(int i=x;i<BIT.size();i=next(i))BIT[i]+=k;
      |                 ~^~~~~~~~~~~
examination.cpp: In function 'void MO(int, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
examination.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if(min_math==m.size()||min_info==in.size()||min_av==av.size()){
      |            ~~~~~~~~^~~~~~~~~~
examination.cpp:68:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if(min_math==m.size()||min_info==in.size()||min_av==av.size()){
      |                                ~~~~~~~~^~~~~~~~~~~
examination.cpp:68:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         if(min_math==m.size()||min_info==in.size()||min_av==av.size()){
      |                                                     ~~~~~~^~~~~~~~~~~

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