Submission #635492

#	Time	Username	Problem	Language	Result	Execution time	Memory
635492		danikoynov	Sum Zero (RMI20_sumzero)	C++14	61 / 100	621 ms	44420 KiB

sumzero

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;

int n, q;
ll pref[maxn];
vector < int > g[maxn];
int s[maxn], tree[4 * maxn], timer, lvl[maxn], in[maxn], out[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);
    }
    out[v] = timer;
}

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;
}

bool in_subtree(int v, int u)
{
    if (in[u] <= in[v] && out[u] >= out[v])
        return true;
    return false;
}
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);
        int ans = lvl[l] - lvl[pos] - 1;
        if (!in_subtree(l, pos))
            ans ++;
        cout << ans << 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;
}
/**

*/

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