제출 #986792

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
986792		vjudge1	벽 (IOI14_wall)	C++17	100 / 100	642 ms	70236 KiB

wall

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

using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())

typedef long long ll;
typedef pair<int, int> point;

const int off = 1 << 19, inf = 1e9;

point T[2 * off];

point Merge(point A, point B) {
  point ret = A;
  ret.first = min(ret.first, B.second);
  ret.first = max(ret.first, B.first);
  ret.second = min(A.second, B.second);

  return ret;
}

void upd(int x, point v) {
  x += off;
  T[x] = v;
  for(x /= 2; x; x /= 2) {
    T[x] = Merge(T[x * 2], T[x * 2 + 1]);
  }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  vector<pair<point, int>> e;
  REP(i, k) {
    e.push_back({{left[i], 0}, i});
    e.push_back({{right[i], 2}, i});
  }
  REP(i, n) {
    e.push_back({{i, 1}, i});
  }

  REP(i, 2 * off) T[i] = {0, inf};

  sort(e.begin(), e.end());

  for(auto p: e) {
    if(p.first.second == 0) {
      point v = {0, inf};
      int i = p.second;
      if(op[i] == 1) {
        v.first = height[i];
      }
      else {
        v.second = height[i];
      }
      upd(i, v);
    }
    else if(p.first.second == 1) {
      finalHeight[p.second] = T[1].first;
    }
    else {
      upd(p.second, {0, inf});
    }
  }
}

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