oj.uz

Submission #964644

# Submission time Handle Problem Language Result Execution time Memory
964644 2024-04-17T09:07:44 Z Soumya1 Land of the Rainbow Gold (APIO17_rainbow) C++17
12 / 100
 220 ms 103600 KB 
#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());
      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;
bool has(int x, int y) {
  return binary_search(all.begin(), all.end(), pair<int, int> {x, y});
}
void init(int R, int C, int sr, int sc, int M, char *S) {
  N = R;
  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(R);
  for (auto [x, y] : all) {
    point.insert(1, 1, R, x, y);
    if (has(x, y + 1)) {
      edger.insert(1, 1, R, x, y);
    }
    if (has(x + 1, y)) {
      edged.insert(1, 1, R, x, y);
    }
    if (has(x + 1, y) && has(x, y + 1) && has(x + 1, y + 1)) {
      f.insert(1, 1, R, x, y);
    }
  }
  point.build(1, 1, R);
  edger.build(1, 1, R);
  edged.build(1, 1, R);
  f.build(1, 1, R);
}
int colour(int ar, int ac, int br, int bc) {
  int nodes = 2 * (br - ar + bc - ac + 4) + point.sum(1, 1, N, ar, br, ac, bc);
  int edges = edger.sum(1, 1, N, ar, br, ac, bc - 1) + edged.sum(1, 1, N, ar, br - 1, ac, bc);
  edges += point.sum(1, 1, N, ar, ar, ac, bc) + point.sum(1, 1, N, br, br, ac, bc);
  edges += point.sum(1, 1, N, ar, br, ac, ac) + point.sum(1, 1, N, ar, br, bc, bc);
  edges += 2 * (br - ar + bc - ac + 4);
  int comp = 1;
  if (ar < mnr && mxr < br && ac < mnc && mxc < bc) comp++;
  int bad_faces = f.sum(1, 1, N, ar, br - 1, ac, bc - 1);
  bad_faces += edged.sum(1, 1, N, ar, br - 1, ac, ac);
  bad_faces += edged.sum(1, 1, N, ar, br - 1, bc, bc);
  bad_faces += edger.sum(1, 1, N, ar, ar, ac, bc - 1);
  bad_faces += edger.sum(1, 1, N, br, br, ac, bc - 1);
  bad_faces += has(ar, ac) + has(ar, bc) + has(br, ac) + has(br, bc);
  return edges - nodes + comp - bad_faces;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 141 ms 5876 KB Output is correct
4 Correct 208 ms 6972 KB Output is correct
5 Correct 198 ms 7000 KB Output is correct
6 Correct 172 ms 7088 KB Output is correct
7 Correct 192 ms 6348 KB Output is correct
8 Correct 66 ms 4868 KB Output is correct
9 Correct 203 ms 7080 KB Output is correct
10 Correct 220 ms 7112 KB Output is correct
11 Correct 180 ms 7104 KB Output is correct
12 Correct 96 ms 6744 KB Output is correct
13 Correct 94 ms 7072 KB Output is correct
14 Correct 104 ms 6848 KB Output is correct
15 Correct 103 ms 7112 KB Output is correct
16 Correct 147 ms 6176 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 86 ms 91408 KB Output is correct
3 Correct 113 ms 103600 KB Output is correct
4 Correct 102 ms 100552 KB Output is correct
5 Correct 77 ms 93776 KB Output is correct
6 Correct 63 ms 84180 KB Output is correct
7 Incorrect 73 ms 91552 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -