#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 mx[off*2],mn[off*2];
void upd(int x,int v){
x+=off;
mx[x]=v;
mn[x]=v;
while(x/=2){
mx[x]=max(mx[x*2],mx[x*2+1]);
if(mn[x*2]==0)mn[x*2]=INT_MAX;
if(mn[x*2+1]==0)mn[x*2+1]=INT_MAX;
mn[x]=min(mn[x*2],mn[x*2+1]);
}
}
int get(int x,int l,int r,int st,int en,int val){
if(r<st||l>en)return 0;
if(l>=st&&r<=en){
if(mn[x]>val)
return r-l+1;
if(mx[x]<=val)
return 0;
}
int mid=(l+r)/2;
return (get(x*2,l,mid,st,en,val)+get(x*2+1,mid+1,r,st,en,val));
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
memset(mx,0,sizeof(mx));
memset(mn,0,sizeof(mn));
int q=X.size(),n=A.size();
vector<int>ans;
int dis[n]={0};
multiset<int>ms;
for(int i=0;i<n;i++){
int x=A[i];
upd(i,x);
if(i)
dis[i]=get(1,1,off-1,0,i-1,x);
ms.insert(dis[i]);
}
for(int j=0;j<q;j++){
int x=X[j],v=V[j];
upd(x,v);
ms.erase(ms.find(dis[x]));
if(x)
dis[x]=get(1,1,off-1,0,x-1,v);
ms.insert(dis[x]);
for(int i=x+1;i<n;i++){
if(A[x]<=A[i]&&v>A[i]){
ms.erase(ms.find(dis[i]));
dis[i]++;
// cout<<dis[i]<<endl;
ms.insert(dis[i]);
}
if(A[x]>A[i]&&v<=A[i]){
ms.erase(ms.find(dis[i]));
dis[i]--;
ms.insert(dis[i]);
}
}
A[x]=v;
auto it=ms.end();
it--;
ans.pb(*it);
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
16732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
16732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4614 ms |
18620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
16732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
