Submission #969888

#	Time	Username	Problem	Language	Result	Execution time	Memory
969888		RandomUser	Poklon (COCI17_poklon)	C++17	84 / 140	5044 ms	18516 KiB

poklon

#include <bits/stdc++.h>

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

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

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

    int n, q;
    cin >> n >> q;
    int B = sqrt(n);

    vector<int> v(n);
    for(int &x : v) cin >> x;

    vector<Query> qus(q);
    for(int i=0; i<q; i++) {
        cin >> qus[i].l >> qus[i].r;
        qus[i].id = i;
        qus[i].l--, qus[i].r--;
    }

    sort(all(qus), [&](Query &q1, Query &q2) {
        int a = q1.l / B;
        int b = q2.l / B;
        if(a == b) return q1.r < q2.r;
        return a < b; 
    });

    vector<int> ans(q);
    int res = 0;
    map<int, int> cnt;
    int l=0, r=-1;

    for(Query &q : qus) {
        while(r < q.r) {
            r++;
            cnt[v[r]]++;
            if(cnt[v[r]] == 2) res++;
            else if(cnt[v[r]] == 3) res--;
        }

        while(r > q.r) {
            cnt[v[r]]--;
            if(cnt[v[r]] == 1) res--;
            else if(cnt[v[r]] == 2) res++;
            r--;
        }

        while(l > q.l) {
            l--;
            cnt[v[l]]++;
            if(cnt[v[l]] == 2) res++;
            else if(cnt[v[l]] == 3) res--;
        }

        while(l < q.l) {
            cnt[v[l]]--;
            if(cnt[v[l]] == 1) res--;
            else if(cnt[v[l]] == 2) res++;
            l++;
        }

        ans[q.id] = res;
    }

    for(int &x : ans) cout << x << '\n';
    return 0;
}

• Subtask 1: 84 / 140