제출 #1026116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1026116		NValchanov	Sum Zero (RMI20_sumzero)	C++17	61 / 100	276 ms	62660 KiB

sumzero

#include <bits/stdc++.h>

#define endl '\n'

using namespace std;

typedef long long ll;

const int MAXN = 4e5 + 10;
const int MAXQ = 4e5 + 10;
const int MAXLOG = 22;

int n, q;
int a[MAXN];
int nxt[MAXN];
int lift[MAXN][MAXLOG];
pair < int, int > queries[MAXQ];
ll ans[MAXN];

map < ll, int > sums;

void read()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        cin >> queries[i].first >> queries[i].second;
    }
}

void fill_nxt()
{
    int minpos = MAXN - 1;
    ll cursum = 0;

    for(int i = n + 1; i >= 1; i--)
    {
        cursum += a[i];

        if(sums.find(cursum) != sums.end())
            minpos = min(minpos, sums[cursum]);

        sums[cursum] = i;
        nxt[i] = minpos;
    }
}

void solve()
{
    for(int i = 1; i <= n + 1; i++)
    {
        lift[i][0] = nxt[i];
    }
    lift[MAXN - 1][0] = MAXN - 1;
    for(int j = 1; j < MAXLOG; j++)
    {
        for(int i = 1; i <= n + 1; i++)
        {
            lift[i][j] = lift[lift[i][j - 1]][j - 1];   
        }
        lift[MAXN - 1][j] = lift[lift[MAXN - 1][j - 1]][j - 1];
    }

    for(int j = MAXLOG - 1; j >= 0; j--)
    {
        for(int i = 1; i <= q; i++)
        {
            int left = queries[i].first;
            int right = queries[i].second;

            if(lift[left][j] <= right + 1)
            {
                ans[i] += (1 << j);
                left = lift[left][j];
            }
            queries[i].first = left;
        }
    }
}

void print()
{
    for(int i = 1; i <= q; i++)
    {
        cout << ans[i] << endl;
    }
    cout << endl;
}

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    read();
    fill_nxt();
    solve();
    print();

    return 0;
}

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