oj.uz

Submission #246077

# Submission time Handle Problem Language Result Execution time Memory
246077 2020-07-08T06:55:11 Z VEGAnn Poklon (COCI17_poklon) C++14
140 / 140
 1556 ms 13416 KB 
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const int oo = 2e9;
const int N = 500100;
const int md = 998244353;
const int PW = 233;
const int B = 700;
vector<int> vc;
int n, a[N], L[N], R[N], ans[N], nm[N], cnt[N], cur_ans, q;

bool cmp(int _x, int _y){
    if (L[_x] / B == L[_y] / B){
        if ((L[_x] / B) & 1)
            return R[_x] > R[_y];
        else return R[_x] < R[_y];
    } else return (L[_x] / B < L[_y] / B);
}

void add(int id){
    cnt[a[id]]++;

    if (cnt[a[id]] == 2)
        cur_ans++;

    if (cnt[a[id]] == 3)
        cur_ans--;
}

void del(int id){
    cnt[a[id]]--;

    if (cnt[a[id]] == 2)
        cur_ans++;

    if (cnt[a[id]] == 1)
        cur_ans--;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAl

    cin >> n >> q;

    for (int i = 0; i < n; i++){
        cin >> a[i];
        vc.PB(a[i]);
    }

    sort(all(vc));
    vc.resize(unique(all(vc)) - vc.begin());

    for (int i = 0; i < n; i++)
        a[i] = lower_bound(all(vc), a[i]) - vc.begin();

    for (int i = 0; i < q; i++) {
        cin >> L[i] >> R[i];
        L[i]--; R[i]--;
        nm[i] = i;
    }

    sort(nm, nm + q, cmp);

    int l = 0, r = -1;

    cur_ans = 0;

    for (int it = 0; it < q; it++){
        int i = nm[it];

        while (l < L[i]) del(l++);
        while (r < R[i]) add(++r);
        while (l > L[i]) add(--l);
        while (r > R[i]) del(r--);

        ans[i] = cur_ans;
    }

    for (int i = 0; i < q; i++)
        cout << ans[i] << '\n';

    return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 256 KB Output is correct
4 Correct 12 ms 640 KB Output is correct
5 Correct 183 ms 3444 KB Output is correct
6 Correct 199 ms 3696 KB Output is correct
7 Correct 426 ms 6060 KB Output is correct
8 Correct 727 ms 8708 KB Output is correct
9 Correct 1108 ms 10700 KB Output is correct
10 Correct 1556 ms 13416 KB Output is correct