Submission #50262

#	Time	Username	Problem	Language	Result	Execution time	Memory
50262		mirbek01	Wall (IOI14_wall)	C++17	100 / 100	1304 ms	89140 KiB

wall

#include "wall.h"

# include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 2;

struct st{
      int mn, mx;
      st(){
            mx = 0;
            mn = 1e5 + 1;
      }
}t[N * 4];

int n;

void upd(int v, int x, int tp){
      if(tp == 1){
            t[v].mx = max(t[v].mx, x);
            t[v].mn = max(t[v].mn, x);
      } else {
            t[v].mn = min(t[v].mn, x);
            t[v].mx = min(t[v].mx, x);
      }
}

void down(int v){
      upd(v << 1, t[v].mx, 1);
      upd(v << 1, t[v].mn, 2);
      upd((v << 1) | 1, t[v].mx, 1);
      upd((v << 1) | 1, t[v].mn, 2);
      t[v].mx = 0;
      t[v].mn = 1e5 + 1;
}

void update(int l, int r, int x, int tp, int v = 1, int tl = 1, int tr = n){
      if(l <= tl && tr <= r){
            upd(v, x, tp);
            return ;
      }
      if(tl > r || l > tr) return ;
      down(v);
      int tm = (tl + tr) >> 1;
      update(l, r, x, tp, v << 1, tl, tm);
      update(l, r, x, tp, (v << 1) | 1, tm + 1, tr);
}

int get(int pos, int v = 1, int tl = 1, int tr = n){
      if(tl == tr){
            return t[v].mx;
      }
      down(v);
      int tm = (tl + tr) >> 1;
      if(pos <= tm)
            return get(pos, v << 1, tl, tm);
      return get(pos, (v << 1) | 1, tm + 1, tr);
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
      n = N;
      for(int i = 0; i < k; i ++){
            update(left[i] + 1, right[i] + 1, height[i], op[i]);
      }
      for(int i = 0; i < n; i ++){
            finalHeight[i] = get(i + 1);
      }
}

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