Submission #1013108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013108		aufan	Wall (IOI14_wall)	C++17	100 / 100	901 ms	224672 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;
const int INF = 1e9;
struct node {
  int val, lb, ub;
  int st, en;
  node *left, *right;
  void lazy() {
    left->val = max(left->val, lb);
    left->lb = max(left->lb, lb);
    left->ub = max(left->ub, lb);
    left->val = min(left->val, ub);
    left->lb = min(left->lb, ub);
    left->ub = min(left->ub, ub);
    right->val = max(right->val, lb);
    right->lb = max(right->lb, lb);
    right->ub = max(right->ub, lb);
    right->val = min(right->val, ub);
    right->lb = min(right->lb, ub);
    right->ub = min(right->ub, ub);
    lb = -INF;
    ub = INF;
  }
  void build(int start, int end) {
    st = start;
    en = end;
    lb = -INF;
    ub = INF;
    if (st == en) {
      val = lb = ub = 0;
      return;
    }
    int md = (st + en)/2;
    left = new node();
    right = new node();
    left->build(st, md);
    right->build(md + 1, en);
  }
  int query(int id) {
    if (st > id || en < id) return 0;
    if (st == en) return val;
    lazy();
    return left->query(id) + right->query(id);
  }
  void updatebounds(int lf, int rg, int x, int y) {
    if (st > rg || en < lf) return;
    if (lf <= st && en <= rg) {
      val = max(val, x);
      lb = max(lb, x);
      ub = max(ub, x);
      val = min(val, y);
      lb = min(lb, y);
      ub = min(ub, y);
      return;
    }
    lazy();
    left->updatebounds(lf, rg, x, y);
    right->updatebounds(lf, rg, x, y);
  }
} sg;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  sg.build(0, n - 1);
  for (int i = 0; i < k; i++) {
    if (op[i] == 1) {
      sg.updatebounds(left[i], right[i], height[i], INF);
    } else if (op[i] == 2) {
      sg.updatebounds(left[i], right[i], -INF, height[i]);
    }
  }
  for (int i = 0; i < n; i++) {
    finalHeight[i] = sg.query(i);
  }
  return;
}

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