Submission #1104196

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104196		tammaidai	Wall (IOI14_wall)	C++17	0 / 100	1 ms	336 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
pair<int,int> seg[8000010];
void push(int l,int r,int idx){
  if(l==r)return;
  seg[idx*2].first = max(seg[idx*2].first,seg[idx].first);
  seg[idx*2].first = min(seg[idx*2].first,seg[idx].second);
  seg[idx*2].second = max(seg[idx*2].second,seg[idx].first);
  seg[idx*2].second = min(seg[idx*2].second,seg[idx].second);
  seg[idx*2+1].first = max(seg[idx*2+1].first,seg[idx].first);
  seg[idx*2+1].first = min(seg[idx*2+1].first,seg[idx].second);
  seg[idx*2+1].second = max(seg[idx*2+1].second,seg[idx].first);
  seg[idx*2+1].second = min(seg[idx*2+1].second,seg[idx].second);
  seg[idx] = {-1e9,1e9};
}
void p(int fh[],int l,int r,int idx){
  if(l==r){
    fh[l] = seg[idx].first;
    return;
  }
  push(l,r,idx);
  int m = (l+r)>>1;
  p(fh,l,m,idx*2);
  p(fh,m+1,r,idx*2+1);
}
void upd(int l,int r,int idx,int val,int op,int ll,int rr){
  if(l>rr || r<ll)return;
  if(l>=ll && r<=rr){
    if(op==1){
      seg[idx].first = max(val,seg[idx].first);
      seg[idx].second = max(val,seg[idx].second);
    }
    else{
      seg[idx].first = min(val,seg[idx].first);
      seg[idx].second = min(val,seg[idx].second);
    }
    return;
  }
  push(l,r,idx);
  int m = (l+r)>>1;
  upd(l,m,idx*2,val,op,ll,rr);
  upd(m+1,r,idx*2+1,val,op,ll,rr);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i = 0;i<k;i++){
    upd(1,n,1,height[i],op[i],left[i],right[i]);
  }
  p(finalHeight,1,n,1);
  return;
}

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