Submission #892079

#	Time	Username	Problem	Language	Result	Execution time	Memory
892079		kh0i	Poklon (COCI17_poklon)	C++17	140 / 140	765 ms	23664 KiB

poklon

/**
 *	author: kh0i
 *	created: 16.06.2022 18:23:56
**/
#include "bits/stdc++.h"
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;

struct Query{
    int l, r, id;
};

const int N = 5e5 + 5;
int n, q, a[N], b[N], ans[N], cnt[N];
Query d[N];
map<int, int> mp;

void add(int x, int &sum, int op){
    if(cnt[x] == 2){
        --sum;
    }
    cnt[x] += op;
    if(cnt[x] == 2){
        ++sum;
    }
}

void solve(){
    cin >> n >> q;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    int cur = 0;
    for(int i = 1; i <= n; ++i){
        if(!mp.count(b[i])){
            mp[b[i]] = ++cur;
        }
    }
    for(int i = 1; i <= n; ++i){
        a[i] = mp[a[i]];
    }
    for(int i = 1; i <= q; ++i){
        cin >> d[i].l >> d[i].r;
        d[i].id = i;
    }
    int root = sqrt(n);
    sort(d + 1, d + q + 1, [root](Query f, Query s){
                return f.l / root != s.l / root ? f.l / root < s.l / root : f.r > s.r;
            });
    int l = 1, r = 1, sum = 0, ql, qr, id;
    cnt[a[1]] = 1;
    for(int i = 1; i <= q; ++i){
        ql = d[i].l, qr = d[i].r, id = d[i].id;
        while(r < qr) add(a[++r], sum, 1);
        while(r > qr) add(a[r--], sum, -1);
        while(l < ql) add(a[l++], sum, -1);
        while(l > ql) add(a[--l], sum, 1);
        ans[id] = sum;
    }
    for(int i = 1; i <= q; ++i){
        cout << ans[i] << '\n';
    }
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    int test = 1;
//    cin >> test;
    for(int i = 1; i <= test; ++i){
        solve();
    }
    cerr << "\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
    return 0;
}

• Subtask 1: 140 / 140