oj.uz

Submission #616121

# Submission time Handle Problem Language Result Execution time Memory
616121 2022-07-31T22:21:41 Z Iwanttobreakfree Examination (JOI19_examination) C++
2 / 100
 3000 ms 31632 KB 
#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,ans=0;
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;
    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,int q){
    //cout<<i<<' ';
    for(int x:g[i]){
        cnt[x]++;
        if(cnt[x]==2){
            if(q<3001)pupd(mp_a[exam[x]]+1,+1);
            ans++;
        }
    }
    //cout<<ans<<' '<<'\n';
}
void del(int i,vector<vector<int>>& g,vector<int>& exam,int q){
    //cout<<i<<' ';
    for(int x:g[i]){
        if(cnt[x]==2){
            if(q<3001)pupd(mp_a[exam[x]]+1,-1);
            ans--;
        }
        cnt[x]--;
    }
    //cout<<ans<<'\n';
}
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<int,pair<pii,pii>>> qu(q);
    vector<int> answer(q);
    for(int i=0;i<q;i++){
        cin>>x>>y>>z;
        //cout<<x<<' '<<y<<' '<<z<<'\n';
        qu[i]={x/sz,{{x,y},{z,i}}};
    }
    sort(qu.begin(),qu.end(),cmp);
    int l_math=m.size(),l_info=in.size();
    m.push_back(1e9+7);
    in.push_back(1e9+7);
    for(int i=0;i<q;i++){
        int min_math=qu[i].second.first.first,min_info=qu[i].second.first.second,min_av;
        if(q<3001)min_av=bin_find(qu[i].second.second.first,av);
        else min_av=0;
        //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>0&&m[l_math]>min_math){
            l_math--;
            add(l_math,math,exam,q);
        }
        while(l_math+1<m.size()&&m[l_math]<min_math){
            del(l_math,math,exam,q);
            l_math++;
        }
        //cout<<l_math<<' '<<l_info<<'\n';
        while(l_info>0&&in[l_info]>min_info){
            l_info--;
            //cout<<l_info<<' ';
            add(l_info,info,exam,q);
        }
        //cout<<l_info<<' ';
        while(l_info+1<in.size()&&in[l_info]<min_info){
            del(l_info,info,exam,q);
            l_info++;
        }
        //cout<<l_math<<' '<<l_info<<' '<<qu[i].second.second<<' '<<ans<<' '<<sum(min_av)<<'\n';
        answer[qu[i].second.second.second]=ans-sum(min_av);
    }
    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 n,q,x,y;
    cin>>n>>q;
    sz=sqrt(n);
    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

examination.cpp: In function 'void pupd(int, int)':
examination.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     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:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         if(min_av==av.size()){
      |            ~~~~~~^~~~~~~~~~~
examination.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         while(l_math+1<m.size()&&m[l_math]<min_math){
      |               ~~~~~~~~^~~~~~~~~
examination.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         while(l_info+1<in.size()&&in[l_info]<min_info){
      |               ~~~~~~~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 2 ms 3540 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3540 KB Output is correct
7 Correct 125 ms 4732 KB Output is correct
8 Correct 124 ms 4736 KB Output is correct
9 Correct 129 ms 4736 KB Output is correct
10 Correct 76 ms 4360 KB Output is correct
11 Correct 74 ms 4308 KB Output is correct
12 Correct 48 ms 3708 KB Output is correct
13 Correct 124 ms 4744 KB Output is correct
14 Correct 124 ms 4732 KB Output is correct
15 Correct 126 ms 4748 KB Output is correct
16 Correct 210 ms 4336 KB Output is correct
17 Correct 207 ms 4332 KB Output is correct
18 Correct 49 ms 3668 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1914 ms 31600 KB Output is correct
2 Correct 1720 ms 31604 KB Output is correct
3 Correct 1775 ms 31632 KB Output is correct
4 Correct 575 ms 22652 KB Output is correct
5 Execution timed out 3070 ms 22056 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1914 ms 31600 KB Output is correct
2 Correct 1720 ms 31604 KB Output is correct
3 Correct 1775 ms 31632 KB Output is correct
4 Correct 575 ms 22652 KB Output is correct
5 Execution timed out 3070 ms 22056 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3540 KB Output is correct
2 Correct 2 ms 3540 KB Output is correct
3 Correct 3 ms 3412 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3540 KB Output is correct
7 Correct 125 ms 4732 KB Output is correct
8 Correct 124 ms 4736 KB Output is correct
9 Correct 129 ms 4736 KB Output is correct
10 Correct 76 ms 4360 KB Output is correct
11 Correct 74 ms 4308 KB Output is correct
12 Correct 48 ms 3708 KB Output is correct
13 Correct 124 ms 4744 KB Output is correct
14 Correct 124 ms 4732 KB Output is correct
15 Correct 126 ms 4748 KB Output is correct
16 Correct 210 ms 4336 KB Output is correct
17 Correct 207 ms 4332 KB Output is correct
18 Correct 49 ms 3668 KB Output is correct
19 Correct 1914 ms 31600 KB Output is correct
20 Correct 1720 ms 31604 KB Output is correct
21 Correct 1775 ms 31632 KB Output is correct
22 Correct 575 ms 22652 KB Output is correct
23 Execution timed out 3070 ms 22056 KB Time limit exceeded
24 Halted 0 ms 0 KB -