Submission #1083658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083658		presko	Sum Zero (RMI20_sumzero)	C++14	0 / 100	69 ms	348 KiB

sumzero

#include<iostream>
#include<vector>
#define MAXN 400010
using namespace std;
int a[MAXN];
long long pre[MAXN];
vector<pair<long long,int>> sums;
vector<pair<int,int>> parts;
int locate(int val)
{
    if(sums.size()==0)return -1;
    int l=0,r=sums.size()-1;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(sums[mid].first<val)l=mid+1;
        else if(sums[mid].first==val){l=mid;break;}
        else r=mid-1;
    }
    if(sums[l].first!=val)return -1;
    return sums[l].second;
}
void calc(int l, int r)
{
    long long sum=0;
    for(int i=l;i<=r;i++)
    {
        if(a[i]==0)
        {
            parts.push_back({i,i});
            sums.clear();
            sums.push_back({0,i});
            sum=0;
            continue;
        }
        sum+=a[i];
        int res=locate(sum);
        if(res>-1){parts.push_back({res+1,i});sums.clear();sums.push_back({0,i});sum=0;}
        sums.push_back({sum,i});
    }
}
int main()
{
    int n,q;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
    }
    /*sums.push_back({0,0});
    calc(1,n);*/
    cin>>q;
    for(int t=0;t<q;t++)
    {
        int l,r;
        cin>>l>>r;
        sums.clear();parts.clear();
        sums.push_back({0,l-1});
        calc(l,r);
        cout<<parts.size()<<"\n";
    }
}

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