oj.uz

답안 #756510

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
756510 2023-06-11T18:34:22 Z SlavicG Sum Zero (RMI20_sumzero) C++17
100 / 100
 263 ms 20128 KB 
//not my code
#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N = 4e5 + 1;
int jump[N], p[N], level[N];
unordered_map<ll, int> f;
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    ll tot = 0;
    int mx = -1;
    level[0] = 1;
    for(int i = 1; i <= n; i++) {
        int a; cin >> a;
        tot += a;
        if(f[tot] || !tot) mx = max(mx, f[tot]);
        f[tot] = i;
        p[i] = mx;
        if(mx == -1) level[i] = 1;
        else
        level[i] = level[p[i]] + 1;
        if(mx >= 0 && level[p[i]] - level[jump[p[i]]] == level[jump[p[i]]] - level[jump[jump[p[i]]]]) jump[i] = jump[jump[p[i]]];
        else jump[i] = p[i];
    }
    int q;
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        int ans = 0; --l;
        while(r) {
            if(p[r] < l) break;
            if(jump[r] >= l) ans += level[r] - level[jump[r]], r = jump[r];
            else ans++, r = p[r];
        }
        cout << ans << "\n";
    }
 }

Compilation message

sumzero.cpp:11:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   11 | main(){
      | ^~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 53 ms 3572 KB Output is correct
8 Correct 46 ms 4060 KB Output is correct
9 Correct 56 ms 2572 KB Output is correct
10 Correct 54 ms 3496 KB Output is correct
11 Correct 45 ms 3368 KB Output is correct
12 Correct 66 ms 2508 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 53 ms 3572 KB Output is correct
8 Correct 46 ms 4060 KB Output is correct
9 Correct 56 ms 2572 KB Output is correct
10 Correct 54 ms 3496 KB Output is correct
11 Correct 45 ms 3368 KB Output is correct
12 Correct 66 ms 2508 KB Output is correct
13 Correct 258 ms 13448 KB Output is correct
14 Correct 228 ms 15764 KB Output is correct
15 Correct 254 ms 8060 KB Output is correct
16 Correct 263 ms 15956 KB Output is correct
17 Correct 235 ms 20128 KB Output is correct
18 Correct 262 ms 14756 KB Output is correct