oj.uz

Submission #559698

# Submission time Handle Problem Language Result Execution time Memory
559698 2022-05-10T12:30:47 Z SSRS Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 395 ms 38524 KB 
#include <bits/stdc++.h>
#include "rainbow.h"
using namespace std;
int xmin, xmax, ymin, ymax;
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);
  }
};
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){
    ST2.add(P.first, P.second);
  }
  ST2.build();
  ST3 = range_tree(R + 1);
  for (auto P : st3){
    ST3.add(P.first, P.second);
  }
  ST3.build();
  ST4 = range_tree(R);
  for (auto P : st4){
    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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 6 ms 748 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 8 ms 724 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 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 1 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 6 ms 980 KB Output is correct
14 Correct 8 ms 1108 KB Output is correct
15 Runtime error 1 ms 340 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 292 ms 24104 KB Output is correct
4 Correct 361 ms 38448 KB Output is correct
5 Correct 395 ms 38240 KB Output is correct
6 Correct 354 ms 30696 KB Output is correct
7 Correct 360 ms 29576 KB Output is correct
8 Correct 69 ms 3964 KB Output is correct
9 Correct 374 ms 38524 KB Output is correct
10 Correct 390 ms 38136 KB Output is correct
11 Correct 382 ms 30700 KB Output is correct
12 Correct 338 ms 36124 KB Output is correct
13 Correct 310 ms 38400 KB Output is correct
14 Correct 379 ms 38104 KB Output is correct
15 Correct 332 ms 30696 KB Output is correct
16 Correct 290 ms 28608 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 340 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 6 ms 748 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 8 ms 724 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 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 1 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 6 ms 980 KB Output is correct
14 Correct 8 ms 1108 KB Output is correct
15 Runtime error 1 ms 340 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 6 ms 748 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 3 ms 340 KB Output is correct
5 Correct 8 ms 724 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 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 1 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 6 ms 980 KB Output is correct
14 Correct 8 ms 1108 KB Output is correct
15 Runtime error 1 ms 340 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -