# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
40933 | 2018-02-09T23:19:50 Z | Hassoony | Poklon (COCI17_poklon) | C++14 | 5000 ms | 10296 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=5e5+9; const int SQ=740; int n,q,ans,res[MX],a[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]); } res[Q[i].second.second]=ans; } for(int i=0;i<q;i++)printf("%d\n",res[i]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 248 KB | Output is correct |
2 | Correct | 4 ms | 352 KB | Output is correct |
3 | Correct | 10 ms | 532 KB | Output is correct |
4 | Correct | 59 ms | 652 KB | Output is correct |
5 | Correct | 1813 ms | 2764 KB | Output is correct |
6 | Correct | 1847 ms | 2764 KB | Output is correct |
7 | Execution timed out | 5001 ms | 4928 KB | Time limit exceeded |
8 | Execution timed out | 5033 ms | 6432 KB | Time limit exceeded |
9 | Execution timed out | 5073 ms | 8484 KB | Time limit exceeded |
10 | Execution timed out | 5082 ms | 10296 KB | Time limit exceeded |