제출 #402288

#제출 시각아이디문제언어결과실행 시간메모리
402288nandonathanielSum Zero (RMI20_sumzero)C++14
100 / 100
752 ms15284 KiB
#include<bits/stdc++.h> using namespace std; typedef pair<int,int> pii; const int MAXN=400005,LOG=4; int kiri[MAXN],pa[LOG][MAXN],idx[MAXN],MAX; vector<pii> V; int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); int N,L,R; cin >> N; memset(kiri,-1,sizeof(kiri)); memset(idx,-1,sizeof(idx)); long long sum=0; V.push_back({sum,0}); for(int i=1;i<=N;i++){ cin >> L; sum+=L; V.push_back({sum,i}); } sort(V.begin(),V.end()); for(int i=0;i<V.size();i++){ if(i==0 || V[i].first!=V[i-1].first)MAX++; pa[0][V[i].second]=MAX; } idx[pa[0][0]]=0; for(int i=1;i<=N;i++){ kiri[i]=idx[pa[0][i]]; idx[pa[0][i]]=i; } for(int i=0;i<=N;i++)pa[0][i]=0; for(int i=N;i>=0;i--){ //find j minimum st j>i and kiri[j]>=i if(i==N)pa[0][i]=N+1; else{ if(pa[0][i])pa[0][i]=min(pa[0][i+1],pa[0][i]); else pa[0][i]=pa[0][i+1]; } for(int j=1;j<LOG;j++){ pa[j][i]=pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][pa[j-1][i]]]]]]]]]]]]]]]]]]]]]]]]]]]; if(pa[j][i]==0)pa[j][i]=N+1; } if(kiri[i]!=-1)pa[0][kiri[i]]=i; } cin >> N; while(N--){ cin >> L >> R; int ans=0,now=pa[0][L-1]; if(now>R){ cout << 0 << '\n'; continue; } int pkt=1; for(int i=1;i<=LOG-1;i++)pkt*=27; for(int i=LOG-1;i>=0;i--){ for(int j=0;j<27;j++){ if(pa[i][now]<=R){ ans+=pkt; now=pa[i][now]; } } pkt/=27; } cout << ans+1 << '\n'; } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

sumzero.cpp: In function 'int main()':
sumzero.cpp:22:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for(int i=0;i<V.size();i++){
      |              ~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...