oj.uz

답안 #1013832

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1013832 2024-07-04T06:42:52 Z amirhoseinfar1385 벽 (IOI14_wall) C++17
0 / 100
 91 ms 100344 KB 
#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
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 59 ms 100184 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 63 ms 100344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 54 ms 100136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 91 ms 100180 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -