oj.uz

답안 #750329

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750329 2023-05-29T11:45:57 Z doowey Sum Zero (RMI20_sumzero) C++14
100 / 100
 704 ms 15880 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)4e5 + 4;
const int B = 3;
const int base = 100;

int nex[B][N];
unordered_map<ll, int> pre;
int pwr[B];

int main(){
    fastIO;
    //freopen("in.txt", "r", stdin);
    int n;
    cin >> n;
    int a;
    pre[0ll] = 0;
    pwr[0] = 1;
    nex[0][0] = -1;
    int st = -1;
    ll sum = 0;

    for(int i = 1; i <= n ; i ++ ){
        cin >> a;
        sum += a;
        if(pre.count(sum)){
            st=max(st,pre[sum]);
        }
        nex[0][i] = st;
        pre[sum]=i;
    }
    pre.clear();
    int g;
    for(int ln = 1; ln < B; ln ++ ){
        pwr[ln] = pwr[ln - 1] * base;
        for(int i = 0 ; i <= n; i ++ ){
            g = i;
            for(int j = 0 ; j < base; j ++ ){
                if(g == -1) break;
                g = nex[ln - 1][g];
            }
            nex[ln][i] = g;
        }
    }

    int q;
    cin >> q;
    int lf, rf;
    for(int iq = 1; iq <= q; iq ++ ){
        cin >> lf >> rf;
        lf -- ;
        g = 0;
        for(int ln = B - 1; ln >= 0 ; ln -- ){
            while(nex[ln][rf] >= lf){
                g += pwr[ln];
                rf = nex[ln][rf];
            }
        }
        cout << g << "\n";
    }
    return 0;
}

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 3 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 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 3 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 115 ms 3540 KB Output is correct
8 Correct 78 ms 4048 KB Output is correct
9 Correct 121 ms 2672 KB Output is correct
10 Correct 130 ms 3512 KB Output is correct
11 Correct 78 ms 3328 KB Output is correct
12 Correct 131 ms 2516 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 3 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 115 ms 3540 KB Output is correct
8 Correct 78 ms 4048 KB Output is correct
9 Correct 121 ms 2672 KB Output is correct
10 Correct 130 ms 3512 KB Output is correct
11 Correct 78 ms 3328 KB Output is correct
12 Correct 131 ms 2516 KB Output is correct
13 Correct 631 ms 13524 KB Output is correct
14 Correct 414 ms 15660 KB Output is correct
15 Correct 703 ms 7864 KB Output is correct
16 Correct 615 ms 15880 KB Output is correct
17 Correct 451 ms 12780 KB Output is correct
18 Correct 704 ms 14780 KB Output is correct