oj.uz

답안 #559698

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559698 2022-05-10T12:30:47 Z SSRS 무지개나라 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -