제출 #969166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
969166		kilkuwu	무지개나라 (APIO17_rainbow)	C++17	100 / 100	635 ms	224776 KiB

rainbow

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

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

constexpr int mxN = 2e5 + 5;

struct SegmentTree {
  struct Node {
    int v = 0, l = 0, r = 0;
  };

  std::vector<int> points[mxN];
  std::vector<Node> info = {Node(), Node()};
  int roots[mxN + 1];

  int copy(int k) {
    info.emplace_back(info[k]);
    return info.size() - 1;
  }

  void add_point(int x, int y) {
    points[x].push_back(y);
  }

  void build() {
    roots[0] = 1;
    for (int i = 0; i < mxN; i++) {
      roots[i + 1] = roots[i];
      std::sort(points[i].begin(), points[i].end());
      points[i].erase(std::unique(points[i].begin(), points[i].end()), points[i].end());

      for (int y : points[i]) {
        roots[i + 1] = update(roots[i + 1], 0, mxN, y, 1);
      }
    }
  }

  int update(int k, int l, int r, int p, int v) {
    int id = copy(k);
    info[id].v += v;
    if (r - l == 1) return id;
    int m = (l + r) / 2;
    if (p < m) {
      int left = update(info[id].l, l, m, p, v);
      info[id].l = left;
    } else {
      int right = update(info[id].r, m, r, p, v);
      info[id].r = right;
    }
    return id;
  }

  int query(int k, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return info[k].v;
    int m = (l + r) / 2;
    int ans = 0;
    if (m > ql) {
      ans += query(info[k].l, l, m, ql, qr); 
    }
    if (m < qr) {
      ans += query(info[k].r, m, r, ql, qr);
    }
    return ans;
  }

  int query(int x1, int y1, int x2, int y2) {
    if (x1 >= x2 || y1 >= y2) return 0;
    return query(roots[x2], 0, mxN, y1, y2) - query(roots[x1], 0, mxN, y1, y2);
  }
} rivers, vertices, edges_ho, edges_ve;

void add_river(int x, int y) {
  dbg(x, y);
  rivers.add_point(x, y);
  vertices.add_point(x, y);
  vertices.add_point(x + 1, y);
  vertices.add_point(x, y + 1);
  vertices.add_point(x + 1, y + 1);
  edges_ho.add_point(x, y);
  edges_ho.add_point(x + 1, y);
  edges_ve.add_point(x, y);
  edges_ve.add_point(x, y + 1);
}

int mn_x, mx_x, mn_y, mx_y;

void init(int R, int C, int sr, int sc, int M, char *S) {
  mn_x = mx_x = sr;
  mn_y = mx_y = sc;

  add_river(sr, sc);
  for (int i = 0; i < M; i++) {
    if (S[i] == 'N') sr--;
    else if (S[i] == 'S') sr++;
    else if (S[i] == 'W') sc--;
    else sc++;
    add_river(sr, sc);
    mn_x = std::min(mn_x, sr);
    mx_x = std::max(mx_x, sr);
    mn_y = std::min(mn_y, sc);
    mx_y = std::max(mx_y, sc);
  }

  rivers.build();
  vertices.build();
  edges_ho.build();
  edges_ve.build();
}

int colour(int ar, int ac, int br, int bc) {
  dbg(ar, ac, br, bc);
  int E = edges_ho.query(ar + 1, ac, br + 1, bc + 1) + edges_ve.query(ar, ac + 1, br + 1, bc + 1);
  E += (br - ar + 1 + bc - ac + 1) * 2;
  int V = vertices.query(ar + 1, ac + 1, br + 1, bc + 1);
  V += (br - ar) * 2 + (bc - ac + 2) * 2;
  int R = rivers.query(ar, ac, br + 1, bc + 1);
  int C = (ar < mn_x && br > mx_x && ac < mn_y && bc > mx_y) ? 2 : 1;
  dbg(E, V, R, C);
  return E - V + C - R;
}

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