oj.uz

답안 #862534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
862534 2023-10-18T12:57:24 Z blackslex Sum Zero (RMI20_sumzero) C++17
100 / 100
 233 ms 20252 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 4e5 + 1;
int n, q, x, y, cur = -1, par[N], dep[N], lf[N];
ll a;
unordered_map<ll, int> mp;

void solve() {
    scanf("%d %d", &x, &y);
    int ans = 0; x--;
    while (y && par[y] >= x) ans += (lf[y] >= x ? dep[y] - dep[lf[y]] : 1), y = (lf[y] >= x ? lf[y] : par[y]);
    printf("%d\n", ans);
}

int main() {
    scanf("%d", &n); dep[0] = 1;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x); a += x;
        if (!a || mp[a]) cur = max(cur, mp[a]);
        mp[a] = i; par[i] = cur; dep[i] = (~cur ? dep[par[i]] + 1 : 1); lf[i] = (~cur && dep[par[i]] - dep[lf[par[i]]] == dep[lf[par[i]]] - dep[lf[lf[par[i]]]] ? lf[lf[par[i]]] : par[i]);
    }
    scanf("%d", &q);
    while (q--) solve();
}

Compilation message

sumzero.cpp: In function 'void solve()':
sumzero.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     scanf("%d %d", &x, &y);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sumzero.cpp: In function 'int main()':
sumzero.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d", &n); dep[0] = 1;
      |     ~~~~~^~~~~~~~~~
sumzero.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d", &x); a += x;
      |         ~~~~~^~~~~~~~~~
sumzero.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 3 ms 4440 KB Output is correct
6 Correct 3 ms 4952 KB Output is correct
7 Correct 48 ms 6572 KB Output is correct
8 Correct 44 ms 7268 KB Output is correct
9 Correct 51 ms 5716 KB Output is correct
10 Correct 47 ms 6664 KB Output is correct
11 Correct 42 ms 6584 KB Output is correct
12 Correct 51 ms 5576 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 3 ms 4700 KB Output is correct
4 Correct 3 ms 4444 KB Output is correct
5 Correct 3 ms 4440 KB Output is correct
6 Correct 3 ms 4952 KB Output is correct
7 Correct 48 ms 6572 KB Output is correct
8 Correct 44 ms 7268 KB Output is correct
9 Correct 51 ms 5716 KB Output is correct
10 Correct 47 ms 6664 KB Output is correct
11 Correct 42 ms 6584 KB Output is correct
12 Correct 51 ms 5576 KB Output is correct
13 Correct 217 ms 13408 KB Output is correct
14 Correct 206 ms 15732 KB Output is correct
15 Correct 222 ms 7888 KB Output is correct
16 Correct 222 ms 16116 KB Output is correct
17 Correct 198 ms 20252 KB Output is correct
18 Correct 233 ms 14928 KB Output is correct