oj.uz

답안 #40913

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40913 2018-02-09T23:05:35 Z Hassoony Poklon (COCI17_poklon) C++14
84 / 140
 5000 ms 10428 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=300;
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]);
        }
     //   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);
                                                     ^

Subtask #1
84.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 4 ms 352 KB Output is correct
3 Correct 6 ms 576 KB Output is correct
4 Correct 32 ms 580 KB Output is correct
5 Correct 2115 ms 2696 KB Output is correct
6 Correct 2110 ms 2696 KB Output is correct
7 Execution timed out 5051 ms 4540 KB Time limit exceeded
8 Execution timed out 5060 ms 6712 KB Time limit exceeded
9 Execution timed out 5050 ms 8528 KB Time limit exceeded
10 Execution timed out 5077 ms 10428 KB Time limit exceeded