Submission #623274

#	Time	Username	Problem	Language	Result	Execution time	Memory
623274		Iwanttobreakfree	Examination (JOI19_examination)	C++17	43 / 100	3060 ms	43828 KiB

examination

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
#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=700,n,q;
int next(int x){return x + (x&(-x));}
int par(int x){return x - (x&(-x));}
bool cmp(pair<int,pair<pii,pii>>& a,pair<int,pair<pii,pii>>& b){
    if(a.first!=b.first)return a.first<b.first;
    if(a.first&1)return a.second.first.second<b.second.first.second;
    return a.second.first.second>b.second.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];
        //cout<<i<<' '<<BIT[i]<<'\n';
    }
    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<<ans<<' '<<'\n';
}
void del(int i,vector<vector<int>>& g,vector<int>& exam){
    //cout<<i<<' ';
    for(int x:g[i]){
        if(cnt[x]==2){
            pupd(mp_a[exam[x]]+1,-1);
        }
        cnt[x]--;
    }
    //cout<<ans<<'\n';
}
vector<vector<int>> math,info;
void MO(vector<int>& m,vector<int>& in,vector<int>& av,vector<int>& exam,vector<int>& id){
    int x,y,z;
    vector<pair<int,pair<pii,pii>>> qu(q);
    vector<int> answer(q);
    for(int i=0;i<q;i++){
        cin>>x>>y>>z;
        x=bin_find(x,m);
        y=bin_find(y,in);
        z=bin_find(z,av);
        //cout<<x<<' '<<y<<' '<<z<<' '<<id[x]<<'\n';
        qu[i]={id[x],{{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=qu[i].second.first.first,min_info=qu[i].second.first.second,min_av=qu[i].second.second.first;
        //cout<<min_math<<' '<<min_info<<'\n';
        if(min_av==av.size()){
            answer[qu[i].second.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].second.second<<' '<<ans<<' '<<sum(min_av)<<'\n';
        answer[qu[i].second.second.second]=val(min_av,BIT.size()-1);
    }
    for(int i=0;i<q;i++)cout<<answer[i]<<'\n';
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int 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> (max(cnta,cnti)+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);
    }
    vector<int> id(cntm+1);
    int cur=0,cont=0;
    for(int i=0;i<math.size();i++){
        if(math[i].size()>=sz){
            cont++;
            id[i]=cont;
            cont++;
            cur=0;
        }else if(math[i].size()+cur>sz){
            cur=0;
            id[i]=cont;
            cont++;
        }else{
            cur+=math[i].size();
            id[i]=cont;
        }
    }
    id[cntm]=cont;
    MO(a,b,c,exam_av,id);
}

Compilation message (stderr)

examination.cpp: In function 'void pupd(int, int)':
examination.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i=x;i<BIT.size();i=next(i))BIT[i]+=k;
      |                 ~^~~~~~~~~~~
examination.cpp: In function 'void MO(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
examination.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         if(min_av==av.size()){
      |            ~~~~~~^~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:159:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  159 |     for(int i=0;i<math.size();i++){
      |                 ~^~~~~~~~~~~~
examination.cpp:160:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  160 |         if(math[i].size()>=sz){
      |            ~~~~~~~~~~~~~~^~~~
examination.cpp:165:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  165 |         }else if(math[i].size()+cur>sz){
      |                  ~~~~~~~~~~~~~~~~~~^~~

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