oj.uz

Submission #402289

# Submission time Handle Problem Language Result Execution time Memory
402289 2021-05-11T14:34:11 Z nandonathaniel Sum Zero (RMI20_sumzero) C++14
100 / 100
 719 ms 15152 KB 
#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,Q,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 >> Q;
	while(Q--){
		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;
}

Compilation message

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++){
      |              ~^~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3660 KB Output is correct
2 Correct 6 ms 3660 KB Output is correct
3 Correct 7 ms 3660 KB Output is correct
4 Correct 6 ms 3660 KB Output is correct
5 Correct 6 ms 3580 KB Output is correct
6 Correct 6 ms 3660 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3660 KB Output is correct
2 Correct 6 ms 3660 KB Output is correct
3 Correct 7 ms 3660 KB Output is correct
4 Correct 6 ms 3660 KB Output is correct
5 Correct 6 ms 3580 KB Output is correct
6 Correct 6 ms 3660 KB Output is correct
7 Correct 111 ms 6292 KB Output is correct
8 Correct 98 ms 6208 KB Output is correct
9 Correct 123 ms 6376 KB Output is correct
10 Correct 111 ms 6276 KB Output is correct
11 Correct 100 ms 6328 KB Output is correct
12 Correct 122 ms 6428 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3660 KB Output is correct
2 Correct 6 ms 3660 KB Output is correct
3 Correct 7 ms 3660 KB Output is correct
4 Correct 6 ms 3660 KB Output is correct
5 Correct 6 ms 3580 KB Output is correct
6 Correct 6 ms 3660 KB Output is correct
7 Correct 111 ms 6292 KB Output is correct
8 Correct 98 ms 6208 KB Output is correct
9 Correct 123 ms 6376 KB Output is correct
10 Correct 111 ms 6276 KB Output is correct
11 Correct 100 ms 6328 KB Output is correct
12 Correct 122 ms 6428 KB Output is correct
13 Correct 598 ms 15032 KB Output is correct
14 Correct 511 ms 14604 KB Output is correct
15 Correct 676 ms 15152 KB Output is correct
16 Correct 617 ms 14868 KB Output is correct
17 Correct 477 ms 14604 KB Output is correct
18 Correct 719 ms 15152 KB Output is correct