Submission #964686

#	Time	Username	Problem	Language	Result	Execution time	Memory
964686		Soumya1	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	742 ms	149584 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());
      t[x].erase(unique(t[x].begin(), t[x].end()), 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;
void init(int R, int C, int sr, int sc, int M, char *S) {
  N = R + 5;
  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(N);
  for (auto [x, y] : all) {
    f.insert(1, 1, N, x, y);
    edger.insert(1, 1, N, x, y);
    edger.insert(1, 1, N, x + 1, y);
    edged.insert(1, 1, N, x, y);
    edged.insert(1, 1, N, x, y + 1);
    point.insert(1, 1, N, x, y);
    point.insert(1, 1, N, x + 1, y);
    point.insert(1, 1, N, x, y + 1);
    point.insert(1, 1, N, x + 1, y + 1);
  }
  point.build(1, 1, N);
  edger.build(1, 1, N);
  edged.build(1, 1, N);
  f.build(1, 1, N);
}
int colour(int ar, int ac, int br, int bc) {
  int X = 2 * (br - ar + bc - ac + 6);
  int nodes = 2 * X - 8 + point.sum(1, 1, N, ar + 1, br, ac + 1, bc);
  int edges = edger.sum(1, 1, N, ar + 1, br, ac, bc) + edged.sum(1, 1, N, ar, br, ac + 1, bc);
  edges += 3 * X - 12;
  int comp = 1;
  if (ar < mnr && mxr < br && ac < mnc && mxc < bc) comp++;
  int bad_faces = X - 4 + f.sum(1, 1, N, ar, br, ac, bc);
  return edges - nodes + comp - bad_faces;
}

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