Submission #50181

#	Time	Username	Problem	Language	Result	Execution time	Memory
50181		mirbek01	Wall (IOI14_wall)	C++17	0 / 100	277 ms	17660 KiB

wall

#include "wall.h"

# include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 2;

struct st{
      int a, b, x;
      st(){
            a = b = 0;
      }
}t[N * 4];

int nn;

void push(int v, int tl, int tr){
      int tm = (tl + tr) >> 1;
      if(t[v].b == 1){
            t[v].a = max(t[v].a, t[v].x);
            if(tl != tr){
                  if(t[v << 1].b == 2)
                        push(v << 1, tl, tm);
                  if(t[(v << 1) | 1].b == 2)
                        push((v << 1) | 1, tm + 1, tr);
                  t[v << 1].b = t[(v << 1) | 1].b = 1;
                  t[v << 1].x = t[(v << 1) | 1].x = t[v].x;
            }
      }
      if(t[v].b == 2){
            t[v].a = min(t[v].a, t[v].x);
            if(tl != tr){
                  if(t[v << 1].b == 1)
                        push(v << 1, tl, tm);
                  if(t[(v << 1) | 1].b == 1)
                        push((v << 1) | 1, tm + 1, tr);
                  t[v << 1].b = t[(v << 1) | 1].b = 2;
                  t[v << 1].x = t[(v << 1) | 1].x = t[v].x;
            }
      }
      t[v].b = 0;
}

void update(int l, int r, int x, int op, int v = 1, int tl = 1, int tr = nn){
      push(v, tl, tr);
      if(l > tr || tl > r) return ;
      if(l <= tl && tr <= r){
            t[v].x = x;
            t[v].b = op;
            push(v, tl, tr);
            return ;
      }
      int tm = (tl + tr) >> 1;
      update(l, r, x, op, v << 1, tl, tm);
      update(l, r, x, op, (v << 1) | 1, tm + 1, tr);
}

int get(int pos, int v = 1, int tl = 1, int tr = nn){
      push(v, tl, tr);
      if(tl == tr)
            return t[v].a;
      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[]){
      nn = 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: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39