oj.uz

Submission #624402

# Submission time Handle Problem Language Result Execution time Memory
624402 2022-08-08T07:26:17 Z boris_mihov Sum Zero (RMI20_sumzero) C++14
100 / 100
 766 ms 20136 KB 
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 400000 + 10;
const int MAXLOG = 3;
const int BASE = 100;

std::unordered_map < llong,int > cnt;
int sparse[MAXLOG][MAXN];
int n, q;

void buildSparse()
{
    for (int log = 1 ; log <= MAXLOG-1 ; ++log)
    {
        sparse[log][0] = -1;
        for (int i = 1 ; i <= n ; ++i)
        {
            sparse[log][i] = i;
            for (int j = 1 ; j <= BASE ; ++j)
            {
                sparse[log][i] = sparse[log-1][sparse[log][i]];
                if (sparse[log][i] == -1) break;
            }
        }
    }
}

int ans, pw;
int lifting(int from, const int &to)
{
    ans = 0;
    pw = 10000;
    for (int log = MAXLOG-1 ; log >= 0 ; --log)
    {
        while (sparse[log][from] >= to-1)
        {
            ans += pw;
            from = sparse[log][from];
        }
    
        pw /= BASE;
    }

    return ans;
}

void solve()
{
    int l, r;
    buildSparse();
    std::cin >> q;
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> l >> r;
        std::cout << lifting(r, l) << '\n';
    }
}

void read()
{
    cnt[0] = 1;
    sparse[0][0] = -1;

    int curr;
    llong sum = 0;
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> curr;
        sum += curr;

        sparse[0][i] = std::max(sparse[0][i-1], cnt[sum] - 1);
        cnt[sum] = i + 1;
    }
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 560 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 560 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 114 ms 3556 KB Output is correct
8 Correct 81 ms 4028 KB Output is correct
9 Correct 122 ms 2516 KB Output is correct
10 Correct 107 ms 3444 KB Output is correct
11 Correct 87 ms 3428 KB Output is correct
12 Correct 125 ms 2500 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 4 ms 560 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 5 ms 468 KB Output is correct
7 Correct 114 ms 3556 KB Output is correct
8 Correct 81 ms 4028 KB Output is correct
9 Correct 122 ms 2516 KB Output is correct
10 Correct 107 ms 3444 KB Output is correct
11 Correct 87 ms 3428 KB Output is correct
12 Correct 125 ms 2500 KB Output is correct
13 Correct 600 ms 13384 KB Output is correct
14 Correct 478 ms 15652 KB Output is correct
15 Correct 759 ms 8024 KB Output is correct
16 Correct 637 ms 15856 KB Output is correct
17 Correct 461 ms 20136 KB Output is correct
18 Correct 766 ms 14700 KB Output is correct