Submission #1119317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119317		MateiKing80	Sum Zero (RMI20_sumzero)	C++14	100 / 100	923 ms	19016 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;

const int N = 4e5;

int tata[N + 5], ptr[N + 5], baga[N + 5];
long long a[N + 5];

int main()
{
    ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i], a[i] += a[i - 1];
    int last = n + 1;
    a[n + 2] = -1;
    a[n + 1] = 0;
    tata[n + 1] = n + 2;
    tata[n + 2] = n + 2;
    vector<int> srt(n + 1);
    for(int i = 0; i <= n; i ++)
        srt[i] = i;
    sort(srt.begin(), srt.end(), [&](int x, int y)
    {
        if(a[x] == a[y])
            return x < y;
        return a[x] < a[y];
    });
    for(int i = 0; i < n; i ++)
    {
        if(a[srt[i + 1]] == a[srt[i]])
            baga[srt[i]] = srt[i + 1];
    }
    for(int i = n; i; i --)
    {
        if(baga[i - 1])
            last = min(last, baga[i - 1]);
        tata[i] = last + 1;
        a[i] = 1 + a[last + 1];
    }
    int q;
    cin >> q;
    for(int i = n + 2; i; i --)
    {
        if(a[ptr[ptr[tata[i]]]] - a[ptr[tata[i]]] == a[ptr[tata[i]]] - a[tata[i]])
            ptr[i] = ptr[ptr[tata[i]]];
        else
            ptr[i] = tata[i];
        assert(i == n + 2 || tata[i] > i);
        assert(i == n + 2 || ptr[i] > i);
    }
    for(int i = 1; i <= q; i ++)
    {
        int l, r, li;
        cin >> l >> r;
        li = l;
        r ++;
        while(1)
        {
            if(ptr[l] <= r)
                l = ptr[l];
            else if(tata[l] <= r)
                l = tata[l];
            else
                break;
        }
        cout << a[li] - a[l] << '\n';
    }
}

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