oj.uz

Submission #562644

# Submission time Handle Problem Language Result Execution time Memory
562644 2022-05-14T20:48:43 Z SSRS Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 1330 ms 142944 KB 
#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
struct range_tree{
  int N;
  vector<vector<int>> ST;
  range_tree(){
  }
  range_tree(int N2){
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST = vector<vector<int>>(N * 2 - 1);
  }
  void add(int X, int Y){
    X += N - 1;
    ST[X].push_back(Y);
    while (X > 0){
      X = (X - 1) / 2;
      ST[X].push_back(Y);
    }
  }
  void build(){
    for (int i = 0; i < N * 2 - 1; i++){
      sort(ST[i].begin(), ST[i].end());
    }
  }
  int rectangle_sum(int L, int R, int U, int D, int i, int l, int r){
    if (r <= L || R <= l){
      return 0;
    } else if (L <= l && r <= R){
      return lower_bound(ST[i].begin(), ST[i].end(), D) - lower_bound(ST[i].begin(), ST[i].end(), U);
    } else {
      int m = (l + r) / 2;
      return rectangle_sum(L, R, U, D, i * 2 + 1, l, m) + rectangle_sum(L, R, U, D, i * 2 + 2, m, r);
    }
  }
  int rectangle_sum(int L, int R, int U, int D){
    return rectangle_sum(L, R, U, D, 0, 0, N);
  }
};
int xmin, xmax, ymin, ymax;
range_tree ST1, ST2, ST3, ST4;
void init(int R, int C, int sr, int sc, int M, char *S){
  sr--;
  sc--;
  vector<int> x(M + 1), y(M + 1);
  x[0] = sr;
  y[0] = sc;
  for (int i = 0; i < M; i++){
    x[i + 1] = x[i];
    y[i + 1] = y[i];
    if (S[i] == 'N'){
      x[i + 1]--;
    }
    if (S[i] == 'S'){
      x[i + 1]++;
    }
    if (S[i] == 'E'){
      y[i + 1]++;
    }
    if (S[i] == 'W'){
      y[i + 1]--;
    }
  }
  xmin = sr;
  xmax = sr;
  ymin = sc;
  ymax = sc;
  for (int i = 1; i <= M; i++){
    xmin = min(xmin, x[i]);
    xmax = max(xmax, x[i]);
    ymin = min(ymin, y[i]);
    ymax = max(ymax, y[i]);
  }
  set<pair<int, int>> st1, st2, st3, st4;
  for (int i = 0; i <= M; i++){
    st1.insert(make_pair(x[i], y[i]));
    st2.insert(make_pair(x[i], y[i]));
    st2.insert(make_pair(x[i] - 1, y[i]));
    st3.insert(make_pair(x[i], y[i]));
    st3.insert(make_pair(x[i], y[i] - 1));
    st4.insert(make_pair(x[i], y[i]));
    st4.insert(make_pair(x[i] - 1, y[i]));
    st4.insert(make_pair(x[i], y[i] - 1));
    st4.insert(make_pair(x[i] - 1, y[i] - 1));
  }
  ST1 = range_tree(R + 1);
  for (auto P : st1){
    ST1.add(P.first, P.second);
  }
  ST1.build();
  ST2 = range_tree(R);
  for (auto P : st2){
    if (P.first >= 0){
      ST2.add(P.first, P.second);
    }
  }
  ST2.build();
  ST3 = range_tree(R + 1);
  for (auto P : st3){
    if (P.second >= 0){
      ST3.add(P.first, P.second);
    }
  }
  ST3.build();
  ST4 = range_tree(R);
  for (auto P : st4){
    if (P.first >= 0 && P.second >= 0){
      ST4.add(P.first, P.second);
    }
  }
  ST4.build();
}
int colour(int ar, int ac, int br, int bc){
  ar--;
  ac--;
  int ans = 1;
  ans -= ST1.rectangle_sum(ar, br, ac, bc);
  ans += ST2.rectangle_sum(ar, br - 1, ac, bc);
  ans += ST3.rectangle_sum(ar, br, ac, bc - 1);
  ans -= ST4.rectangle_sum(ar, br - 1, ac, bc - 1);
  if (ar < xmin && xmax < br - 1 && ac < ymin && ymax < bc - 1){
    ans++;
  }
  return ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 6 ms 724 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 5 ms 596 KB Output is correct
13 Correct 7 ms 980 KB Output is correct
14 Correct 9 ms 1144 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 284 ms 21452 KB Output is correct
4 Correct 394 ms 35500 KB Output is correct
5 Correct 464 ms 35168 KB Output is correct
6 Correct 360 ms 27172 KB Output is correct
7 Correct 398 ms 26740 KB Output is correct
8 Correct 79 ms 1432 KB Output is correct
9 Correct 373 ms 35564 KB Output is correct
10 Correct 394 ms 35216 KB Output is correct
11 Correct 385 ms 27204 KB Output is correct
12 Correct 314 ms 33260 KB Output is correct
13 Correct 317 ms 35628 KB Output is correct
14 Correct 328 ms 35116 KB Output is correct
15 Correct 318 ms 27328 KB Output is correct
16 Correct 282 ms 25296 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 973 ms 129688 KB Output is correct
3 Correct 527 ms 140796 KB Output is correct
4 Correct 482 ms 135376 KB Output is correct
5 Correct 473 ms 114732 KB Output is correct
6 Correct 191 ms 65864 KB Output is correct
7 Correct 347 ms 80464 KB Output is correct
8 Correct 284 ms 35296 KB Output is correct
9 Correct 320 ms 32848 KB Output is correct
10 Correct 160 ms 41388 KB Output is correct
11 Correct 373 ms 65280 KB Output is correct
12 Correct 954 ms 129676 KB Output is correct
13 Correct 552 ms 140844 KB Output is correct
14 Correct 485 ms 135364 KB Output is correct
15 Correct 470 ms 114664 KB Output is correct
16 Correct 169 ms 62988 KB Output is correct
17 Correct 332 ms 81516 KB Output is correct
18 Correct 652 ms 130956 KB Output is correct
19 Correct 642 ms 130268 KB Output is correct
20 Correct 707 ms 129936 KB Output is correct
21 Correct 307 ms 35248 KB Output is correct
22 Correct 319 ms 32908 KB Output is correct
23 Correct 165 ms 41488 KB Output is correct
24 Correct 391 ms 65272 KB Output is correct
25 Correct 991 ms 129692 KB Output is correct
26 Correct 538 ms 140980 KB Output is correct
27 Correct 477 ms 135512 KB Output is correct
28 Correct 491 ms 114712 KB Output is correct
29 Correct 172 ms 62888 KB Output is correct
30 Correct 314 ms 81312 KB Output is correct
31 Correct 619 ms 131000 KB Output is correct
32 Correct 681 ms 130224 KB Output is correct
33 Correct 645 ms 129932 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 6 ms 724 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 5 ms 596 KB Output is correct
13 Correct 7 ms 980 KB Output is correct
14 Correct 9 ms 1144 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1016 ms 31740 KB Output is correct
19 Correct 152 ms 2248 KB Output is correct
20 Correct 169 ms 1300 KB Output is correct
21 Correct 161 ms 1468 KB Output is correct
22 Correct 171 ms 1868 KB Output is correct
23 Correct 145 ms 2136 KB Output is correct
24 Correct 200 ms 1324 KB Output is correct
25 Correct 213 ms 1708 KB Output is correct
26 Correct 189 ms 2000 KB Output is correct
27 Correct 561 ms 26216 KB Output is correct
28 Correct 417 ms 13348 KB Output is correct
29 Correct 521 ms 23880 KB Output is correct
30 Correct 975 ms 60372 KB Output is correct
31 Correct 3 ms 340 KB Output is correct
32 Correct 752 ms 27532 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 6 ms 724 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 6 ms 724 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 5 ms 596 KB Output is correct
13 Correct 7 ms 980 KB Output is correct
14 Correct 9 ms 1144 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1016 ms 31740 KB Output is correct
19 Correct 152 ms 2248 KB Output is correct
20 Correct 169 ms 1300 KB Output is correct
21 Correct 161 ms 1468 KB Output is correct
22 Correct 171 ms 1868 KB Output is correct
23 Correct 145 ms 2136 KB Output is correct
24 Correct 200 ms 1324 KB Output is correct
25 Correct 213 ms 1708 KB Output is correct
26 Correct 189 ms 2000 KB Output is correct
27 Correct 561 ms 26216 KB Output is correct
28 Correct 417 ms 13348 KB Output is correct
29 Correct 521 ms 23880 KB Output is correct
30 Correct 975 ms 60372 KB Output is correct
31 Correct 3 ms 340 KB Output is correct
32 Correct 752 ms 27532 KB Output is correct
33 Correct 973 ms 129688 KB Output is correct
34 Correct 527 ms 140796 KB Output is correct
35 Correct 482 ms 135376 KB Output is correct
36 Correct 473 ms 114732 KB Output is correct
37 Correct 191 ms 65864 KB Output is correct
38 Correct 347 ms 80464 KB Output is correct
39 Correct 284 ms 35296 KB Output is correct
40 Correct 320 ms 32848 KB Output is correct
41 Correct 160 ms 41388 KB Output is correct
42 Correct 373 ms 65280 KB Output is correct
43 Correct 954 ms 129676 KB Output is correct
44 Correct 552 ms 140844 KB Output is correct
45 Correct 485 ms 135364 KB Output is correct
46 Correct 470 ms 114664 KB Output is correct
47 Correct 169 ms 62988 KB Output is correct
48 Correct 332 ms 81516 KB Output is correct
49 Correct 652 ms 130956 KB Output is correct
50 Correct 642 ms 130268 KB Output is correct
51 Correct 707 ms 129936 KB Output is correct
52 Correct 307 ms 35248 KB Output is correct
53 Correct 319 ms 32908 KB Output is correct
54 Correct 165 ms 41488 KB Output is correct
55 Correct 391 ms 65272 KB Output is correct
56 Correct 991 ms 129692 KB Output is correct
57 Correct 538 ms 140980 KB Output is correct
58 Correct 477 ms 135512 KB Output is correct
59 Correct 491 ms 114712 KB Output is correct
60 Correct 172 ms 62888 KB Output is correct
61 Correct 314 ms 81312 KB Output is correct
62 Correct 619 ms 131000 KB Output is correct
63 Correct 681 ms 130224 KB Output is correct
64 Correct 645 ms 129932 KB Output is correct
65 Correct 284 ms 21452 KB Output is correct
66 Correct 394 ms 35500 KB Output is correct
67 Correct 464 ms 35168 KB Output is correct
68 Correct 360 ms 27172 KB Output is correct
69 Correct 398 ms 26740 KB Output is correct
70 Correct 79 ms 1432 KB Output is correct
71 Correct 373 ms 35564 KB Output is correct
72 Correct 394 ms 35216 KB Output is correct
73 Correct 385 ms 27204 KB Output is correct
74 Correct 314 ms 33260 KB Output is correct
75 Correct 317 ms 35628 KB Output is correct
76 Correct 328 ms 35116 KB Output is correct
77 Correct 318 ms 27328 KB Output is correct
78 Correct 282 ms 25296 KB Output is correct
79 Correct 514 ms 36784 KB Output is correct
80 Correct 564 ms 34904 KB Output is correct
81 Correct 448 ms 43768 KB Output is correct
82 Correct 691 ms 67264 KB Output is correct
83 Correct 1330 ms 131824 KB Output is correct
84 Correct 1155 ms 142944 KB Output is correct
85 Correct 874 ms 137480 KB Output is correct
86 Correct 918 ms 116752 KB Output is correct
87 Correct 476 ms 64828 KB Output is correct
88 Correct 692 ms 83316 KB Output is correct
89 Correct 943 ms 132968 KB Output is correct
90 Correct 1111 ms 132036 KB Output is correct
91 Correct 1173 ms 131896 KB Output is correct