#include<bits/stdc++.h>
using namespace std;
#define app push_back
#define ii pair <int, int>
#define mp make_pair
const int N = 1e6 + 7;
int mx[N << 2], add[N << 2];
void push(int v) {
if (add[v]) {
for (int i = v * 2 + 1; i <= v * 2 + 2; ++i) {
mx[i] += add[v]; add[i] += add[v];
}
add[v] = 0;
}
}
void relax(int v) {
mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
}
void upd(int v, int tl, int tr, int p, int x) {
if (tl == tr) {
mx[v] = x;
return;
}
int tm = (tl + tr) >> 1;
push(v);
if (p <= tm) upd(v * 2 + 1, tl, tm, p, x);
else upd(v * 2 + 2, tm + 1, tr, p, x);
relax(v);
}
void add_(int v, int tl, int tr, int l, int r, int x) {
if (tr < l || r < tl) return;
if (l <= tl && tr <= r) {
mx[v] += x; add[v] += x;
return;
}
int tm = (tl + tr) >> 1;
push(v);
add_(v * 2 + 1, tl, tm, l, r, x); add_(v * 2 + 2, tm + 1, tr, l, r, x);
relax(v);
}
int f[N];
void addf(int i, int x) {
for (; i < N; i |= i + 1) f[i] += x;
}
int get(int i) {
int ans = 0;
for (; i >= 0; i &= i + 1, --i) ans += f[i];
return ans;
}
vector <int> countScans(vector <int> a, vector <int> p, vector <int> x) {
for (auto &e : p) --e;
int n = a.size(), q = p.size();
vector <ii> v;
for (int i = 0; i < n; ++i) {
v.app({a[i], i});
}
for (int i = 0; i < q; ++i) {
v.app({x[i], p[i]});
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
for (int i = 0; i < n; ++i) {
a[i] = lower_bound(v.begin(), v.end(), mp(a[i], i)) - v.begin();
}
for (int i = 0; i < q; ++i) {
x[i] = lower_bound(v.begin(), v.end(), mp(x[i], p[i])) - v.begin();
}
for (int i = 0; i < (N << 2); ++i) mx[i] = -N;
vector <int> t;
for (int i = 0; i < n; ++i) {
t.app(a[i]);
}
sort(t.begin(), t.end()); t.resize(unique(t.begin(), t.end()) - t.begin());
for (int i = 0; i < n; ++i) {
int p = lower_bound(t.begin(), t.end(), a[i]) - t.begin();
upd(0, 0, N, a[i], i - p);
addf(a[i], 1);
}
vector <int> ans;
for (int i = 0; i < q; ++i) {
if (a[i] < x[i]) {
//cout << "add " << min(a[i], x[i]) + 1 << ' ' << max(a[i], x[i]) - 1 << ' ' << -1 << '\n';
add_(0, 0, N, min(a[i], x[i]) + 1, max(a[i], x[i]) - 1, -1);
}
else {
//cout << "add " << min(a[i], x[i]) + 1 << ' ' << max(a[i], x[i]) - 1 << ' ' << 1 << '\n';
add_(0, 0, N, min(a[i], x[i]) + 1, max(a[i], x[i]) - 1, 1);
}
upd(0, 0, N, a[i], -N);
addf(a[i], -1);
int pp = get(x[i]);
upd(0, 0, N, pp, p[i] - pp);
addf(x[i], 1);
a[i] = x[i];
ans.app(mx[0]);
}
return ans;
}
#ifdef HOME
signed main() {
freopen("input.txt", "r", stdin);
int n, q;
cin >> n >> q;
vector <int> a(n), p(q), x(q);
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < q; ++i) cin >> p[i] >> x[i];
vector <int> ans = countScans(a, p, x);
for (int e : ans) cout << e << '\n';
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
32504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
32504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
17160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
40 ms |
32504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
