제출 #1264625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264625		ortsac	벽 (IOI14_wall)	C++20	100 / 100	710 ms	105828 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define fr first
#define se second

const int INF = 0x3f3f3f3f;
const int MAXK = 5e5 + 10;

struct Node {
  int mi = INF, mx = 0;
};

int tipo[MAXK];
int v[MAXK];
Node seg[4*MAXK];

Node merge(Node a, Node b) {
  Node ans;
  ans.mi = min(a.mi, b.mi);
  ans.mx = max(a.mx, b.mx);
  return ans;
}

Node empt;

void setZero(int node, int l, int r, int po) {
  if (l == r) {
    seg[node] = empt;
    return;
  }
  int m = (l + r)/2;
  if (po <= m) setZero(2*node, l, m, po);
  else setZero(2*node + 1, m + 1, r, po);
  seg[node] = merge(seg[2*node], seg[2*node + 1]);
}

void setOn(int node, int l, int r, int po) {
  if (l == r) {
    seg[node] = empt;
    if (tipo[po] == 1) seg[node].mx = v[l]; // we want the maximum of the adding phase (max)
    else seg[node].mi = v[l];
    return;
  }
  int m = (l + r)/2;
  if (po <= m) setOn(2*node, l, m, po);
  else setOn(2*node + 1, m + 1, r, po);
  seg[node] = merge(seg[2*node], seg[2*node + 1]);
}

Node query(int node, int l, int r, int tl, int tr) {
  if ((r < tl) || (tr < l)) return empt;
  if ((tl <= l) && (r <= tr)) return seg[node];
  int m = (l + r)/2;
  return merge(query(2*node, l, m, tl, tr), query(2*node + 1, m + 1, r, tl, tr));
}

int bbin(int node, int l, int r, Node val) {
  if (l == r) return l;
  Node dir = merge(seg[2*node + 1], val);
  int m = (l + r)/2;
  if (dir.mx > dir.mi) return bbin(2*node + 1, m + 1, r, val);
  return bbin(2*node, l, m, dir);
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[]){
  // 1 is adding phase, 2 is removing phase
  for (int i = 0; i < k; i++) tipo[i] = op[i];
  for (int i = 0; i < k; i++) v[i] = h[i];
  vector<vector<pii>> ops(n + 1);
  for (int i = 0; i < k; i++) {
    ops[l[i]].push_back({i, 1});
    ops[r[i] + 1].push_back({i, 0});
  }
  int qtd = 0;
  for (int i = 0; i < n; i++) {
    for (auto u : ops[i]) {
      if (u.se) setOn(1, 0, k - 1, u.fr);
      else setZero(1, 0, k - 1, u.fr);
      //cout << seg[1].mi << " " << seg[1].mx << "\n";
    }
    if (seg[1].mi >= seg[1].mx) {
      fh[i] = seg[1].mx;
      continue; // no intersection
    }
    int po = bbin(1, 0, k - 1, empt);
    Node ans = query(1, 0 , k - 1, po + 1, k - 1);
    if (tipo[po] == 1) fh[i] = ans.mi;
    else fh[i] = ans.mx;
  }
  //for (int i = 0; i < n; i++) cout << fh[i] << " ";
  //cout << "\n";
  return;
}

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