#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
// #define int long long
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(),a.end()
const int N=2e5 + 3;
const int MOD=1e9+7;
const int off=(1<<20);
int t[off*2],dis[off*2],lazy[off*2];
void upd2(int x,int v){
x+=off;
t[x]+=v;
while(x/=2){
t[x]=t[x*2]+t[x*2+1];
}
}
int get2(int x,int l,int r,int st,int en){
if(r<st||l>en)return 0;
if(r<=en&&l>=st){
return t[x];
}
int md=(l+r)/2;
return get2(x*2,l,md,st,en)+get2(x*2+1,md+1,r,st,en);
}
void push(int x,int l,int r){
if(lazy[x]==0)return;
if(l!=r){
lazy[x*2]+=lazy[x];
lazy[x*2+1]+=lazy[x];
}
dis[x]+=lazy[x];
lazy[x]=0;
}
void upd(int x,int l,int r,int st,int en,int df){
push(x,l,r);
if(r<st||l>en)return ;
if(l>=st&&r<=en){
lazy[x]+=df;
push(x,l,r);
return ;
}
int md=(l+r)/2;
upd(x*2,l,md,st,en,df);
upd(x*2+1,md+1,r,st,en,df);
dis[x]=max(dis[x*2],dis[x*2+1]);
}
int get(int x,int l,int r,int st,int en){
push(x,l,r);
if(r<st||l>en)return INT_MIN;
if(l>=st&&r<=en){
return dis[x];
}
int md=(l+r)/2;
int ll=get(x*2,l,md,st,en);
int rr=get(x*2+1,md+1,r,st,en);
return max(ll,rr);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
for(int i=0;i<off*2;i++)dis[i]=INT_MIN,t[i]=0,lazy[i]=0;
int q=X.size(),n=A.size();
vector<int>ans;
set<int>st;
for(auto it:A)st.insert(it);
for(auto it:V)st.insert(it);
int cnt=1;
map<int,int>mp;
for(auto it:st)mp[it]=cnt++;
vector<set<int>>vv(1e6+20);
for(int i=0;i<n;i++){
int a=A[i];
upd2(mp[a],1);
vv[mp[a]].insert(i+1);
}
int cur=0;
for(int i=1;i<=cnt;i++){
if(vv[i].empty()){
// upd(1,1,off-1,i+1,i+1,INT_MIN);
continue;
}
cur+=vv[i].size();
upd(1,1,off-1,i+1,i+1,(-1*dis[i+off])+(*vv[i].rbegin())-cur);
}
for(int j=0;j<q;j++){
int x=X[j],v=mp[V[j]];
int a=mp[A[x]],prev;
upd(1,1,off-1,a+1,cnt+1,-1);
if(a<v){
upd(1,1,off-1,a+2,v+1,2);
}
upd(1,1,off-1,v+1,cnt+1,1);
upd(1,1,off-1,a+1,a+1,-1*dis[a+off]);
upd2(a,-1);
vv[a].erase(x+1);
vv[v].insert(x+1);
upd2(v,1);
prev=get2(1,1,off-1,1,v+1);
// cout<<prev<<' ';
upd(1,1,off-1,v+1,v+1,-1*dis[v+off]);
upd(1,1,off-1,v+1,v+1,(*vv[v].rbegin())-prev);
// cout<<dis[1]<<endl;
if(vv[a].size()&&a!=v){
prev=get2(1,1,off-1,1,a+1);
upd(1,1,off-1,a+1,a+1,(*vv[a].rbegin())-prev);
}
A[x]=V[j];
// ans.pb(dis[1]);
ans.pb(dis[1]);
}
return ans;
}
/*
1 2 5 7 3 5 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
72024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
72024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
73564 KB |
Output is correct |
| 2 |
Correct |
99 ms |
75180 KB |
Output is correct |
| 3 |
Correct |
166 ms |
75904 KB |
Output is correct |
| 4 |
Correct |
170 ms |
75892 KB |
Output is correct |
| 5 |
Incorrect |
163 ms |
76096 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
72024 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
