#include <bits/stdc++.h>
//#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=1<<20;
const int STALA=1e6;
const int inf=1e9+9;
int LAZY[MAX*4],MAXI[MAX*4];
void push(int u){
LAZY[2*u]+=LAZY[u];
LAZY[2*u+1]+=LAZY[u];
MAXI[u]+=LAZY[u];
LAZY[u]=0;
}
void update(int a,int b,int u,int lo,int hi,int c){
if (b<lo || a>hi)return;
if (a<=lo && b>=hi){
LAZY[u]+=c;
return;
}
int mid=(lo+hi)>>1;
update(a,b,2*u,lo,mid,c);
update(a,b,2*u+1,mid+1,hi,c);
MAXI[u]=max(MAXI[2*u]+LAZY[2*u],MAXI[2*u+1]+LAZY[2*u+1]);
}
int getmax(int a,int b,int u,int lo,int hi){
if (b<lo || a>hi)return -inf;
push(u);
if (a<=lo && b>=hi)
return MAXI[u];
int mid=(lo+hi)>>1;
int L=getmax(a,b,2*u,lo,mid);
int R=getmax(a,b,2*u+1,mid+1,hi);
return max(L,R);
}
void upd(int u,int v,int c){
update(u,v,1,1,MAX,c);
}
int ran(int u,int v){
return getmax(u,v,1,1,MAX);
}
int a[MAX],x[MAX],v[MAX];
vi countScans(vi _a,vi _x,vi _v){
int n=sz(_a);
int q=sz(_v);
vector<pii> compress;
compress.clear();
for (int i=1;i<=n;i++)a[i]=_a[i-1],compress.pb(mp(a[i],i));
for (int i=1;i<=q;i++){
x[i]=_x[i];
v[i]=_v[i];
compress.pb(mp(v[i],x[i]));
}
sort(compress.begin(),compress.end());
compress.erase(unique(compress.begin(),compress.end()),compress.end());
for (int i=1;i<=n;i++){
a[i]=lower_bound(compress.begin(),compress.end(),mp(a[i],i))-compress.begin()+1;
}
for (int i=1;i<=q;i++){
v[i]=lower_bound(compress.begin(),compress.end(),mp(v[i],x[i]))-compress.begin()+1;
}
int ile=sz(compress);
for (int i=1;i<=n;i++){
upd(a[i],a[i],i); // assert uniqueness
upd(a[i]+1,ile,-1);
}
vi ans;
ans.clear();
for (int i=1;i<=q;i++){
upd(a[x[i]],a[x[i]],-x[i]);
upd(a[x[i]]+1,ile,1);
a[x[i]]=v[i];
upd(a[x[i]],a[i],x[i]);
upd(a[x[i]]+1,ile,-1);
ans.pb(ran(1,STALA));
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
1500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
