Submission #401967

#	Time	Username	Problem	Language	Result	Execution time	Memory
401967		maximath_1	Sum Zero (RMI20_sumzero)	C++11	61 / 100	547 ms	23440 KiB

sumzero

#include <iostream>
#include <math.h>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <set>
#include <functional>
#include <limits.h>
#include <map>
#include <queue>
using namespace std;

#define ll long long
#define ld long double
#define endl "\n"
const int MX = 400005;
const int BLOCK = 350;
const ll mod = 998244353;
const int LG = 5;

int n, q;
map<ll, int> last;
ll v[MX];
int anc[MX][LG], pw10[LG + 1];

int main(){
	pw10[0] = 1;
	for(int i = 1; i <= LG; i ++)
		pw10[i] = pw10[i - 1] * 10;
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n;
	for(int i = 1; i <= n; i ++)
		cin >> v[i];
	for(int i = 1; i <= n; i ++)
		v[i] += v[i - 1];

	last[v[n]] = n;
	anc[n][0] = n + 1;
	for(int i = n - 1; i >= 0; i --){
		if(!last.count(v[i])) anc[i][0] = n + 1;
		else anc[i][0] = last[v[i]];
		last[v[i]] = i;
	}

	for(int i = n - 1; i >= 0; i --)
		anc[i][0] = min(anc[i][0], anc[i + 1][0]);

	for(int j = 1; j < LG; j ++){
		for(int i = 0; i <= n; i ++){
			if(anc[i][j - 1] == n + 1) anc[i][j] = n + 1;
			else if(anc[anc[i][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
			else if(anc[anc[anc[i][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
			else if(anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
			else if(anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
			else if(anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
			else if(anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
			else if(anc[anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
			else if(anc[anc[anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) anc[i][j] = n + 1;
			else anc[i][j] = anc[anc[anc[anc[anc[anc[anc[anc[anc[anc[i][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1];
		}
	}

	cin >> q;
	for(int l, r, i = 0; i < q; i ++){
		cin >> l >> r;
		l --;
		int ans = 0, nw = l;
		for(int j = LG; j >= 0; j --){
			for(int tp = 0; tp < 10; tp ++){
				if(j == LG){
					int cr;
					if(anc[nw][j - 1] == n + 1) cr = n + 1;
					else if(anc[anc[nw][j - 1]][j - 1] == n + 1) cr = n + 1;
					else if(anc[anc[anc[nw][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
					else if(anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
					else if(anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
					else if(anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
					else if(anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
					else if(anc[anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
					else if(anc[anc[anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1] == n + 1) cr = n + 1;
					else cr = anc[anc[anc[anc[anc[anc[anc[anc[anc[anc[nw][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1]][j - 1];

					if(cr <= r){
						ans += pw10[j];
						nw = cr;
					}
				}else{
					if(anc[nw][j] <= r){
						ans += pw10[j];
						nw = anc[nw][j];
					}else break;
				}
			}
		}
		cout << ans << endl;
	}
}

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