#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1e6 + 5;
int maxn[MAXN * 4 + 10], lazy[MAXN * 4 + 10];
void pushup(int rt) { maxn[rt] = max(maxn[rt << 1], maxn[rt << 1 | 1]); }
void pushdown(int rt) {
if (lazy[rt] != -1e7) {
maxn[rt << 1] += lazy[rt], maxn[rt << 1 | 1] += lazy[rt];
lazy[rt << 1] += lazy[rt], lazy[rt << 1 | 1] += lazy[rt];
lazy[rt] = -1e7;
}
}
void update(int L, int R, int I, int l = 1, int r = MAXN, int rt = 1) {
if (L <= l && r <= R) {
maxn[rt] += I, lazy[rt] += I;
return;
}
int m = (l + r) / 2;
pushdown(rt);
if (L <= m)
update(L, R, I, l, m, rt << 1);
if (R > m)
update(L, R, I, m + 1, r, rt << 1 | 1);
pushup(rt);
}
int query(int L, int R, int l = 1, int r = MAXN, int rt = 1) {
if (L <= l && r <= R)
return maxn[rt];
int m = (l + r) / 2, ans = -1e9;
if (L <= m)
ans = max(ans, query(L, R, l, m, rt << 1));
if (R > m)
ans = max(ans, query(L, R, m + 1, r, rt << 1 | 1));
return ans;
}
void p_update(int x, int I, int len = MAXN) {
int v = query(x, x, 1, len, 1);
update(x, x, I - v, 1, len, 1);
}
int pool[MAXN], tot;
struct BIT {
int t[MAXN + 5];
void update(int x, int I) {
while (x <= MAXN)
t[x] += I, x += x & -x;
}
int query(int x) {
int ans = 0;
while (x)
ans += t[x], x -= x & -x;
return ans;
}
} T;
void compress(int &x) { x = lower_bound(pool + 1, pool + tot + 1, x) - pool; }
std::vector<int> countScans(std::vector<int> A, std::vector<int> X,
std::vector<int> V) {
int Q = X.size(), N = A.size();
for (int i = 0; i < N; i++)
A[i] *= 2;
for (int i = 0; i < Q; i++)
V[i] *= 2;
std::vector<int> answer(Q);
for (int i = 0; i < N; i++)
A[i] += i, pool[++tot] = A[i];
for (int i = 0; i < Q; i++)
V[i] += X[i], pool[++tot] = V[i];
sort(pool + 1, pool + tot + 1);
tot = unique(pool + 1, pool + tot + 1) - pool - 1;
for (int i = 0; i < N; i++)
compress(A[i]), T.update(A[i], 1);
for (int i = 0; i < Q; i++)
compress(V[i]);
for (int i = 0; i < 4 * MAXN + 5; i++)
maxn[i] = lazy[i] = -1e7;
for (int i = 0; i < N; i++) {
p_update(A[i], i - T.query(A[i] - 1));
// cerr<<"ID"<<A[i]<<"EXPECTED"<<i - T.query(A[i] - 1)<<endl;
}
// cerr << "Compressed Results:" << endl;
// for (int i = 0; i < N; i++)
// cerr << A[i] << " \n"[i == N - 1];
// for (int i = 0; i < Q; i++)
// cerr << X[i] << " " << V[i] << endl;
for (int i = 0; i < Q; i++) {
int src = A[X[i]];
// cerr << "SGT:" << endl;
// for (int i = 1; i <= 6; i++)
// cerr << query(i, i) << " \n"[i == 6];
if (src == V[i]) {
answer[i] = query(1, MAXN);
continue;
}
T.update(src, -1);
T.update(V[i], 1);
p_update(src, -1e7);
p_update(V[i], X[i] - T.query(V[i] - 1));
if (src < V[i]) {
if (src + 1 <= V[i] - 1)
update(src + 1, V[i] - 1, 1);
} else {
if (V[i] + 1 <= src - 1)
update(V[i] + 1, src - 1, -1);
}
A[X[i]] = V[i];
answer[i] = query(1, MAXN);
}
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
31572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
31572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
32076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
31572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
