oj.uz

Submission #234181

# Submission time Handle Problem Language Result Execution time Memory
234181 2020-05-23T13:07:03 Z rama_pang Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 2676 ms 363896 KB 
#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 Update(Node* &n, int tl, int tr, int p, int q, int x) {
    if (n == nullptr) n = new Node(sy);
    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);
    }
  }

  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);

  map<pair<int, int>, int> tobe;

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

    // Edges
    tobe[{2 * x - 1, 2 * y}] = -1;
    tobe[{2 * x + 1, 2 * y}] = -1;
    tobe[{2 * x, 2 * y - 1}] = -1;
    tobe[{2 * x, 2 * y + 1}] = -1;
    
    // Faces
    tobe[{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++;

  for (auto p : tobe) {
    river_cells.Update(p.first.first, p.first.second, p.second);
  }
}

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 16 ms 1408 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 13 ms 1664 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 8 ms 768 KB Output is correct
12 Correct 10 ms 1152 KB Output is correct
13 Correct 14 ms 2048 KB Output is correct
14 Correct 17 ms 2176 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 594 ms 87660 KB Output is correct
4 Correct 882 ms 146552 KB Output is correct
5 Correct 924 ms 146448 KB Output is correct
6 Correct 738 ms 107636 KB Output is correct
7 Correct 880 ms 106972 KB Output is correct
8 Correct 95 ms 1400 KB Output is correct
9 Correct 944 ms 146328 KB Output is correct
10 Correct 925 ms 146528 KB Output is correct
11 Correct 741 ms 107640 KB Output is correct
12 Correct 821 ms 136440 KB Output is correct
13 Correct 844 ms 146504 KB Output is correct
14 Correct 853 ms 146640 KB Output is correct
15 Correct 692 ms 107768 KB Output is correct
16 Correct 666 ms 101368 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 2439 ms 326264 KB Output is correct
3 Correct 2066 ms 345116 KB Output is correct
4 Correct 2239 ms 346344 KB Output is correct
5 Correct 1608 ms 251096 KB Output is correct
6 Correct 456 ms 25056 KB Output is correct
7 Correct 889 ms 47536 KB Output is correct
8 Correct 740 ms 123364 KB Output is correct
9 Correct 755 ms 118208 KB Output is correct
10 Correct 371 ms 28704 KB Output is correct
11 Correct 1108 ms 121240 KB Output is correct
12 Correct 2521 ms 326228 KB Output is correct
13 Correct 2133 ms 345132 KB Output is correct
14 Correct 2286 ms 346360 KB Output is correct
15 Correct 1642 ms 251004 KB Output is correct
16 Correct 373 ms 20088 KB Output is correct
17 Correct 816 ms 47992 KB Output is correct
18 Correct 2009 ms 127556 KB Output is correct
19 Correct 2224 ms 329364 KB Output is correct
20 Correct 2344 ms 360380 KB Output is correct
21 Correct 737 ms 123436 KB Output is correct
22 Correct 730 ms 118264 KB Output is correct
23 Correct 358 ms 28792 KB Output is correct
24 Correct 1055 ms 121336 KB Output is correct
25 Correct 2463 ms 326340 KB Output is correct
26 Correct 2051 ms 345080 KB Output is correct
27 Correct 2301 ms 346608 KB Output is correct
28 Correct 1651 ms 251240 KB Output is correct
29 Correct 376 ms 20088 KB Output is correct
30 Correct 817 ms 48112 KB Output is correct
31 Correct 2069 ms 127408 KB Output is correct
32 Correct 2268 ms 329288 KB Output is correct
33 Correct 2336 ms 360192 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 16 ms 1408 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 13 ms 1664 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 8 ms 768 KB Output is correct
12 Correct 10 ms 1152 KB Output is correct
13 Correct 14 ms 2048 KB Output is correct
14 Correct 17 ms 2176 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 1136 ms 89768 KB Output is correct
19 Correct 161 ms 7924 KB Output is correct
20 Correct 130 ms 4496 KB Output is correct
21 Correct 146 ms 5368 KB Output is correct
22 Correct 178 ms 6340 KB Output is correct
23 Correct 170 ms 7776 KB Output is correct
24 Correct 157 ms 4744 KB Output is correct
25 Correct 177 ms 5688 KB Output is correct
26 Correct 173 ms 6648 KB Output is correct
27 Correct 755 ms 55320 KB Output is correct
28 Correct 469 ms 29084 KB Output is correct
29 Correct 688 ms 49260 KB Output is correct
30 Correct 1444 ms 129672 KB Output is correct
31 Correct 8 ms 512 KB Output is correct
32 Correct 892 ms 52500 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 16 ms 1408 KB Output is correct
3 Correct 7 ms 640 KB Output is correct
4 Correct 7 ms 768 KB Output is correct
5 Correct 13 ms 1664 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 8 ms 768 KB Output is correct
12 Correct 10 ms 1152 KB Output is correct
13 Correct 14 ms 2048 KB Output is correct
14 Correct 17 ms 2176 KB Output is correct
15 Correct 5 ms 256 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 1136 ms 89768 KB Output is correct
19 Correct 161 ms 7924 KB Output is correct
20 Correct 130 ms 4496 KB Output is correct
21 Correct 146 ms 5368 KB Output is correct
22 Correct 178 ms 6340 KB Output is correct
23 Correct 170 ms 7776 KB Output is correct
24 Correct 157 ms 4744 KB Output is correct
25 Correct 177 ms 5688 KB Output is correct
26 Correct 173 ms 6648 KB Output is correct
27 Correct 755 ms 55320 KB Output is correct
28 Correct 469 ms 29084 KB Output is correct
29 Correct 688 ms 49260 KB Output is correct
30 Correct 1444 ms 129672 KB Output is correct
31 Correct 8 ms 512 KB Output is correct
32 Correct 892 ms 52500 KB Output is correct
33 Correct 2439 ms 326264 KB Output is correct
34 Correct 2066 ms 345116 KB Output is correct
35 Correct 2239 ms 346344 KB Output is correct
36 Correct 1608 ms 251096 KB Output is correct
37 Correct 456 ms 25056 KB Output is correct
38 Correct 889 ms 47536 KB Output is correct
39 Correct 740 ms 123364 KB Output is correct
40 Correct 755 ms 118208 KB Output is correct
41 Correct 371 ms 28704 KB Output is correct
42 Correct 1108 ms 121240 KB Output is correct
43 Correct 2521 ms 326228 KB Output is correct
44 Correct 2133 ms 345132 KB Output is correct
45 Correct 2286 ms 346360 KB Output is correct
46 Correct 1642 ms 251004 KB Output is correct
47 Correct 373 ms 20088 KB Output is correct
48 Correct 816 ms 47992 KB Output is correct
49 Correct 2009 ms 127556 KB Output is correct
50 Correct 2224 ms 329364 KB Output is correct
51 Correct 2344 ms 360380 KB Output is correct
52 Correct 737 ms 123436 KB Output is correct
53 Correct 730 ms 118264 KB Output is correct
54 Correct 358 ms 28792 KB Output is correct
55 Correct 1055 ms 121336 KB Output is correct
56 Correct 2463 ms 326340 KB Output is correct
57 Correct 2051 ms 345080 KB Output is correct
58 Correct 2301 ms 346608 KB Output is correct
59 Correct 1651 ms 251240 KB Output is correct
60 Correct 376 ms 20088 KB Output is correct
61 Correct 817 ms 48112 KB Output is correct
62 Correct 2069 ms 127408 KB Output is correct
63 Correct 2268 ms 329288 KB Output is correct
64 Correct 2336 ms 360192 KB Output is correct
65 Correct 1072 ms 126852 KB Output is correct
66 Correct 1106 ms 121564 KB Output is correct
67 Correct 622 ms 32348 KB Output is correct
68 Correct 1304 ms 124848 KB Output is correct
69 Correct 2645 ms 329952 KB Output is correct
70 Correct 2268 ms 348544 KB Output is correct
71 Correct 2391 ms 349808 KB Output is correct
72 Correct 1734 ms 254656 KB Output is correct
73 Correct 462 ms 23672 KB Output is correct
74 Correct 882 ms 51704 KB Output is correct
75 Correct 2118 ms 131064 KB Output is correct
76 Correct 2450 ms 332764 KB Output is correct
77 Correct 2676 ms 363896 KB Output is correct
78 Correct 594 ms 87660 KB Output is correct
79 Correct 882 ms 146552 KB Output is correct
80 Correct 924 ms 146448 KB Output is correct
81 Correct 738 ms 107636 KB Output is correct
82 Correct 880 ms 106972 KB Output is correct
83 Correct 95 ms 1400 KB Output is correct
84 Correct 944 ms 146328 KB Output is correct
85 Correct 925 ms 146528 KB Output is correct
86 Correct 741 ms 107640 KB Output is correct
87 Correct 821 ms 136440 KB Output is correct
88 Correct 844 ms 146504 KB Output is correct
89 Correct 853 ms 146640 KB Output is correct
90 Correct 692 ms 107768 KB Output is correct
91 Correct 666 ms 101368 KB Output is correct