# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
246767 | NONAME | Poklon (COCI17_poklon) | C++14 | 453 ms | 26216 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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";
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |