Submission #1182755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182755		nguyenkhangninh99	Poklon (COCI17_poklon)	C++20	140 / 140	776 ms	13336 KiB

poklon

#include <bits/stdc++.h>
using namespace std;

#define all(a) begin(a), end(a)

const int N = 5e5 + 1, BLOCK = 800;

struct Query {
    int l, r, i;

    bool operator<(const Query& rhs) const {
        if(l / BLOCK != rhs.l / BLOCK) return l < rhs.l;
        return (l / BLOCK & 1) ? (r < rhs.r) : (r > rhs.r);
    }
} quer[N];

int a[N], cnt[N], cnt1[N], res[N];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, q; cin >> n >> q;
    vector<int> compress;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        compress.push_back(a[i]);
    }
    sort(all(compress));
    compress.erase(unique(all(compress)), end(compress));
    for(int i = 1; i <= n; ++i) a[i] = upper_bound(all(compress), a[i]) - begin(compress);
    for(int i = 1; i <= q; ++i) {
        cin >> quer[i].l >> quer[i].r;
        quer[i].i = i;
    }
    sort(quer + 1, quer + q + 1);
    int cur_l = 0, cur_r = -1;
    for(int i = 1; i <= q; ++i) {
        while(cur_l > quer[i].l) {
            --cur_l;
            --cnt1[cnt[a[cur_l]]];
            ++cnt1[++cnt[a[cur_l]]];
        }
        while(cur_r < quer[i].r) {
            ++cur_r;
            --cnt1[cnt[a[cur_r]]];
            ++cnt1[++cnt[a[cur_r]]];
        }
        while(cur_l < quer[i].l) {
            --cnt1[cnt[a[cur_l]]];
            ++cnt1[--cnt[a[cur_l]]];
            ++cur_l;
        }
        while(cur_r > quer[i].r) {
            --cnt1[cnt[a[cur_r]]];
            ++cnt1[--cnt[a[cur_r]]];
            --cur_r;
        }
        res[quer[i].i] = cnt1[2];
    }
    for(int i = 1; i <= q; ++i) cout << res[i] << endl;
}

• Subtask 1: 140 / 140