oj.uz

답안 #942622

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
942622 2024-03-11T01:31:22 Z adaawf Sum Zero (RMI20_sumzero) C++17
100 / 100
 939 ms 19780 KB 
#include <iostream>
#include <algorithm>
using namespace std;
int l[400005][2], f[400005];
pair<long long int, int> c[400005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    long long int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        c[i] = {c[i - 1].first + x, i};
        f[i] = -1e9;
    }
    sort(c, c + n + 1);
    for (int i = 1; i <= n; i++) {
        if (c[i].first == c[i - 1].first) {
            f[c[i].second] = c[i - 1].second;
        }
    }
    f[0] = l[0][0] = -1;
    for (int i = 1; i <= n; i++) {
        f[i] = max(f[i - 1], f[i]);
        l[i][0] = f[i];
    }
    for (int j = 0; j <= n; j++) {
        int h = j;
        for (int k = 0; k < 400; k++) {
            if (h == -1 || l[h][0] == -1) {
                h = -1;
                break;
            }
            else h = l[h][0];
        }
        l[j][1] = h;
    }
    int q;
    cin >> q;
    for (int jj = 0; jj < q; jj++) {
        int x, y, res = 0;
        cin >> x >> y;
        for (int i = 1; i >= 0; i--) {
            if (y < x) break;
            int c = 1;
            for (int j = 1; j <= i; j++) c *= 400;
            while (l[y][i] >= x - 1) {
                y = l[y][i];
                res += c;
            }
        }
        cout << res << '\n';
    }
}

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4440 KB Output is correct
2 Correct 4 ms 4440 KB Output is correct
3 Correct 6 ms 4444 KB Output is correct
4 Correct 7 ms 4660 KB Output is correct
5 Correct 4 ms 4444 KB Output is correct
6 Correct 6 ms 4648 KB Output is correct
7 Correct 144 ms 9100 KB Output is correct
8 Correct 141 ms 9324 KB Output is correct
9 Correct 162 ms 9296 KB Output is correct
10 Correct 141 ms 9108 KB Output is correct
11 Correct 150 ms 9096 KB Output is correct
12 Correct 166 ms 9296 KB Output is correct

Subtask #3
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4440 KB Output is correct
2 Correct 4 ms 4440 KB Output is correct
3 Correct 6 ms 4444 KB Output is correct
4 Correct 7 ms 4660 KB Output is correct
5 Correct 4 ms 4444 KB Output is correct
6 Correct 6 ms 4648 KB Output is correct
7 Correct 144 ms 9100 KB Output is correct
8 Correct 141 ms 9324 KB Output is correct
9 Correct 162 ms 9296 KB Output is correct
10 Correct 141 ms 9108 KB Output is correct
11 Correct 150 ms 9096 KB Output is correct
12 Correct 166 ms 9296 KB Output is correct
13 Correct 801 ms 13444 KB Output is correct
14 Correct 634 ms 13220 KB Output is correct
15 Correct 901 ms 13756 KB Output is correct
16 Correct 734 ms 13264 KB Output is correct
17 Correct 675 ms 12932 KB Output is correct
18 Correct 939 ms 19780 KB Output is correct