Submission #1166631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166631		HappyCapybara	Wall (IOI14_wall)	C++17	100 / 100	652 ms	89004 KiB

wall

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

int n;
vector<pair<int,int>> st;

pair<int,int> merge(pair<int,int> a, pair<int,int> 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)};
}

void pushdown(int node, int tl, int tr){
  if (tl == tr) return;
  st[node*2] = merge(st[node*2], st[node]);
  st[node*2+1] = merge(st[node*2+1], st[node]);
  st[node] = {0, 100000};
}

void update(int l, int r, int lo, int hi, int node=1, int tl=0, int tr=n-1){
  pushdown(node, tl, tr);
  if (l <= tl && tr <= r){
    st[node] = merge(st[node], {lo, hi});
    return;
  }
  int tm = (tl+tr)/2;
  if (l <= tm) update(l, r, lo, hi, node*2, tl, tm);
  if (tm+1 <= r) update(l, r, lo, hi, node*2+1, tm+1, tr);
}

int query(int pos, int node=1, int tl=0, int tr=n-1){
  pushdown(node, tl, tr);
  if (tl == tr) return st[node].first;
  int tm = (tl+tr)/2;
  if (pos <= tm) return query(pos, node*2, tl, tm);
  else return query(pos, node*2+1, tm+1, tr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  ::n = n;
  st.resize(4*n, {0, 100000});
  for (int i=0; i<k; i++){
    if (op[i] == 1) update(left[i], right[i], height[i], 100000);
    if (op[i] == 2) update(left[i], right[i], 0, height[i]);
  }
  for (int i=0; i<n; i++) finalHeight[i] = query(i);
  return;
}

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