#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 10 + 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]) {
maxn[rt << 1] += lazy[rt], maxn[rt << 1 | 1] += lazy[rt];
lazy[rt << 1] += lazy[rt], lazy[rt << 1 | 1] += lazy[rt];
lazy[rt] = 0;
}
}
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, placed = 0;
pushdown(rt);
if (L <= m) {
ans = query(L, R, l, m, rt << 1);
placed = 1;
}
if (R > m) {
if(placed) ans = max(ans, query(L, R, m + 1, r, rt << 1 | 1));
else 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);
update(x, x, I - v);
}
typedef pair<int, int> pr;
#define mp make_pair
pr pool[MAXN];
int tot;
struct BIT {
int t[MAXN + 20];
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, int id) {
x = lower_bound(pool + 1, pool + tot + 1, mp(x, id)) - pool;
}
std::vector<int> countScans(std::vector<int> A, std::vector<int> X,
std::vector<int> V) {
int Q = X.size(), N = A.size();
std::vector<int> answer(Q);
for (int i = 0; i < N; i++)
pool[++tot] = mp(A[i], i);
for (int i = 0; i < Q; i++)
pool[++tot] = mp(V[i], X[i]);
sort(pool + 1, pool + tot + 1);
tot = unique(pool + 1, pool + tot + 1) - pool - 1;
// for (i = 1; i <= tot; i++) {
// printf("%d %d\n",pool[i].first,pool[i].second);
// }
for (int i = 0; i < N; i++)
compress(A[i], i), T.update(A[i], 1);
for (int i = 0; i < Q; i++)
compress(V[i], X[i]);
for (int i = 0; i < 4 * MAXN + 10; i++)
maxn[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 - before:" << endl;
// for (int i = 1; i <= 7; i++)
// cerr << query(i, i) << " \n"[i == 7];
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 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
916 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
