oj.uz

Submission #597230

# Submission time Handle Problem Language Result Execution time Memory
597230 2022-07-15T18:31:34 Z CaroLinda Sum Zero (RMI20_sumzero) C++14
100 / 100
 211 ms 15108 KB 
#include <bits/stdc++.h>

#define ll long long

const int LOG = 20;
const int MAXN = 4e5+10;

using namespace std;

int N, Q, T;
ll C[MAXN];
int d[MAXN], l[MAXN], r[MAXN];
int dp[MAXN];
int ans[MAXN];
int id[MAXN];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	for(int i = 1; i <= N; i++)
		cin >> C[i], C[i] += C[i-1];

	iota(id, id+1+N, 0);
	sort(id, id+1+N, [&](int a, int b){
		if(C[a] == C[b]){
			return a < b;
		}
		return C[a] < C[b];
	});

	for(int i= N; i > 0; i--){
		if(C[id[i-1]] == C[id[i]]){
			dp[id[i]] =id[i-1];
		}
		else dp[id[i]] = -1;
	}


	dp[0] = 0;

	for(int i = 1; i <= N; i++){
		if(dp[i] != -1){
			d[i] = d[dp[i]]+1;
			if( (d[i-1] == d[i] && dp[i-1] > dp[i]) || d[i-1] > d[i] ){
				d[i] = d[i-1];
				dp[i] = dp[i-1];
			}
		}
		else{
			d[i] = d[i-1];
			dp[i] = dp[i-1];
		}

	}

	cin >> Q;

	for(int i = 1; i <= Q; i++){
		cin >> l[i] >> r[i];

		ans[i] = d[r[i]]-d[l[i]-1];
	}

	int toGet = 0, toFill = 1;

	for(int i = 0; i < LOG; i++){
		for(int j = 1; j <= Q; j++){
			if((1<<i)&ans[j]){
				r[j] = dp[r[j]];
			}
		}
		for(int j= 1; j <= N; j++)
			d[j] = dp[dp[j]];

		for(int j = 1; j <= N; j++)
			dp[j] = d[j];
	}

	for(int i = 1; i <= Q; i++)
		cout << ans[i]-(r[i] < l[i]-1) << "\n";

}

Compilation message

sumzero.cpp: In function 'int main()':
sumzero.cpp:66:6: warning: unused variable 'toGet' [-Wunused-variable]
   66 |  int toGet = 0, toFill = 1;
      |      ^~~~~
sumzero.cpp:66:17: warning: unused variable 'toFill' [-Wunused-variable]
   66 |  int toGet = 0, toFill = 1;
      |                 ^~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 44 ms 3916 KB Output is correct
8 Correct 42 ms 3808 KB Output is correct
9 Correct 53 ms 3860 KB Output is correct
10 Correct 44 ms 3856 KB Output is correct
11 Correct 45 ms 3812 KB Output is correct
12 Correct 49 ms 3856 KB Output is correct

Subtask #3
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 44 ms 3916 KB Output is correct
8 Correct 42 ms 3808 KB Output is correct
9 Correct 53 ms 3860 KB Output is correct
10 Correct 44 ms 3856 KB Output is correct
11 Correct 45 ms 3812 KB Output is correct
12 Correct 49 ms 3856 KB Output is correct
13 Correct 180 ms 14712 KB Output is correct
14 Correct 176 ms 14504 KB Output is correct
15 Correct 211 ms 15108 KB Output is correct
16 Correct 184 ms 14752 KB Output is correct
17 Correct 188 ms 14500 KB Output is correct
18 Correct 210 ms 15004 KB Output is correct