Submission #246077

#	Time	Username	Problem	Language	Result	Execution time	Memory
246077		VEGAnn	Poklon (COCI17_poklon)	C++14	140 / 140	1556 ms	13416 KiB

poklon

#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const int oo = 2e9;
const int N = 500100;
const int md = 998244353;
const int PW = 233;
const int B = 700;
vector<int> vc;
int n, a[N], L[N], R[N], ans[N], nm[N], cnt[N], cur_ans, q;

bool cmp(int _x, int _y){
    if (L[_x] / B == L[_y] / B){
        if ((L[_x] / B) & 1)
            return R[_x] > R[_y];
        else return R[_x] < R[_y];
    } else return (L[_x] / B < L[_y] / B);
}

void add(int id){
    cnt[a[id]]++;

    if (cnt[a[id]] == 2)
        cur_ans++;

    if (cnt[a[id]] == 3)
        cur_ans--;
}

void del(int id){
    cnt[a[id]]--;

    if (cnt[a[id]] == 2)
        cur_ans++;

    if (cnt[a[id]] == 1)
        cur_ans--;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAl

    cin >> n >> q;

    for (int i = 0; i < n; i++){
        cin >> a[i];
        vc.PB(a[i]);
    }

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    for (int i = 0; i < n; i++)
        a[i] = lower_bound(all(vc), a[i]) - vc.begin();

    for (int i = 0; i < q; i++) {
        cin >> L[i] >> R[i];
        L[i]--; R[i]--;
        nm[i] = i;
    }

    sort(nm, nm + q, cmp);

    int l = 0, r = -1;

    cur_ans = 0;

    for (int it = 0; it < q; it++){
        int i = nm[it];

        while (l < L[i]) del(l++);
        while (r < R[i]) add(++r);
        while (l > L[i]) add(--l);
        while (r > R[i]) del(r--);

        ans[i] = cur_ans;
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';

    return 0;
}

• Subtask 1: 140 / 140