Submission #1119986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119986		Newtonabc	Wall (IOI14_wall)	C++14	100 / 100	1280 ms	102472 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
const int N=1<<22;
pair<int,int> s[N],lz[N];
pair<int,int> merge(pair<int,int> a,pair<int,int> b){
  if(a.first==-1 && a.second==-1) return b;
  if(b.first>a.second) return {b.first,b.first};
  if(b.second<a.first) return {b.second,b.second};
  return {max(a.first,b.first),min(a.second,b.second)};
}
pair<int,int> add(pair<int,int> a,pair<int,int> b){
  return {min(a.first,b.first),max(a.second,b.second)};
}
void buildlz(int l,int r,int idx){
  lz[idx]={-1,-1};
  if(l==r) return;
  int m=(l+r)/2;
  buildlz(l,m,idx*2);
  buildlz(m+1,r,idx*2+1);
}
void pushlz(int l,int r,int idx){
  if(lz[idx]==mp(-1,-1)) return;
  s[idx]=merge(s[idx],lz[idx]);
  if(l!=r) lz[idx*2]=merge(lz[idx*2],lz[idx]),lz[idx*2+1]=merge(lz[idx*2+1],lz[idx]);
  lz[idx]={-1,-1};
}
void update(int l,int r,int idx,int a,int b,int type,int val){
  pushlz(l,r,idx);
  if(a>r || b<l) return;
  if(a<=l && b>=r){
    if(type==1) lz[idx]=merge(lz[idx],mp(val,INT_MAX));
    else lz[idx]=merge(lz[idx],mp(INT_MIN,val));
    pushlz(l,r,idx);
    return;
  }
  int m=(l+r)/2;
  update(l,m,idx*2,a,b,type,val);
  update(m+1,r,idx*2+1,a,b,type,val);
  s[idx]=add(s[idx*2],s[idx*2+1]);
}
int query(int l,int r,int idx,int a){
  pushlz(l,r,idx);
  if(a>r || a<l) return 0;
  if(l==r) return s[idx].first;
  int m=(l+r)/2;
  return query(l,m,idx*2,a)+query(m+1,r,idx*2+1,a);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  buildlz(0,n-1,1);
  for(int i=0;i<k;i++){
    update(0,n-1,1,left[i],right[i],op[i],height[i]);
    /*for(int i=1;i<=26;i++) cout<<i <<" " <<s[i].first <<" " <<s[i].second <<" " <<lz[i].first <<" " <<lz[i].second <<"\n";
    cout<<"---------------------------\n";*/
  }
  for(int i=0;i<n;i++) finalHeight[i]=query(0,n-1,1,i);
  
  return;
}

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