oj.uz

답안 #756512

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
756512 2023-06-11T18:36:50 Z keta_tsimakuridze Sum Zero (RMI20_sumzero) C++14
100 / 100
 332 ms 15860 KB 
#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 + 5, mod = 1e9 + 7; // !
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:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main(){
      | ^~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 60 ms 3488 KB Output is correct
8 Correct 48 ms 4020 KB Output is correct
9 Correct 56 ms 2544 KB Output is correct
10 Correct 66 ms 3496 KB Output is correct
11 Correct 57 ms 3384 KB Output is correct
12 Correct 65 ms 2492 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 60 ms 3488 KB Output is correct
8 Correct 48 ms 4020 KB Output is correct
9 Correct 56 ms 2544 KB Output is correct
10 Correct 66 ms 3496 KB Output is correct
11 Correct 57 ms 3384 KB Output is correct
12 Correct 65 ms 2492 KB Output is correct
13 Correct 265 ms 13484 KB Output is correct
14 Correct 232 ms 15752 KB Output is correct
15 Correct 332 ms 7712 KB Output is correct
16 Correct 262 ms 15860 KB Output is correct
17 Correct 290 ms 12844 KB Output is correct
18 Correct 275 ms 7748 KB Output is correct