제출 #1038876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038876		DangKhoizzzz	Sum Zero (RMI20_sumzero)	C++14	0 / 100	30 ms	65536 KiB

sumzero

#include <bits/stdc++.h>
#define ll long long
 
using namespace std;
const int maxn = 1e6 + 7;
 
int n , q , a[maxn] , nxt[maxn] , pos[maxn][25];
ll sufsum[maxn];
 
void buildnext()
{
    for(int i = n; i >= 1; i--)
    {
        sufsum[i] = sufsum[i+1] + a[i];
    }
 
    unordered_map <ll , int> sumpos;
    sumpos[0] = n+1;
    nxt[n+1] = n+1;
 
    /*next[i] = j (j nho nhat)
      sao cho ton tai i <= k <= j sao cho sum[k...j] = 0
    */
 
    for(int i = n; i >= 1; i--)
    {
        if(!sumpos.count(sufsum[i])) nxt[i] = nxt[i+1];
        else nxt[i] = min(nxt[i+1] , sumpos[sufsum[i]] - 1);
        sumpos[sufsum[i]] = i;
    }
}
 
void preprocess()// pos[i][j] la vi tri cuoi cung sau khi buoc 2^j buoc
{
    for(int i = 0; i < maxn; i++)
    {
        fill(pos[i] , pos[i] + 25 , n+1);
    }
 
    for(int i = 1; i <= n; i++) pos[i][0] = nxt[i];
 
    for(int j = 1; j <= 20; j++)
    {
        for(int i = 1; i <= n; i++) pos[i][j] = n+1;
        for(int i = 1; i <= n; i++)
        {
            pos[i][j] = pos[pos[i][j-1]+1][j-1];
        }
    }
}
 
void solve()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    buildnext();
    preprocess();

    cin >> q;
    
    while(q--)
    {
        int l , r , cur , cnt = 0;
        cin >> l >> r;
 
        cur = l;
 
        for(int i = 19; i >= 0; i--)
        {
            if(pos[cur][i] <= r)
            {
                cnt += (1 << i);
                cur = pos[cur][i] + 1;
            }
        }
        cout << cnt << '\n';
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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