답안 #332444

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
332444 2020-12-02T15:42:36 Z guka415 Poklon (COCI17_poklon) C++14
140 / 140
1506 ms 13292 KB
#define fast ios::sync_with_stdio(false); cin.tie(0);
#define foru(i, k, n) for (int i = k; i < n; i++)
#define ford(i, k, n) for (int i = k; i >= n; i--)
#define pb push_back

#include <iostream>
#include <algorithm>
#include <math.h>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<pii, int> query;

const int sz = 1e6;
int a[sz], cnts[sz];
int n, q;
int B;
query qu[sz];
int ans[sz];
unordered_map<int, int> inv;

void compress() {
    int cur=0;
    foru(i,0,n){
        if(inv.find(a[i])!=inv.end())a[i]=inv[a[i]];
        else {
            inv[a[i]]=cur++;
            a[i]=cur-1;
        }
    }
}


bool cmp(const query &l, const query &r) {
    if (l.first.first / B != r.first.first / B)return l.first.first < r.first.first;
    else if (l.first.second != r.first.second)return l.first.second < r.first.second;
    else if (l.first.first != r.first.first)return l.first.first < r.first.first;
    else return l.second < r.second;
}


int main() {
    fast;
    cin >> n>>q;
    foru(i, 0, n)cin >> a[i];
    foru(i, 0, q) {
        cin >> qu[i].first.first >> qu[i].first.second;
        qu[i].first.first--;
        qu[i].first.second--;
        qu[i].second = i;
    }
    compress();
    B = (int)((ld)n / sqrtl(q));
    sort(qu, qu + q, cmp);
    int prv = -1, l = -1,r=-1,ret=0;
    foru(i,0,q){
        int block = qu[i].first.first/B;
        if(block!=prv){
            ret=0;
            foru(j,0,n)cnts[j]=0;
            l=qu[i].first.first,r=qu[i].first.second;
            foru(j,l,r+1){
                cnts[a[j]]++;
                if(cnts[a[j]]==2)ret++;
                if(cnts[a[j]]==3)ret--;
            }
        }
        else {
            while(l>qu[i].first.first){
                cnts[a[--l]]++;
                if(cnts[a[l]]==2)ret++;
                if(cnts[a[l]]==3)ret--;
            }
            while(l<qu[i].first.first){
                cnts[a[l++]]--;
                if(cnts[a[l-1]]==1)ret--;
                if(cnts[a[l-1]]==2)ret++;
            }
            while(r<qu[i].first.second){
                cnts[a[++r]]++;
                if(cnts[a[r]]==2)ret++;
                if(cnts[a[r]]==3)ret--;
            }
        }
        ans[qu[i].second]=ret;
        prv=block;
    }
    foru(i,0,q)cout<<ans[i]<<'\n';
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 5 ms 492 KB Output is correct
5 Correct 166 ms 2924 KB Output is correct
6 Correct 165 ms 2924 KB Output is correct
7 Correct 455 ms 5612 KB Output is correct
8 Correct 751 ms 8172 KB Output is correct
9 Correct 1121 ms 10816 KB Output is correct
10 Correct 1506 ms 13292 KB Output is correct