#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 5e5+10;
const int inf = 1e9+10;
vector<int> ans;
struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
struct node{
int mx,smx,tag;
node(){
mx = inf;
smx = 0;
tag = 0;
}
};
node seg[mxn*4];
SEG(){
for(auto &i:seg)i = node();
}
void push(int now){
if(seg[ls].mx >= seg[now].mx)seg[ls].tag += seg[now].tag,seg[ls].mx = seg[now].mx;
if(seg[rs].mx >= seg[now].mx)seg[rs].tag += seg[now].tag,seg[rs].mx = seg[now].mx;
seg[now].tag = 0;
return;
}
void pull(int now){
seg[now].mx = max(seg[ls].mx,seg[rs].mx);
if(seg[ls].mx<seg[rs].mx)seg[now].smx = max(seg[ls].mx,seg[rs].smx);
else if(seg[ls].mx>seg[rs].mx)seg[now].smx = max(seg[ls].smx,seg[rs].mx);
else seg[now].smx = max(seg[ls].smx,seg[rs].smx);
return;
}
void modify(int now,int l,int r,int s,int e,int v){
if(seg[now].mx<v)return;
if(l>=s&&e>=r){
if(seg[now].smx<v){
seg[now].mx = v;
seg[now].tag++;
}
else{
push(now);
modify(ls,l,mid,s,e,v);
modify(rs,mid+1,r,s,e,v);
pull(now);
}
return;
}
push(now);
if(mid>=s)modify(ls,l,mid,s,e,v);
if(mid<e)modify(rs,mid+1,r,s,e,v);
pull(now);
}
void dfs(int now,int l,int r){
if(l == r){
ans.push_back(seg[now].tag);
return;
}
push(now);
dfs(ls,l,mid);
dfs(rs,mid+1,r);
pull(now);
return;
}
#undef ls
#undef rs
#undef mid
};
SEG seg;
vector<pii> op[mxn];
int N,Q;
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
N = A.size(),Q = X.size();
for(int i = 0;i<Q;i++){
int p = X[i],v = V[i];
A[p] = v;
int tans = 0,sm = inf;
for(int j = N-1;j>=0;j--){
tans += (sm>=A[j]);
sm = min(sm,A[j]);
}
ans.push_back(N-tans);
}
return ans;
for(int i = 0;i<N;i++)op[i].push_back(pii(0,A[i]));
for(int i = 0;i<Q;i++){
int p = X[i],v = V[i];
op[p].push_back(pii(i+1,v));
}
for(int i = N-1;i>=0;i--){
int pre = Q;
while(!op[i].empty()){
auto [t,v] = op[i].back();op[i].pop_back();
seg.modify(0,0,Q,t,pre,v);
pre = t-1;
}
}
seg.dfs(0,0,Q);
ans.erase(ans.begin());
for(auto &i:ans)i = N-i;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
35776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
35776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
35904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
35776 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
