Submission #50237

#	Time	Username	Problem	Language	Result	Execution time	Memory
50237		mirbek01	Wall (IOI14_wall)	C++17	32 / 100	849 ms	18972 KiB

wall

#include "wall.h"

# include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

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

int n;

void push(int v, int tl, int tr){
      if(t[v].b){
            t[v].mx = max(t[v].mx, t[v].x);
            if(tl != tr){
                  t[v << 1].b = t[(v << 1) | 1].b = 1;
                  t[v << 1].x = max(t[v << 1].x, t[v].x);
                  t[(v << 1) | 1].x = max(t[(v << 1) | 1].x, t[v].x);
            }
            t[v].b = 0;
      }
      if(t[v].c){
            t[v].mn = min(t[v].mn, t[v].y);
            if(tl != tr){
                  t[v << 1].c = t[(v << 1) | 1].c = 1;
                  t[v << 1].y = min(t[v << 1].y, t[v].y);
                  t[(v << 1) | 1].y = min(t[(v << 1) | 1].y, t[v].y);
            }
            t[v].c = 0;
      }
}

void update(int l, int r, int x, int tp, int v = 1, int tl = 1, int tr = n){
      push(v, tl, tr);
      if(tl > r || l > tr) return ;
      if(l <= tl && tr <= r){
            if(tp == 1){
                  t[v].x = x;
                  t[v].b = 1;
            } else {
                  t[v].y = x;
                  t[v].c = 1;
            }
            push(v, tl, tr);
            return ;
      }
      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){
      push(v, tl, tr);
      if(tl == tr){
            return min(t[v].mn, t[v].mx);
      }
      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;

      if(n <= 10000 && k <= 5000){
            for(int i = 0; i < k; i ++){
                  for(int j = left[i]; j <= right[i]; j ++){
                        if(op[i] == 1){
                              finalHeight[j] = max(finalHeight[j], height[i]);
                        } else {
                              finalHeight[j] = min(finalHeight[j], height[i]);
                        }
                  }
            }
      } else {
            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: 0 / 29
• Subtask 4: 0 / 39