Submission #635523

#	Time	Username	Problem	Language	Result	Execution time	Memory
635523		danikoynov	Sum Zero (RMI20_sumzero)	C++14	61 / 100	555 ms	30248 KiB

sumzero

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

int n, q;
ll pref[maxn];
int fr[maxn], to[maxn];
int s[maxn], tree[4 * maxn], timer, lvl[maxn], in[maxn], out[maxn];
///vector < int > g[maxn];
void trav(int v, int p)
{
    s[++ timer] = v;
    in[v] = timer;
    for (int u = to[v]; u >= fr[v]; u --)
///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);
    }


    return min(walk(root * 2, left, mid, qleft, qright, val),
               walk(root * 2 + 1, mid + 1, right, qleft, qright, val));
}

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

    for (int i = 0; i <= n + 1; i ++)
        fr[i] = n + 1;

    unordered_map < int, int > last;
    int cl = n + 1;
    to[cl] = n;
    for (int i = n; i >= 0; i --)
    {
        if (last[pref[i]] != 0)
        {
            if (last[pref[i]] < cl)
            {
                fr[cl] = i + 1;
                cl = min(cl, last[pref[i]]);
                to[cl] = i;
            }
        }

        //g[cl].push_back(i);
        //cout << i << " : " << cl << endl;
        last[pref[i]] = i;
    }
    fr[cl] = 0;





    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;
    int pos, ans, l, r;
    for (int i = 1; i <= q; i ++)
    {
        l, r;
        cin >> l >> r;
        l = l - 1;
         pos = walk(1, 1, timer, 1, in[l], r);
        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;
}
/**

*/

Compilation message (stderr)

sumzero.cpp: In function 'void solve()':
sumzero.cpp:128:9: warning: left operand of comma operator has no effect [-Wunused-value]
  128 |         l, r;
      |         ^
sumzero.cpp:128:13: warning: right operand of comma operator has no effect [-Wunused-value]
  128 |         l, r;
      |             ^

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