Submission #1013836

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013836		amirhoseinfar1385	벽 (IOI14_wall)	C++17	100 / 100	827 ms	86120 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000000+10,lg=21,kaf=(1<<lg);
int inf=1e9+5;

struct segment{
  struct node{
    int l,r,now;
    node(){
      now=l=0;
      r=inf;
    }
  };
  node seg[(1<<(lg+1))];
  void calc(int i){
    if(i>=kaf){
      //cout<<i-kaf<<" "<<seg[i].now<<" "<<seg[i].l<<" "<<seg[i].r<<endl;
      seg[i].now=max(seg[i].now,seg[i].l);
      seg[i].now=min(seg[i].now,seg[i].r);
      seg[i].l=0;
      seg[i].r=inf;
      return ;
    }
  }
  void shift(int i){
    if(i>=kaf){
      return calc(i);
    }
    seg[(i<<1)].l=max(seg[i].l,seg[(i<<1)].l);
    seg[(i<<1)^1].l=max(seg[i].l,seg[(i<<1)^1].l);
    seg[(i<<1)].r=min(seg[(i<<1)].r,seg[i].r);
    seg[(i<<1)^1].r=min(seg[i].r,seg[(i<<1)^1].r);
    if(seg[(i<<1)].l>seg[(i<<1)].r){
      if(seg[i].l==seg[(i<<1)].l){
        seg[(i<<1)].r=seg[i].l;
      }else{
        seg[(i<<1)].l=seg[i].r;
      }
    }
    if(seg[(i<<1)^1].l>seg[(i<<1)^1].r){
      if(seg[i].l==seg[(i<<1)^1].l){
        seg[(i<<1)^1].r=seg[i].l;
      }else{
        seg[(i<<1)^1].l=seg[i].r;
      }
    }
    seg[i].l=0;
    seg[i].r=inf;
    return ;
  }
  void upd(int i,int l,int r,int tl,int tr,int vas,int w){
    if(l>r||l>tr||r<tl||tl>tr){
      return ;
    }
    shift(i);
    if(l>=tl&&r<=tr){
      if(vas==1){
        seg[i].l=max(seg[i].l,w);
      }else{
        seg[i].r=min(seg[i].r,w);
      }
      ////cout<<"upd: "<<l<<" "<<r<<" "<<vas<<" "<<w<<" "<<seg[i].l<<endl;
      shift(i);
      calc(i);
      //if(l==4&&r==5)
      ////cout<<"upd: "<<l<<" "<<r<<" "<<vas<<" "<<w<<" "<<seg[(i<<1)^1].l<<endl;
      return ;
    }
    int m=(l+r)>>1;
    upd((i<<1),l,m,tl,tr,vas,w);
    upd((i<<1)^1,m+1,r,tl,tr,vas,w);
    calc(i);
    return ;
  }
  int pors(int i,int l,int r,int tl,int tr){
    if(l>r||l>tr||r<tl||tl>tr){
      return 0;
    }
    shift(i);
    calc(i);
    if(l>=tl&&r<=tr){
      return seg[i].now;
    }
    int m=(l+r)>>1;
    return pors((i<<1),l,m,tl,tr)+pors((i<<1)^1,m+1,r,tl,tr);;
  }
}seg;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i=0;i<k;i++){
    seg.upd(1,0,kaf-1,left[i],right[i],op[i],height[i]);
  }
  for(int i=0;i<n;i++){
    finalHeight[i]=seg.pors(1,0,kaf-1,i,i);
  }
}

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