Submission #234153

#	Time	Username	Problem	Language	Result	Execution time	Memory
234153		rama_pang	Land of the Rainbow Gold (APIO17_rainbow)	C++14	50 / 100	3089 ms	184396 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

class SegmentTree {
 private:
  struct Node {
    int val = 0;
    Node *lc = nullptr;
    Node *rc = nullptr;
  };

  int sz;
  Node *root = nullptr;

  void Pull(Node* &n) {
    n->val = 0;
    if (n->lc != nullptr) n->val += n->lc->val;
    if (n->rc != nullptr) n->val += n->rc->val;
  }

  void Update(Node* &n, int tl, int tr, int p, int x) {
    if (n == nullptr) n = new Node();
    if (tl == tr) return void(n->val = x);
    int mid = (tl + tr) / 2;
    if (p <= mid) {
      Update(n->lc, tl, mid, p, x);
    } else {
      Update(n->rc, mid + 1, tr, p, x);
    }
    return Pull(n);
  }

  int Query(Node* &n, int tl, int tr, int l, int r) {
    if (n == nullptr) return 0;
    if (r < tl || tr < l || tl > tr || l > r) return 0;
    if (l <= tl && tr <= r) return n->val;
    int mid = (tl + tr) / 2;
    return Query(n->lc, tl, mid, l, r) + 
           Query(n->rc, mid + 1, tr, l, r);
  }

 public:
  SegmentTree() {}
  SegmentTree(int sz) : sz(sz) {}

  void Update(int p, int x) {
    return Update(root, 0, sz, p, x);
  }
  int Query(int l, int r) {
    return Query(root, 0, sz, l, r);
  }
};

class RangeTree {
 private:
  struct Node {
    SegmentTree seg;
    Node *lc = nullptr;
    Node *rc = nullptr;
    Node(int sz) : seg(sz) {}
  };

  int sx, sy;
  Node *root = nullptr;

  void Pull(Node* &n, int pos) {
    int val = 0;
    if (n->lc != nullptr) val += n->lc->seg.Query(pos, pos);
    if (n->rc != nullptr) val += n->rc->seg.Query(pos, pos);
    n->seg.Update(pos, val);
  }

  void Update(Node* &n, int tl, int tr, int p, int q, int x) {
    if (n == nullptr) n = new Node(sy);
    if (tl == tr) return void(n->seg.Update(q, x));
    if (tl == tr) return;
    int mid = (tl + tr) / 2;
    if (p <= mid) {
      Update(n->lc, tl, mid, p, q, x);
    } else {
      Update(n->rc, mid + 1, tr, p, q, x);
    }
    return Pull(n, q);
  }

  int Query(Node* &n, int tl, int tr, int l, int r, int d, int u) {
    if (n == nullptr) return 0;
    if (r < tl || tr < l || tl > tr || l > r) return 0;
    if (l <= tl && tr <= r) return n->seg.Query(d, u);
    int mid = (tl + tr) / 2;
    return Query(n->lc, tl, mid, l, r, d, u) + 
           Query(n->rc, mid + 1, tr, l, r, d, u);
  }

 public:
  RangeTree() {}
  RangeTree(int sx, int sy) : sx(sx), sy(sy) {}

  void Update(int p, int q, int x) {
    return Update(root, 0, sx, p, q, x);
  }
  int Query(int l, int r, int d, int u) {
    return Query(root, 0, sx, l, r, d, u);
  }
};



// V - E + F = 2
// Vertices = 4 suares points aroud river cells
// Edges = borders around river cells
// Faces = land components + number of river cells

RangeTree river_cells; // keeps V - E + F, scaled by 2
int minr, maxr, minc, maxc;

void init(int R, int C, int sr, int sc, int M, char *S) {
  river_cells = RangeTree(2 * R + 5, 2 * C + 5);

  auto Update = [&](int x, int y) { // cell (x, y) is a river cell
    // Vertices
    river_cells.Update(2 * x - 1, 2 * y - 1, 1);
    river_cells.Update(2 * x - 1, 2 * y + 1, 1);
    river_cells.Update(2 * x + 1, 2 * y - 1, 1);
    river_cells.Update(2 * x + 1, 2 * y + 1, 1);

    // Edges
    river_cells.Update(2 * x - 1, 2 * y, -1);
    river_cells.Update(2 * x + 1, 2 * y, -1);
    river_cells.Update(2 * x, 2 * y - 1, -1);
    river_cells.Update(2 * x, 2 * y + 1, -1);
    
    // Faces
    river_cells.Update(2 * x, 2 * y, 1);
  };

  minr = maxr = sr;
  minc = maxc = sc;

  Update(sr, sc);
  for (int i = 0; i < M; i++) {
    if (S[i] == 'N') sr--;
    if (S[i] == 'S') sr++;
    if (S[i] == 'W') sc--;
    if (S[i] == 'E') sc++;
    Update(sr, sc);
    minr = min(minr, sr);
    minc = min(minc, sc);
    maxr = max(maxr, sr);
    maxc = max(maxc, sc);
  }
  minr--;
  maxr++;
  minc--;
  maxc++;
}

int colour(int ar, int ac, int br, int bc) {
  ar = max(ar, minr);
  ac = max(ac, minc);
  br = min(br, maxr);
  bc = min(bc, maxc);

  return 1 + (ar == minr && ac == minc && br == maxr && bc == maxc) 
         - river_cells.Query(2 * ar, 2 * br, 2 * ac, 2 * bc);
}

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