oj.uz

Submission #636569

# Submission time Handle Problem Language Result Execution time Memory
636569 2022-08-29T15:03:31 Z danikoynov Sum Zero (RMI20_sumzero) C++14
100 / 100
 748 ms 20156 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10, maxlog = 3, base = 100;

int n, dp[maxlog][maxn], q;
void solve()
{
    cin >> n;
    ll x, sum = 0;
    int cl = -1;
        unordered_map < ll, int > last;
    for (int i = 1; i <= n; i ++)
    {
        cin >> x;
        sum = sum + x;
        if (last[sum] != 0 || sum == 0)
        cl = max(cl, last[sum]);
        last[sum] = i;
        dp[0][i] = cl;
    }
    dp[0][0] = -1;

    for (int j = 1; j < maxlog; j ++)
    {
        dp[j][0] = -1;
        for (int i = 1; i <= n; i ++)
        {
            dp[j][i] = dp[j - 1][i];
            for (int f = 1; f < base && dp[j][i] != -1; f ++)
                dp[j][i] = dp[j - 1][dp[j][i]];
        }
    }

    /**for (int j = 0; j < 4; j ++, cout << endl)
        for (int i = 0; i <= n; i ++)
        cout << dp[i][j] << " ";*/

    cin >> q;
    int l, r, jump, st, bit, f;
    for (int i = 1; i <= q; i ++)
    {
        cin >> l >> r;
        jump = 0, st = 1;
        for (bit = 1; bit < maxlog; bit ++)
            st = st * base;
        for ( bit = maxlog - 1; bit >= 0; bit --)
        {
            //cout << l << " " << jump << endl;
            while(dp[bit][r] >= l - 1)
            {
                jump += st;
                r = dp[bit][r];
            }
            st /= base;
        }
        cout << jump << endl;
    }
}
void speed()
{
    ios_base::sync_with_stdio((false));
    cin.tie(NULL);
    cout.tie(NULL);
}
int main()
{
    speed();
    ///freopen("input.txt", "r", stdin);
    solve();
    return 0;
}
/**

*/

Compilation message

sumzero.cpp: In function 'void solve()':
sumzero.cpp:41:30: warning: unused variable 'f' [-Wunused-variable]
   41 |     int l, r, jump, st, bit, f;
      |                              ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 4 ms 480 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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 4 ms 480 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 111 ms 3508 KB Output is correct
8 Correct 83 ms 4016 KB Output is correct
9 Correct 128 ms 2568 KB Output is correct
10 Correct 111 ms 3508 KB Output is correct
11 Correct 75 ms 3368 KB Output is correct
12 Correct 124 ms 2520 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 4 ms 480 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 111 ms 3508 KB Output is correct
8 Correct 83 ms 4016 KB Output is correct
9 Correct 128 ms 2568 KB Output is correct
10 Correct 111 ms 3508 KB Output is correct
11 Correct 75 ms 3368 KB Output is correct
12 Correct 124 ms 2520 KB Output is correct
13 Correct 588 ms 13520 KB Output is correct
14 Correct 446 ms 15688 KB Output is correct
15 Correct 748 ms 7728 KB Output is correct
16 Correct 623 ms 15780 KB Output is correct
17 Correct 452 ms 20156 KB Output is correct
18 Correct 724 ms 14924 KB Output is correct