Submission #413653

#	Time	Username	Problem	Language	Result	Execution time	Memory
413653		blue	Sum Zero (RMI20_sumzero)	C++17	61 / 100	1071 ms	65536 KiB

sumzero

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;

struct loc
{
    long long sm;
    int i;
};

bool operator < (loc A, loc B)
{
    if(A.sm == B.sm) return A.i < B.i;
    return A.sm < B.sm;
}

int main()
{
    int N;
    cin >> N;

    int nxt[N+2][21];
    for(int i = 1; i <= N+1; i++)
        for(int j = 0; j <= 20; j++)
            nxt[i][j] = N+1;

    multiset<loc> L;

    long long c[N+2];
    c[0] = 0;
    L.insert(loc{0, 0});

    for(int i = 1; i <= N; i++)
    {
        cin >> c[i];
        c[i] += c[i-1];

        L.insert(loc{c[i], i});
    }

    while(!L.empty())
    {
        vector<int> p;
        long long s = L.begin()->sm;

        while(!L.empty() && L.begin()->sm == s)
        {
            p.push_back(L.begin()->i);
            L.erase(L.begin());
        }

        for(int i = 0; i+1 < p.size(); i++)
        {
            nxt[ p[i] + 1 ][0] = p[i+1];
        }
    }
    // cerr << "check\n";
    for(int i = N; i >= 1; i--)
        nxt[i][0] = min(nxt[i][0], nxt[i+1][0]);

    // cerr << "c\n";

    for(int j = 1; j <= 20; j++)
    {
        // cerr << j << '\n';
        for(int i = 1; i <= N; i++)
            if(nxt[i][j-1] <= N)
                nxt[i][j] = nxt[ nxt[i][j-1] + 1 ][j-1];

    }

        // cerr << "chec2\n";
    int Q;
    cin >> Q;

    for(int q = 1; q <= Q; q++)
    {
        int L, R;
        cin >> L >> R;

        int res = 0;
        for(int j = 20; j >= 0; j--)
        {
            if(nxt[L][j] > R) continue;
            L = nxt[L][j] + 1;
            // cerr << (1 << j) << ' ' << L << '\n';
            res += (1 << j);
        }
        cout << res << '\n';
    }
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:54:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         for(int i = 0; i+1 < p.size(); i++)
      |                        ~~~~^~~~~~~~~~

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