oj.uz

Submission #246640

# Submission time Handle Problem Language Result Execution time Memory
246640 2020-07-09T20:41:25 Z NONAME Poklon (COCI17_poklon) C++14
140 / 140
 981 ms 28392 KB 
#include  <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
using ld = long double;

const int N = 5e5 + 500;
const array <int, 3> ch = {0, 1, -1};

int n, m, a[N], t[4 * N], res[N];

void upd(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
        t[v] += val;
        return;
    }

    int md = (tl + tr) >> 1;

    if (pos <= md) upd(v + v, tl, md, pos, val);
        else upd(v + v + 1, md + 1, tr, pos, val);

    t[v] = t[v + v] + t[v + v + 1];
}

int sum(int v, int tl, int tr, int ql, int qr) {
    //cerr << v << " " << tl << " " << tr << " " << ql << " " << qr << " " << t[v] << "\n";
    if ((tl > tr) || (tl > qr) || (ql > tr))
        return 0;

    if ((tl >= ql) && (tr <= qr))
        return t[v];

    int md = (tl + tr) >> 1;

    return (sum(v + v, tl, md, ql, qr) + sum(v + v + 1, md + 1, tr, ql, qr));
}

int main() {
    fast_io;

    cin >> n >> m;
    vector <int> all;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        all.push_back(a[i]);
    }

    sort(all.begin(), all.end());
    all.resize(unique(all.begin(), all.end()) - all.begin());

    vector <int> ps[int(all.size())];
    vector <int> pt(int(all.size()), 0);

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

    vector <pair <pair <int, int>, int> > q(m);

    for (int i = 0; i < m; ++i) {
        cin >> q[i].first.first >> q[i].first.second;
        --q[i].first.first, --q[i].first.second;
        q[i].second = i;
    }

    sort(q.begin(), q.end());

    for (int i = 0; i < int(all.size()); ++i)
    for (int j = 0; j < min(3, int(ps[i].size())); ++j)
        upd(1, 0, n - 1, ps[i][j], ch[j]);

    int l = 0;

    for (int j = 0; j < m; ++j) {
        int L = q[j].first.first, R = q[j].first.second;
        while (l < L) {
            int x = lower_bound(all.begin(), all.end(), a[l]) - all.begin();

            for (int i = pt[x]; i < min(pt[x] + 3, int(ps[x].size())); ++i)
                upd(1, 0, n - 1, ps[x][i], -ch[i - pt[x]]);
            ++pt[x];
            for (int i = pt[x]; i < min(pt[x] + 3, int(ps[x].size())); ++i)
                upd(1, 0, n - 1, ps[x][i], ch[i - pt[x]]);

            ++l;
        }

        //dbg(L);
        //dbg(R);

        res[q[j].second] = sum(1, 0, n - 1, L, R);
    }

    for (int i = 0; i < m; ++i)
        cout << res[i] << "\n";
}

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 384 KB Output is correct
4 Correct 12 ms 640 KB Output is correct
5 Correct 168 ms 5892 KB Output is correct
6 Correct 166 ms 6000 KB Output is correct
7 Correct 376 ms 11888 KB Output is correct
8 Correct 580 ms 19508 KB Output is correct
9 Correct 781 ms 24168 KB Output is correct
10 Correct 981 ms 28392 KB Output is correct