oj.uz

Submission #951250

# Submission time Handle Problem Language Result Execution time Memory
951250 2024-03-21T13:43:33 Z Beerus13 Poklon (COCI17_poklon) C++14
140 / 140
 758 ms 24976 KB 
#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

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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 5 ms 4664 KB Output is correct
5 Correct 80 ms 8292 KB Output is correct
6 Correct 76 ms 8012 KB Output is correct
7 Correct 199 ms 12412 KB Output is correct
8 Correct 386 ms 18744 KB Output is correct
9 Correct 539 ms 21192 KB Output is correct
10 Correct 758 ms 24976 KB Output is correct