oj.uz

Submission #969890

# Submission time Handle Problem Language Result Execution time Memory
969890 2024-04-25T18:32:04 Z RandomUser Poklon (COCI17_poklon) C++17
140 / 140
 1027 ms 12996 KB 
#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;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

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);
    set<int> s;
    for(int &x : v) cin >> x, s.insert(x);

    vector<int> comp(all(s));
    for(int &x : v) x = lower_bound(all(comp), x) - comp.begin();

    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;
    vector<int> cnt(n+1);
    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
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 115 ms 2800 KB Output is correct
6 Correct 121 ms 2896 KB Output is correct
7 Correct 292 ms 5428 KB Output is correct
8 Correct 513 ms 8072 KB Output is correct
9 Correct 726 ms 10848 KB Output is correct
10 Correct 1027 ms 12996 KB Output is correct