Submission #40909

# Submission time Handle Problem Language Result Execution time Memory
40909 2018-02-09T23:00:02 Z Hassoony Poklon (COCI17_poklon) C++14
0 / 140
365 ms 16616 KB
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef double D;
const ll inf=(1ll<<61);
const int mod=1e9+7;
const int MX=1e6+9;
const int SQ=250;
int n,q,a[MX],ans,res[MX];
pair<int,pair<int,int> >Q[MX];
unordered_map<int,int>cnt;
bool cmp(pair<int,pair<int,int> >A,pair<int,pair<int,int> >B){
    if((A.first/SQ)==(B.first/SQ)){
        return A.second.first<B.second.first;
    }
    return (A.first/SQ)<(B.first/SQ);
}
void add(int x){
    ans-=(cnt[x]==2);
    cnt[x]++;
    ans+=(cnt[x]==2);
}
void rem(int x){
    ans-=(cnt[x]==2);
    cnt[x]--;
    ans+=(cnt[x]==2);
}
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<q;i++){
        scanf("%d%d",&Q[i].first,&Q[i].second.first);
        Q[i].second.second=i;
    }
    sort(Q,Q+q,cmp);
    int mol=1,mor=0;
    for(int i=0;i<q;i++){
        int L=Q[i].first,R=Q[i].second.first;
        while(mor<R){
            add(a[++mor]);
        }
        while(mor>R){
            rem(a[mor++]);
        }
        while(mol<L){
            rem(a[mol++]);
        }
        while(mol>L){
            add(a[++mol]);
        }
     //   cout<<L<<" "<<R<<" "<<Q[i].second.second<<endl;
        res[Q[i].second.second]=ans;
    }
    for(int i=0;i<q;i++)printf("%d\n",res[i]);
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:32:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
                          ^
poklon.cpp:35:53: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&Q[i].first,&Q[i].second.first);
                                                     ^
# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 488 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 55 ms 680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 55 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 56 ms 884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 114 ms 3956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 122 ms 4024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 208 ms 7192 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 249 ms 10432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 335 ms 13452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 365 ms 16616 KB Execution killed with signal 11 (could be triggered by violating memory limits)