제출 #964644

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964644		Soumya1	무지개나라 (APIO17_rainbow)	C++17	12 / 100	220 ms	103600 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;
struct SegmentTree {
  int n;
  vector<vector<int>> t;
  SegmentTree() { }
  SegmentTree(int _n) {
    n = _n;
    t.resize(4 * n);
  }
  void insert(int x, int lx, int rx, int px, int py) {
    if (lx == rx) {
      t[x].push_back(py);
      return;
    }
    int mx = (lx + rx) >> 1;
    if (px <= mx) insert(x << 1, lx, mx, px, py);
    else insert(x << 1 | 1, mx + 1, rx, px, py);
  }
  void build(int x, int lx, int rx) {
    if (lx == rx) {
      sort(t[x].begin(), t[x].end());
      return;
    }
    int mx = (lx + rx) >> 1;
    build(x << 1, lx, mx);
    build(x << 1 | 1, mx + 1, rx);
    merge(t[x << 1].begin(), t[x << 1].end(), t[x << 1 | 1].begin(), t[x << 1 | 1].end(), back_inserter(t[x]));
  }
  int sum(int x, int lx, int rx, int xl, int xr, int yl, int yr) {
    if (xl > xr || yl > yr) return 0;
    if (lx > xr || xl > rx) return 0;
    if (xl <= lx && xr >= rx) return upper_bound(t[x].begin(), t[x].end(), yr) - lower_bound(t[x].begin(), t[x].end(), yl);
    int mx = (lx + rx) >> 1;
    return sum(x << 1, lx, mx, xl, xr, yl, yr) + sum(x << 1 | 1, mx + 1, rx, xl, xr, yl, yr);
  }
};
int mxc, mxr, mnc, mnr;
SegmentTree point, edger, edged, f;
int N;
vector<pair<int, int>> all;
bool has(int x, int y) {
  return binary_search(all.begin(), all.end(), pair<int, int> {x, y});
}
void init(int R, int C, int sr, int sc, int M, char *S) {
  N = R;
  all = {{sr, sc}};
  mxr = mnr = sr;
  mxc = mnc = sc;
  for (int i = 0; i < M; i++) {
    if (S[i] == 'E') sc++;
    if (S[i] == 'W') sc--;
    if (S[i] == 'N') sr--;
    if (S[i] == 'S') sr++;
    all.push_back({sr, sc});
    mxr = max(mxr, sr);
    mnr = min(mnr, sr);
    mxc = max(mxc, sc);
    mnc = min(mnc, sc);
  }
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  point = edger = edged = f = SegmentTree(R);
  for (auto [x, y] : all) {
    point.insert(1, 1, R, x, y);
    if (has(x, y + 1)) {
      edger.insert(1, 1, R, x, y);
    }
    if (has(x + 1, y)) {
      edged.insert(1, 1, R, x, y);
    }
    if (has(x + 1, y) && has(x, y + 1) && has(x + 1, y + 1)) {
      f.insert(1, 1, R, x, y);
    }
  }
  point.build(1, 1, R);
  edger.build(1, 1, R);
  edged.build(1, 1, R);
  f.build(1, 1, R);
}
int colour(int ar, int ac, int br, int bc) {
  int nodes = 2 * (br - ar + bc - ac + 4) + point.sum(1, 1, N, ar, br, ac, bc);
  int edges = edger.sum(1, 1, N, ar, br, ac, bc - 1) + edged.sum(1, 1, N, ar, br - 1, ac, bc);
  edges += point.sum(1, 1, N, ar, ar, ac, bc) + point.sum(1, 1, N, br, br, ac, bc);
  edges += point.sum(1, 1, N, ar, br, ac, ac) + point.sum(1, 1, N, ar, br, bc, bc);
  edges += 2 * (br - ar + bc - ac + 4);
  int comp = 1;
  if (ar < mnr && mxr < br && ac < mnc && mxc < bc) comp++;
  int bad_faces = f.sum(1, 1, N, ar, br - 1, ac, bc - 1);
  bad_faces += edged.sum(1, 1, N, ar, br - 1, ac, ac);
  bad_faces += edged.sum(1, 1, N, ar, br - 1, bc, bc);
  bad_faces += edger.sum(1, 1, N, ar, ar, ac, bc - 1);
  bad_faces += edger.sum(1, 1, N, br, br, ac, bc - 1);
  bad_faces += has(ar, ac) + has(ar, bc) + has(br, ac) + has(br, bc);
  return edges - nodes + comp - bad_faces;
}

• Subtask 1: 0 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26