Submission #644078

#	Time	Username	Problem	Language	Result	Execution time	Memory
644078		badmachine77	Sum Zero (RMI20_sumzero)	C++17	22 / 100	92 ms	23368 KiB

sumzero

#include<bits/stdc++.h>
using namespace std;

typedef int ll;

vector<vector<ll> > gr;
vector<ll> v[400400];
map<ll,ll> mp;
ll nxt[400400];
ll hev[400400];
ll a[400400];
ll s[400400];
ll ot[400400];
ll depth[400400];
ll n,q,cnt=-1;
bool used[400400];

void dfs(ll pos){
  used[pos]=1;
  s[pos]=1;
  for(ll i : v[pos]){
    depth[i]=depth[pos]+1;
    dfs(i);
    s[pos]+=s[i];
    }

  hev[pos]=-1;
  for(ll i : v[pos]){
    if(s[i]>=s[pos]/2.0){
      hev[pos]=i;
      break;
      }
    }
  }

void dfs2(ll pos){
  ot[pos]=cnt;
  gr[cnt].push_back(pos);
  if(hev[pos]!=-1){
    dfs2(hev[pos]);
    }

  for(ll i : v[pos]){
    if(i==hev[pos])continue;
    ++cnt;
    gr.push_back(vector<ll>());
    nxt[cnt]=pos;
    dfs2(i);
    }
  }

int main(){

ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);

cin>>n;
for(ll i=1;i<=n;++i){
  cin>>a[i];
  s[i]=s[i-1]+a[i];
  }

ll last=1e9;
for(ll i=n;i>=0;--i){
  if(mp[s[i]]==0){
    nxt[i]=last;
    if(last!=1e9)v[last].push_back(i);
    mp[s[i]]=i;
    continue;
    }

  last=min(last,mp[s[i]]);
  v[last].push_back(i);
  nxt[i]=last;

  mp[s[i]]=i;
  }

//for(ll i=0;i<=n;++i)cout<<i<<" "<<nxt[i]<<endl;

for(ll i=n;i>=0;--i){
  if(used[i])continue;

  depth[i]=1;
  dfs(i);
  ++cnt;
  nxt[cnt]=-1;
  gr.push_back(vector<ll>());
  dfs2(i);
  }

//for(ll i=0;i<=cnt;++i)cout<<nxt[i]<<" ";cout<<endl;

/*
for(ll i=0;i<=cnt;++i){
  cout<<endl<<endl;
  cout<<par[i]<<endl;
  for(ll j : gr[i])cout<<j<<" ";cout<<endl;
  for(ll j : gr[i])cout<<ot[j]<<" ";cout<<endl;
  }
cout<<"--------------"<<endl;
*/

cin>>q;
ll x1,x2,c1,c2,pos,l,mid,r;
while(q--){
  cin>>x1>>x2;
  --x1;
  c1=depth[x1];
  pos=ot[x1];

  //cout<<c1<<" "<<pos<<" ";

  while(nxt[pos]!=-1){
    c2=ot[nxt[pos]];
    if(gr[pos][0]<x2 && nxt[pos]<=x2)pos=c2;
    else break;
    }

  //cout<<pos<<endl;

  l=0;
  r=gr[pos].size()-1;
  last=-1;
  while(l<=r){
    mid=(l+r)/2;
    if(gr[pos][mid]<=x2){
      r=mid-1;
      last=gr[pos][mid];
      }
    else {
      l=mid+1;
      }
    }

  c2=depth[last];
  cout<<c1-c2<<'\n';
  }

return 0;
}
/*
10
1 2 -3 0 1 -4 3 2 -1 1
3
1 10
1 5
2 9

10
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

*/

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