#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define bug(x) cerr << #x << " : " << x << '\n'
#define mid ((l + r) >> 1)
#define lc (id << 1)
#define rc (lc | 1)
typedef pair<int, int> pii;
const int maxn = 1e6 + 10;
const int inf = 1e9 + 10;
int n, q, m, a[maxn];
int seg[maxn << 2], lz[maxn << 2];
int fen[maxn];
vector<pii> C;
void shift(int id, int l, int r);
void add(int id, int l, int r, int ql, int qr, int x){
if(qr <= l or r <= ql)
return;
if(l >= ql and r <= qr){
seg[id] += x;
lz[id] += x;
return;
}
shift(id, l, r);
add(lc, l, mid, ql, qr, x);
add(rc, mid, r, ql, qr, x);
seg[id] = max(seg[lc], seg[rc]);
}
void change(int id, int l, int r, int p, int x){
if(l + 1 == r){
seg[id] = x;
return;
}
shift(id, l, r);
if(p < mid)
change(lc, l, mid, p, x);
else
change(rc, mid, r, p, x);
seg[id] = max(seg[lc], seg[rc]);
}
void shift(int id, int l, int r){
if(!lz[id])
return;
add(lc, l, mid, l, mid, lz[id]);
add(rc, mid, r, mid, r, lz[id]);
lz[id] = 0;
}
void add(int i, int x){
for(i ++; i <= m; i += i & -i)
fen[i] += x;
}
int get(int i){
int res = 0;
for(; i; i -= i & -i)
res += fen[i];
return res;
}
int get(int l, int r){
return get(r) - get(l);
}
void add(int x, int i, int val){
int ind = lower_bound(all(C), mp(x, i)) - C.begin();
int r = lower_bound(all(C), mp(x, -inf)) - C.begin();
int l = upper_bound(all(C), mp(x, inf)) - C.begin();
add(1, 0, m, 0, r, val);
if(val == -1){
change(1, 0, m, ind, -inf);
}
else{
int res = get(l, m) - (n - 1 - i);
change(1, 0, m, ind, res);
}
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
n = A.size();
q = X.size();
for(int i = 0; i < n; i ++)
C.pb(mp(a[i], i));
for(int i = 0; i < q; i ++)
C.pb(mp(V[i], X[i]));
sort(all(C));
C.resize(unique(all(C)) - C.begin());
m = C.size();
fill_n(seg, maxn << 2, -inf);
for(int i = 0; i < n; i ++){
add(a[i], i, 1);
}
vector<int> ans;
for(int i = 0; i < q; i ++){
add(a[X[i]], X[i], -1);
a[X[i]] = V[i];
add(a[X[i]], X[i], 1);
ans.pb(seg[1]);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
15940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
15940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
17044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
15940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
