#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
template<class T, int SZ> struct LazySegTree {
T sum[2*SZ], mx[2*SZ], lazy[2*SZ]; // set SZ to a power of 2
LazySegTree() {
F0R(i,2*SZ) mx[i] = -MOD, sum[i] = 0;
memset (lazy,0,sizeof lazy);
}
void push(int ind, int L, int R) {
mx[ind] += lazy[ind];
if (L != R) lazy[2*ind] += lazy[ind], lazy[2*ind+1] += lazy[ind];
lazy[ind] = 0;
}
void pull(int ind) {
sum[ind] = sum[2*ind]+sum[2*ind+1];
mx[ind] = max(mx[2*ind],mx[2*ind+1]);
}
void build() {
F0Rd(i,SZ) pull(i);
}
T qsum(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
push(ind,L,R);
if (lo > R || L > hi) return 0;
if (lo <= L && R <= hi) return sum[ind];
int M = (L+R)/2;
return qsum(lo,hi,2*ind,L,M) + qsum(lo,hi,2*ind+1,M+1,R);
}
T qmax(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
push(ind,L,R);
if (lo > R || L > hi) return -MOD;
if (lo <= L && R <= hi) return mx[ind];
int M = (L+R)/2;
return max(qmax(lo,hi,2*ind,L,M), qmax(lo,hi,2*ind+1,M+1,R));
}
void se(int pos, pi val, int ind = 1, int L = 0, int R = SZ-1) {
push(ind,L,R);
if (R < pos || pos < L) return;
if (L == R) {
mx[ind] = val.f, sum[ind] = val.s;
return;
}
int M = (L+R)/2;
se(pos,val,2*ind,L,M), se(pos,val,2*ind+1,M+1,R);
pull(ind);
}
void upd(int lo, int hi, int inc, int ind = 1, int L = 0, int R = SZ-1) {
push(ind,L,R);
if (hi < L || R < lo) return;
if (lo <= L && R <= hi) {
lazy[ind] = inc;
push(ind,L,R);
return;
}
int M = (L+R)/2;
upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R);
pull(ind);
}
};
LazySegTree<int,1<<20> L;
#include "bubblesort2.h"
map<pi,int> m;
vpi v;
vi cur;
void init(vi A, vi X, vi V) {
F0R(i,sz(A)) {
m[{A[i],i}] = 0;
v.pb({A[i],i});
}
F0R(i,sz(V)) m[{V[i],X[i]}] = 0;
int co = 0;
for (auto& a: m) a.s = co++;
sort(all(v));
cur = A;
F0R(i,sz(v)) {
int ind = m[{A[i],i}];
L.mx[ind^(1<<20)] = v[i].s-i;
L.sum[ind^(1<<20)] = 1;
}
L.build();
}
// // store current pos - correct pos based on {value, correct pos}
int process(int x, int v) {
int pos = m[{cur[x],x}];
L.upd(pos+1,(1<<20)-1,1);
L.se(pos,{-MOD,0});
cur[x] = v;
pos = m[{cur[x],x}];
L.upd(pos+1,(1<<20)-1,-1);
L.se(pos,{x-L.qsum(0,pos-1),1});
return L.qmax(0,(1<<20)-1);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
init(A,X,V);
vi answer; F0R(i,sz(V)) answer.pb(process(X[i],V[i]));
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
25080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
25080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
27620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
25080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
