#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
using Arr = array<int, 3>;
const int N = 500500;
const int inf = 1e9;
int lz[N << 3];
int cnt[N << 3];
int val[N << 3];
void push(int v,int l,int r) {
if (lz[v]) {
val[v] += lz[v];
if (l < r) {
lz[v << 1] += lz[v];
lz[v << 1 | 1] += lz[v];
}
lz[v] = 0;
}
}
void upd(int v,int l,int r,int p,int x,int y) {
push(v, l, r);
if (p > r || p < l) return;
if (l == r) {
val[v] = x;
cnt[v] = y;
return;
}
int md = (l + r) >> 1;
upd(v << 1, l, md, p, x, y);
upd(v << 1 | 1, md + 1, r, p, x, y);
val[v] = max(val[v << 1], val[v << 1 | 1]);
cnt[v] = cnt[v << 1] + cnt[v << 1 | 1];
}
void add(int v,int l,int r,int L,int R,int x) {
push(v, l, r);
if (L > r || R < l) return;
if (L <= l && r <= R) {
lz[v] = x;
push(v, l, r);
return;
}
int md = (l + r) >> 1;
add(v << 1, l, md, L, R, x);
add(v << 1 | 1, md + 1, r, L, R, x);
val[v] = max(val[v << 1], val[v << 1 | 1]);
}
int get(int v,int l,int r,int L,int R) {
push(v, l, r);
if (L > r || R < l) return 0;
if (L <= l && r <= R) return cnt[v];
int md = (l + r) >> 1;
return get(v << 1, l, md, L, R) + get(v << 1 | 1, md + 1, r, L, R);
}
int now[N], pos[N];
vector<int> countScans(vector<int> a, vector<int> x, vector<int> y) {
int n = a.size(), q = x.size();
vector<Arr> vals;
for (int i = 0; i < n; ++i) {
vals.push_back({a[i], i, i});
}
for (int i = 0; i < q; ++i) {
vals.push_back({y[i], x[i], i + n});
}
sort(vals.begin(), vals.end());
int sz = n + q;
memset(val, -69, sizeof val);
for (int i = 0; i < sz; ++i) {
printf("%d %d %d\n", vals[i][0], vals[i][1], vals[i][2]);
int p = vals[i][1], id = vals[i][2];
if (id >= n) {
pos[id - n] = i;
} else {
int nw = p - get(1, 0, sz - 1, 0, i);
now[p] = i;
upd(1, 0, sz - 1, p, nw, 1);
}
}
vector<int> ans(q);
for (int i = 0; i < q; ++i) {
add(1, 0, sz - 1, now[x[i]], sz - 1, 1);
upd(1, 0, sz - 1, now[x[i]], -inf, 0);
now[x[i]] = pos[i];
int nw = x[i] - get(1, 0, sz - 1, 0, now[x[i]]);
add(1, 0, sz - 1, now[x[i]], sz - 1, -1);
upd(1, 0, sz - 1, now[x[i]], nw, 1);
ans[i] = val[1];
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
16128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
16128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
17908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
16128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
