oj.uz

답안 #968919

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
968919 2024-04-24T09:40:57 Z 12345678 Sum Zero (RMI20_sumzero) C++17
0 / 100
 3 ms 4700 KB 
#include <bits/stdc++.h>

using namespace std;

const int nx=4e5+5, kx=19;

#define ll long long

int n, q, a[nx], L, R, vl[nx], dp[nx];
map<ll, int> mp;
ll qs;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<=n;i ++) cin>>a[i];
    mp[0]=1;
    for (int i=1; i<=n; i++)
    {
        qs+=a[i];
        if (mp.find(qs)!=mp.end()) vl[i]=mp[qs];
        mp[qs]=i+1;
    }
    for (int i=1; i<=n; i++) vl[i]=max(vl[i], vl[i-1]);
    for (int i=1; i<=n; i++) if (vl[i]) dp[i]=dp[vl[i]-1]+1;
    cin>>q;
    while (q--)
    {
        cin>>L>>R;
        if (dp[R]==0) cout<<0<<'\n';
        else
        {
            int l=L, r=R;
            while (l<r)
            {
                int md=(l+r)/2;
                if (vl[md]<l) l=md+1;
                else r=md;
            }
            cout<<dp[R]-dp[l]+1<<'\n';
        }
    }
}

Subtask #1
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 4700 KB Output isn't correct
2 Halted 0 ms 0 KB -