#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
vi a, segm, lazy;
vector<pair<int,int>>V;
void propagate(int pos, int l, int r) {
if(l==r) return;
int m = (l+r)/2, right = pos + 2 * (m-l+1);
lazy[pos+1] += lazy[pos];
lazy[right] += lazy[pos];
segm[pos+1] += lazy[pos];
segm[right] += lazy[pos];
lazy[pos] = 0;
}
void upd(int pos, int l, int r, int L, int R, int val) {
if(l > R or r < L) return;
propagate(pos, l, r);
if(l >= L && r <= R) {
segm[pos] += val;
lazy[pos] += val;
return;
}
int m = (l+r)/2, right = pos + 2 * (m-l+1);
if(L <= m) upd(pos+1, l, m, L, R, val);
if(R >= m+1) upd(right, m+1, r, L, R, val);
segm[pos] = max(segm[pos+1], segm[right]);
}
void add(int i, int x) {
int j = lower_bound(V.begin(), V.end(), make_pair(a[i], i)) - V.begin();
int j2 = lower_bound(V.begin(), V.end(), make_pair(a[i], -1)) - V.begin();
upd(1, 0, V.size()-1, j, j, x*(i+1));
upd(1, 0, V.size()-1, j2, V.size()-1, -x);
}
vi countScans(vi A, vi x, vi y) {
int n = A.size(), q = x.size();
vi ans;
V.clear();
segm.assign(8*n, 0);
lazy.assign(8*n, 0);
a.assign(n, 0);
for(int i=0; i<n; ++i) {
a[i] = A[i];
V.push_back({A[i], i});
}
sort(V.begin(), V.end());
V.erase(unique(V.begin(), V.end()), V.end());
for(int i=0; i<n; ++i) add(i, 1);
for(int i=0; i<q; ++i) {
add(x[i], -1);
a[x[i]] = y[i];
add(x[i], 1);
ans.push_back(segm[0]);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
2896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
