oj.uz

Submission #969888

# Submission time Handle Problem Language Result Execution time Memory
969888 2024-04-25T18:30:21 Z RandomUser Poklon (COCI17_poklon) C++17
84 / 140
 5000 ms 18516 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;

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 21 ms 604 KB Output is correct
5 Correct 1769 ms 3968 KB Output is correct
6 Correct 2207 ms 3848 KB Output is correct
7 Execution timed out 5011 ms 7508 KB Time limit exceeded
8 Execution timed out 5044 ms 11212 KB Time limit exceeded
9 Execution timed out 5043 ms 15004 KB Time limit exceeded
10 Execution timed out 5018 ms 18516 KB Time limit exceeded