Submission #173006

#	Time	Username	Problem	Language	Result	Execution time	Memory
173006		Nightlight	Wall (IOI14_wall)	C++14	100 / 100	649 ms	72884 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define adds 1
#define remov 2
#define left(n) (n<<1)
#define right(n) (n<<1|1)
using namespace std;

const int last = 1 << 21;
const int szt = 5e6;
const int maxn = 1<<21;
const int inf = 0x3f3f3f3f;

int ql, qr, state, val; 

struct segtree{
  int mx[szt], mn[szt];
  segtree() {
    memset(mx, inf, sizeof(mx));
  }
  void go(int node) {
    if(state == 2) {
      mx[node] = min(mx[node], val);
      mn[node] = min(mn[node], val);
    }else {
      mx[node] = max(mx[node], val);
      mn[node] = max(mn[node], val);
    }
  }
  void merge(int par, int kid) {
    mx[kid] = min(mx[kid], mx[par]);
    mx[kid] = max(mx[kid], mn[par]);
    mn[kid] = max(mn[kid], mn[par]);
    mn[kid] = min(mn[kid], mx[par]);
  }
  void unlazy(int node) {
    merge(node, left(node));
    merge(node, right(node));
    mx[node] = inf; mn[node] = 0;
  }
  void update(int node, int l, int r) {
    if(ql <= l && r <= qr) {
      go(node);
      return;
    }
    unlazy(node);
    int mid = (l + r) >> 1;
    if(ql <= mid) update(left(node), l, mid);
    if(qr > mid) update(right(node), mid + 1, r);
  }
  void finish() {
    for(int i = 1; i < last; i++)unlazy(i);
  }
};

segtree tree;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[]){
  for(int i = 0; i < k; i++) {
    state = op[i], ql = left[i] + 1, qr = right[i] + 1, val = height[i];
//    cout << state << " " << ql << " " << qr << " " << val << "\n";
    tree.update(1, 1, last);
  }
  tree.finish();
  int cnt = 0;
  for(int i = last; i < last + n; i++) {
//    ans[cnt++] = tree.mn[i];
    ans[cnt++] = min(tree.mx[i], tree.mn[i]);
  }
  return;
}

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