Submission #644093

#	Time	Username	Problem	Language	Result	Execution time	Memory
644093		badmachine77	Sum Zero (RMI20_sumzero)	C++17	61 / 100	341 ms	40804 KiB

sumzero

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

typedef int ll;

vector<pair<ll,ll>> wow;
vector<ll> v[400400],gr;
unordered_map<ll,ll> mp;
ll nxt[400400];
ll hev[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]>>1){
      hev[pos]=i;
      break;
      }
    }
  }

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

  for(ll i : v[pos]){
    if(i==hev[pos])continue;
    ++cnt;
    wow.push_back({gr.size(),gr.size()-1});
    nxt[cnt]=pos;
    dfs2(i);
    }
  }

int main(){

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

scanf("%d",&n);
for(ll i=1;i<=n;++i){
  scanf("%d",&s[i]);
  s[i]+=s[i-1];
  }

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

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

  mp[s[i]]=i;
  }

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

  depth[i]=1;
  dfs(i);
  ++cnt;
  nxt[cnt]=1e9;

  wow.push_back({gr.size(),gr.size()-1});

  dfs2(i);
  }

scanf("%d",&q);
ll x1,x2,c1,c2,pos,l,mid,r;
while(q--){
  scanf("%d%d",&x1,&x2);
  --x1;
  c1=depth[x1];
  pos=ot[x1];

  while(nxt[pos]<=x2){
    pos=ot[nxt[pos]];
    }

  l=wow[pos].first;
  r=wow[pos].second;
  last=-1;
  while(l<=r){
    mid=(l+r)>>1;
    if(gr[mid]<=x2){
      r=mid-1;
      last=mid;
      }
    else {
      l=mid+1;
      }
    }

  c2=depth[gr[last]];
  printf("%d\n",c1-c2);
  }

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

*/

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:57:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 | scanf("%d",&n);
      | ~~~~~^~~~~~~~~
sumzero.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   scanf("%d",&s[i]);
      |   ~~~~~^~~~~~~~~~~~
sumzero.cpp:90:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 | scanf("%d",&q);
      | ~~~~~^~~~~~~~~
sumzero.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   scanf("%d%d",&x1,&x2);
      |   ~~~~~^~~~~~~~~~~~~~~~

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