Submission #635473

#	Time	Username	Problem	Language	Result	Execution time	Memory
635473		danikoynov	Sum Zero (RMI20_sumzero)	C++14	0 / 100	18 ms	10068 KiB

sumzero

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10, maxlog = 19;

int n, q;
ll pref[maxn];
vector < int > g[maxn];
int s[maxn], tree[4 * maxn], timer, lvl[maxn], in[maxn];

void trav(int v, int p)
{
    s[++ timer] = v;
    in[v] = timer;
    for (int u : g[v])
    {
        if (u == p)
            continue;
            lvl[u] = lvl[v] + 1;
        trav(u, v);
    }
}

void make_tree(int root, int left, int right)
{
    ///cout << root << " - " << left << " - " << right << endl;
    if (left == right)
    {
        tree[root] = s[left];

        return;
    }

    int mid = (left + right) / 2;
    make_tree(root * 2, left, mid);
    make_tree(root * 2 + 1, mid + 1, right);

    tree[root] = max(tree[root * 2], tree[root * 2 + 1]);
}

int walk(int root, int left, int right, int qleft, int qright, int val)
{
///cout << root << " - " << left << " - " << right << endl;
    if (left > qright || right < qleft)
        return n + 1;

    int mid = (left + right) / 2;
    if (left >= qleft && right <= qright)
    {
        if (left == right)
        {
            if (tree[root] > val)
            {
                return tree[root];
            }
            else
                return n + 1;
        }

        if (tree[root * 2 + 1] > val)
            return walk(root * 2 + 1, mid + 1, right, qleft, qright, val);
        return walk(root * 2, left,  mid, qleft, qright, val);
    }


    int x = min(walk(root * 2, left, mid, qleft, qright, val),
               walk(root * 2 + 1, mid + 1, right, qleft, qright, val));

    return x;
}

void solve()
{
    cin >> n;
    ll x;
    for (int i = 1; i <= n; i ++)
    {
        cin >> x;
        pref[i] = pref[i - 1] + x;
    }

    map < int, int > last;
    int cl = n + 1;
    for (int i = n; i >= 0; i --)
    {
        if (last[pref[i]] != 0)
        cl = min(cl, last[pref[i]]);
        g[cl].push_back(i);
        //cout << i << " : " << cl << endl;
        last[pref[i]] = i;
    }

    trav(n + 1, -1);
    make_tree(1, 1, timer);
    /**for (int i = 1; i <= timer; i ++)
        cout << s[i] << " ";
    cout << endl;*/

    ///cout << walk(1, 1, timer, 1, in[2], 9) << endl;
    cin >> q;
    for (int i = 1; i <= q; i ++)
    {
        int l, r;
        cin >> l >> r;
        l = l - 1;
        int pos = walk(1, 1, timer, 1, in[l], r);
        cout << lvl[l] - lvl[pos]  - 1 << endl;
    }
}
int main()
{
    //freopen("input.txt", "r", stdin);
    solve();
   return 0;
}
/**

*/

Compilation message (stderr)

sumzero.cpp: In function 'void trav(int, int)':
sumzero.cpp:18:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   18 |         if (u == p)
      |         ^~
sumzero.cpp:20:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   20 |             lvl[u] = lvl[v] + 1;
      |             ^~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39