oj.uz

Submission #988580

# Submission time Handle Problem Language Result Execution time Memory
988580 2024-05-25T08:02:51 Z erering Poklon (COCI17_poklon) C++17
140 / 140
 1426 ms 69368 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define inf 2e18
#define endl '\n'
const int N=5e5+2,MAXN=1e6+2;
int n,q,a[N],offset=1;
int seg[N*4];
void update(int idx,int val){
    idx+=offset;
    seg[idx]=val;
    idx/=2;
    while(idx>0){
        seg[idx]=seg[idx*2]+seg[idx*2+1];
        idx/=2;
    }
}
int query(int node,int qlo,int qhi,int lo,int hi){
    if(lo>=qlo && hi<=qhi)return seg[node];
    if(lo>qhi || hi<qlo)return 0;
    int mid=(lo+hi)/2;
    return query(node*2,qlo,qhi,lo,mid)+query(node*2+1,qlo,qhi,mid+1,hi);
}
signed main(){
    //srand(time(NULL))
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,q; cin>>n>>q;
    while(offset<n)offset*=2;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<pair<int,int>> vec,og;
    while(q--){
        int l,r; cin>>l>>r;
        vec.pb({r,l});
        og.pb({l,r});
    }
    sort(vec.begin(),vec.end());
    map<int,vector<int>> mp;
    map<pair<int,int>,int> ans;
    int idx=0;
    for(int i=0;i<n;i++){
        vector<int> v=mp[a[i]];
        if(v.size()==0)mp[a[i]].pb(i);
        else if(v.size()==1){
            update(v[0],1);
            mp[a[i]].pb(i);
        }
        else if(v.size()==2){
            update(v[0],-1);
            update(v[1],1);
            mp[a[i]].pb(i);
        }
        else{
            update(v[0],0);
            update(v[1],-1);
            update(v[2],1);
            mp[a[i]].clear();
            mp[a[i]].pb(v[1]);
            mp[a[i]].pb(v[2]);
            mp[a[i]].pb(i);
        }
        while(idx!=q && vec[idx].first==i+1){
            ans[{vec[idx].second,vec[idx].first}]=query(1,vec[idx].second-1,vec[idx].first-1,0,offset-1);
            idx++;
        }
    }
    for(int i=0;i<og.size();i++){
        cout<<ans[{og[i].first,og[i].second}]<<endl;
    }
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:69:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for(int i=0;i<og.size();i++){
      |                 ~^~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2536 KB Output is correct
3 Correct 2 ms 2396 KB Output is correct
4 Correct 6 ms 3084 KB Output is correct
5 Correct 121 ms 14096 KB Output is correct
6 Correct 130 ms 14252 KB Output is correct
7 Correct 346 ms 30288 KB Output is correct
8 Correct 622 ms 45604 KB Output is correct
9 Correct 919 ms 56716 KB Output is correct
10 Correct 1426 ms 69368 KB Output is correct