Submission #1123082

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123082		epicci23	Wall (IOI14_wall)	C++20	8 / 100	3098 ms	71176 KiB

wall

#include "bits/stdc++.h"
#include "wall.h"
using namespace std;

const int N = 2e6 + 5;
const int INF = 1e9 + 5;
array<int,2> seg[4*N];

inline array<int,2> apply(array<int,2> a,array<int,2> b){
  if(a[0] > a[1]) return b;
  if(b[0] > a[1]) return {b[0],b[0]};
  if(b[1] < a[0]) return {b[1],b[1]};
  return {max(b[0],a[0]),min(b[1],a[1])};
}

inline void push(int rt,int l,int r){
  if(seg[rt][0] > seg[rt][1] || l == r) return;
  array<int,2> u = seg[rt];
  seg[rt][0] = 1, seg[rt][1] = 0;
  seg[rt*2] = apply(seg[rt*2], u);
  seg[rt*2+1] = apply(seg[rt*2+1], u);
}

void upd(int rt,int l,int r,int gl,int gr,array<int,2> u){
  push(rt,l,r);
  if(r<gl || l>gr) return;
  if(l>=gl && r<=gr){
    seg[rt]=apply(seg[rt],u);
    push(rt,l,r);
    return;
  }
  int m=(l+r)/2;
  upd(rt*2,l,m,gl,gr,u),upd(rt*2+1,m+1,r,gl,gr,u);
}

array<int,2> query(int rt,int l,int r,int ind){
  push(rt,l,r);
  if(l==r) return seg[rt];
  int m=(l+r)/2;
  if(ind<=m) return query(rt*2,l,m,ind);
  return query(rt*2+1,m+1,r,ind);
}

void buildWall(int _n, int _q, int _op[], int left[], int right[], int height[], int finalHeight[]){
  int n=_n,q=_q;
  int ar[n+5];
  for(int i=1;i<=n;i++) ar[i]=0;
  
  for(int i=0;i<4*N;i++) seg[i]={1,0};

  /*for(int i=0;i<q;i++){
  	int op=_op[i],l=left[i]+1,r=right[i]+1,h=height[i];
  	if(op==1) upd(1,1,n,l,r,{h,INF});
  	else upd(1,1,n,l,r,{-INF,h});
  }*/

  for(int i=0;i<q;i++){
  	int op=_op[i],l=left[i]+1,r=right[i]+1,h=height[i];
  	for(int j=l;j<=r;j++){
  	  if(op==1) ar[j]=max(ar[j],h);
  	  else ar[j]=min(ar[j],h);
  	}
  }
  
  /*for(int i=1;i<=n;i++){
  	auto x = query(1,1,n,i);
  	if(ar[i] <= x[0]) finalHeight[i-1]=x[0];
  	else if(ar[i] <= x[1]) finalHeight[i-1]=0;
  	else finalHeight[i-1]=x[1];
  }*/

  for(int i=1;i<=n;i++) finalHeight[i-1]=ar[i];
  return;
}

/*void _(){
  int n,q;
  cin >> n >> q;
  int ar[n+5];
  for(int i=1;i<=n;i++) cin >> ar[i];
  
  for(int i=0;i<4*N;i++) seg[i]={-INF,INF};

  for(int i=1;i<=q;i++){
  	int op,l,r,h;
  	cin >> op >> l >> r >> h;
  	if(op==1) upd(1,1,n,l,r,{h,INF});
  	else upd(1,1,n,l,r,{-INF,h});
  }
  
  for(int i=1;i<=n;i++){
  	auto x = query(1,1,n,i);
  	if(ar[i] <= x[0]) cout << x[0] << '\n';
  	else if(ar[i] <= x[1]) cout << ar[i] << '\n';
  	else cout << x[1] << '\n';
  }
}

int32_t main(){
  ios::sync_with_stdio(0);cin.tie(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
}*/

• Subtask 1: 8 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39