oj.uz

답안 #401960

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
401960 2021-05-11T04:21:04 Z rama_pang Sum Zero (RMI20_sumzero) C++17
100 / 100
 702 ms 17920 KB 
#include <bits/stdc++.h>
using namespace std;

const int BASE = 32;
const int LOG32 = 4;

int pow32[LOG32];
int dp[400005][LOG32];

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  pow32[0] = 1;
  for (int i = 1; i < LOG32; i++) {
    pow32[i] = BASE * pow32[i - 1];
  }

  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  // dp[i][x] = minimum j, such that [i, j - 1] contains 6^x valid segments
  { // Compute dp[]
    for (int i = 0; i <= N + 1; i++) {
      for (int j = 0; j < LOG32; j++) {
        dp[i][j] = N + 1;
      }
    }
    long long sum = 0;
    vector<long long> coords;
    coords.emplace_back(sum);
    for (int i = N - 1; i >= 0; i--) {
      sum += A[i];
      coords.emplace_back(sum);
    }
    sort(begin(coords), end(coords));
    coords.resize(unique(begin(coords), end(coords)) - begin(coords));

    sum = 0;
    vector<int> last(coords.size(), N + 1);
    const auto Get = [&](long long x) {
      return lower_bound(begin(coords), end(coords), x) - begin(coords);
    };
    last[Get(sum)] = N;
    for (int i = N - 1; i >= 0; i--) {
      sum += A[i];
      dp[i][0] = last[Get(sum)];
      last[Get(sum)] = i;
    }
    for (int i = N - 2; i >= 0; i--) {
      dp[i][0] = min(dp[i][0], dp[i + 1][0]);
    }
    for (int j = 1; j < LOG32; j++) {
      for (int i = 0; i < N; i++) {
        int x = i;
        for (int k = 0; k < BASE; k++) {
          x = dp[x][j - 1];
        }
        dp[i][j] = x;
      }
    }
  }

  int Q;
  cin >> Q;
  while (Q--) {
    int L, R;
    cin >> L >> R;
    L--;
    int ans = 0;
    int x = LOG32 - 1;
    while (x >= 0) {
      if (dp[L][x] <= R) {
        ans += pow32[x];
        L = dp[L][x];
      } else {
        x--;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 5 ms 460 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 5 ms 536 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 5 ms 460 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 5 ms 536 KB Output is correct
7 Correct 112 ms 3424 KB Output is correct
8 Correct 100 ms 3404 KB Output is correct
9 Correct 130 ms 3416 KB Output is correct
10 Correct 125 ms 3404 KB Output is correct
11 Correct 101 ms 3404 KB Output is correct
12 Correct 146 ms 3404 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 460 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Correct 5 ms 460 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 5 ms 460 KB Output is correct
6 Correct 5 ms 536 KB Output is correct
7 Correct 112 ms 3424 KB Output is correct
8 Correct 100 ms 3404 KB Output is correct
9 Correct 130 ms 3416 KB Output is correct
10 Correct 125 ms 3404 KB Output is correct
11 Correct 101 ms 3404 KB Output is correct
12 Correct 146 ms 3404 KB Output is correct
13 Correct 631 ms 12384 KB Output is correct
14 Correct 520 ms 12348 KB Output is correct
15 Correct 684 ms 12380 KB Output is correct
16 Correct 657 ms 17180 KB Output is correct
17 Correct 499 ms 17920 KB Output is correct
18 Correct 702 ms 17380 KB Output is correct