Submission #1210486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210486		marshziin	Wall (IOI14_wall)	C++20	61 / 100	371 ms	13320 KiB

wall

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

const int maxn = 5e5 + 10;

struct SegTree {
  int maxx[4*maxn], minn[4*maxn], lz[4*maxn];
  void init() {
    for (int i = 0; i < maxn; ++i)
        lz[i] = -1;
  }
  void unlazy(int node, int tl, int tr) {
    if(lz[node] == -1) return;
    maxx[node] = lz[node];
    minn[node] = lz[node];
    if(tl != tr) {
      lz[2*node] = lz[node];
      lz[2*node+1] = lz[node];

    }
    lz[node] = -1;
  }

  void update(int node, int l, int r, int tl, int tr, int val, int add) {
    unlazy(node, tl, tr);
    if(tl > r || tr < l) return;
    if (tl >= l && tr <= r) {
        if (add == 1) {
            if (minn[node] >= val) return;
            if (maxx[node] <= val) {
                lz[node] = val;
                unlazy(node, tl, tr);
                return;
            }
        }
        if (add == 2) {
            if (maxx[node] <= val) return;
            if (minn[node] >= val) {
                lz[node] = val;
                unlazy(node, tl, tr);
                return;
            }
        }
            }

    int mid = (tl+tr)/2;
    update(2*node, l, r, tl, mid, val, add);
    update(2*node+1, l, r, mid+1, tr, val, add);
    maxx[node] = max(maxx[2*node], maxx[2*node+1]);
    minn[node] = min(minn[2*node], minn[2*node+1]);
  }

  int query(int node, int l, int r, int pos) {
    unlazy(node,l,r);
    if(l == r) return maxx[node];
    int mid = (l+r)/2;
    if(pos <= mid) return query(2*node, l, mid, pos);
    return query(2*node+1, mid+1, r, pos);
  }
} seg;


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  seg.init();
  for (int i = 0; i < k; ++i)
      seg.update(1,left[i], right[i], 0, n-1, height[i], op[i]);
  for (int i = 0; i < n; ++i)
    finalHeight[i] = seg.query(1,0,n-1,i);
  return;
}

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