제출 #1273700

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273700		nguyenbaoanh	Sum Zero (RMI20_sumzero)	C++20	22 / 100	41 ms	7784 KiB

sumzero

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 4e5 + 5;
const int mod = 1e9+7;
int n,nquery,nxt[maxn][13];
pair<ll,int> b[maxn];
int a[maxn];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i =1;i<=n;i++)
    {
        cin>>a[i];
        a[i]+=a[i-1];
        b[i] = {a[i],i};
    }
    b[0] = {0,0};
    sort(b,b+n+1);
    for(int i =0;i<n;i++)
    {
        if(b[i].first == b[i+1].first) a[b[i].second] = b[i+1].second;
        else a[b[i].second] = n+1;
    }
    a[b[n].second] = n+1;
    for(int i =0;i<=n;i++) nxt[i][0] = a[i];//bước nhảy đầu tiên
    for(int i = 0;i<13;i++) nxt[n+1][i] = n+1;
    for(int i =n;i>=0;i--)
    {
      nxt[i][0]=min(nxt[i][0],nxt[i+1][0]);//bước nhảy tiếp theo
      for(int j = 1;j<13;j++)
            nxt[i][j] = nxt[nxt[i][j-1]][j-1];//binary lifting
    }
    cin>>nquery;
    while(nquery--)
    {
        int l,r,res=0;
        cin>>l>>r;
        l--;
        for(int  i = 12;i>=0;i--)
        {
            if(nxt[l][i]<=r)
            {
               l = nxt[l][i];
               res += (1ll<<i);//Cộng dồn kết quả theo bước nhảy
            }
        }
        cout<<res<<'\n';
    }
    return 0;
}

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