oj.uz

Submission #234151

# Submission time Handle Problem Language Result Execution time Memory
234151 2020-05-23T11:10:31 Z rama_pang Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 3000 ms 181936 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 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

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 * sr - 1, 2 * sc - 1, 1);
    river_cells.Update(2 * sr - 1, 2 * sc + 1, 1);
    river_cells.Update(2 * sr + 1, 2 * sc - 1, 1);
    river_cells.Update(2 * sr + 1, 2 * sc + 1, 1);

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

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

int colour(int ar, int ac, int br, int bc) {
  return 1 - river_cells.Query(2 * ar, 2 * br, 2 * ac, 2 * bc);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB Output is correct
2 Correct 28 ms 1144 KB Output is correct
3 Incorrect 8 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -

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 256 KB Output is correct
3 Correct 868 ms 67872 KB Output is correct
4 Correct 1430 ms 111864 KB Output is correct
5 Correct 1451 ms 111996 KB Output is correct
6 Correct 1369 ms 81784 KB Output is correct
7 Correct 1449 ms 81600 KB Output is correct
8 Correct 1068 ms 3960 KB Output is correct
9 Correct 1470 ms 111608 KB Output is correct
10 Correct 1478 ms 111944 KB Output is correct
11 Correct 1384 ms 81784 KB Output is correct
12 Correct 1222 ms 104404 KB Output is correct
13 Correct 1367 ms 111608 KB Output is correct
14 Correct 1391 ms 111892 KB Output is correct
15 Correct 1334 ms 81784 KB Output is correct
16 Correct 1002 ms 77596 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Execution timed out 3078 ms 181936 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB Output is correct
2 Correct 28 ms 1144 KB Output is correct
3 Incorrect 8 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB Output is correct
2 Correct 28 ms 1144 KB Output is correct
3 Incorrect 8 ms 640 KB Output isn't correct
4 Halted 0 ms 0 KB -