Submission #951250

#	Time	Username	Problem	Language	Result	Execution time	Memory
951250		Beerus13	Poklon (COCI17_poklon)	C++14	140 / 140	758 ms	24976 KiB

poklon

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(), v.end()
const int N = 5e5 + 5;
const int sqr = 500;

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

int n, q, a[N], ans[N], cnt[N], res;
vector<int> num;
vector<query> qrs;

bool cmp(query a, query b) {
    if(a.l / sqr != b.l / sqr) return a.l / sqr < b.l / sqr;
    return a.r < b.r;
}

void add(int val) {
    cnt[val]++;
    if(cnt[val] == 2) ++res;
    if(cnt[val] == 3) --res;
}

void del(int val) {
    cnt[val]--;
    if(cnt[val] == 2) ++res;
    if(cnt[val] == 1) --res;
}

void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
        num.push_back(a[i]);
    }
    sort(all(num));
    num.resize(unique(all(num)) - num.begin());
    for(int i = 1; i <= n; ++i) {
        a[i] = lower_bound(all(num), a[i]) - num.begin() + 1;
    }
    for(int i = 1, l, r; i <= q; ++i) {
        cin >> l >> r;
        qrs.push_back({l, r, i});
    }
    sort(all(qrs), cmp);
    int l = 1, r = 0;
    for(auto [ql, qr, i] : qrs) {
        while(l > ql) add(a[--l]);
        while(l < ql) del(a[l++]);
        while(r < qr) add(a[++r]);
        while(r > qr) del(a[r--]);
        ans[i] = res;
    }
    for(int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    return 0;
}

Compilation message (stderr)

poklon.cpp: In function 'void solve()':
poklon.cpp:50:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |     for(auto [ql, qr, i] : qrs) {
      |              ^

• Subtask 1: 140 / 140