Submission #1124795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124795		ducanh0811	Poklon (COCI17_poklon)	C++20	28 / 140	186 ms	22684 KiB

poklon

#include <bits/stdc++.h>
#define     debug(x)        cout << #x << " = " << x << '\n'
#define     int             long long
#define     pii             pair<int, int>
#define     fi              first
#define     se              second
#define     pb              push_back
#define     eb              emplace_back
#define     ALL(x)          x.begin(), x.end()
#define     MASK(i)         (1ll << (i))
#define     FOR(i,a,b)      for (int i = (a); i <= (b); ++i)
#define     REV(i,a,b)      for (int i = (a); i >= (b); --i)
using namespace std;

int n, q;
#define MAXN 500005
int a[MAXN];

struct query{
    int l,r,i;
};

int SIZE = 707;

vector<query> Q;

int bid(int id){
    return id / SIZE;
}

int res[MAXN];
int cnt[MAXN];

int ANS = 0;

void compress(){
    vector<int> nenso;
    FOR(i,0,n-1) nenso.pb(a[i]);
    sort(ALL(nenso));
    int cur = nenso[0];
    int cnt = 1;
    map<int,int>mp;
    for (int &x : nenso){
        if (cur != x) cur = x, cnt++;
        mp[cur] = cnt;
    }
    FOR(i,0,n-1) a[i] = mp[a[i]];
}

void inc(int x){
    if (cnt[x] == 2) ANS--;
    if (cnt[x] == 1) ANS++;
    cnt[x]++;
}

void dec(int x){
    if (cnt[x] == 2) ANS--;
    if (cnt[x] == 3) ANS++;
    cnt[x]--;
}

void solve(){
    cin >> n >> q;
    FOR(i,0,n-1) cin >> a[i];
    compress();
    FOR(i,1,q){
        int x,y; cin >> x >> y;
        x--; y--;
        Q.push_back({x,y,i});
    }
    sort(ALL(Q),[](const query&A, const query&B){
        if (bid(A.l) != bid(B.l)) return bid(A.l) < (B.l);
        return bid(A.l) & 1 ? A.r < B.r : A.r > B.r;
    });

    int ll = Q[0].l;
    int rr = Q[0].r;

    FOR(i,ll,rr){
        inc(a[i]);
    }

    res[Q[0].i] = ANS;

    FOR(i,1,q-1){
        while (ll > Q[i].l) ll--, inc(a[ll]);
        while (ll < Q[i].l) dec(a[ll]), ll++;
        while (rr > Q[i].r) dec(a[rr]), rr--;
        while (rr < Q[i].r) rr++, inc(a[rr]);
        res[Q[i].i] = ANS;
    }

    FOR(i,1,q){
        cout << res[i] << '\n';
    }

}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(__null); cout.tie(__null);
    solve();
    return 0;
}

• Subtask 1: 28 / 140