oj.uz

Submission #246767

# Submission time Handle Problem Language Result Execution time Memory
246767 2020-07-10T07:13:20 Z NONAME Poklon (COCI17_poklon) C++14
140 / 140
 453 ms 26216 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], fen[N], res[N];

void upd(int x, int vl) { while (x < n) fen[x] += vl, x = (x | (x + 1)); }

int sum(int x) { int k = 0; while (x >= 0) k += fen[x], x = (x & (x + 1)) - 1; return k; }

int sum(int l, int r) { return sum(r) - sum(l - 1); }

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(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(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(ps[x][i], ch[i - pt[x]]);

            ++l;
        }

        res[q[j].second] = sum(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 6 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 8 ms 640 KB Output is correct
5 Correct 82 ms 5236 KB Output is correct
6 Correct 81 ms 5360 KB Output is correct
7 Correct 172 ms 10664 KB Output is correct
8 Correct 284 ms 16488 KB Output is correct
9 Correct 352 ms 21568 KB Output is correct
10 Correct 453 ms 26216 KB Output is correct