Submission #401995

#	Time	Username	Problem	Language	Result	Execution time	Memory
401995		maximath_1	Sum Zero (RMI20_sumzero)	C++11	100 / 100	485 ms	19516 KiB

sumzero

#include <bits/stdc++.h>

#define kyou using
#define mo namespace
#define kawaii std

kyou mo kawaii; // hi honey~

#define ll long long
#define ld long double
#define endl "\n"
const int MX = 400005;
const int LG = 5;
// const int BLOCK = 205;
// const int inf = 1000000069;
// const ll inf_ll = 8000000000000000069ll;
// const ll mod = 1e9 + 7;
// const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
// const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
// const int dx[] = {0, 1, 0, -1, 0, 0};
// const int dy[] = {1, 0, -1, 0, 0, 0}; // adj
// const int dz[] = {0, 0, 0, 0, 1, -1}; // 3d
// const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
// const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)

bool untied = 0;
void setIn(string s){freopen(s.c_str(), "r", stdin);}
void setOut(string s){freopen(s.c_str(), "w", stdout);}
void unsyncIO(){cin.tie(0) -> sync_with_stdio(0);}
void setIO(string s = ""){
	if(!untied) unsyncIO(), untied = 1;
	if(s.size()){
		setIn(s + ".in");
		setOut(s + "_output.out");
	}
}

const int H = (1 << 19) - 1;
ll key[H + 1];
int val[H + 1];

int &last(ll k){
	int i = (int)(k & H);
	while(val[i] != 0 && key[i] != k)
		i = (i + 1) & H;
	key[i] = k;
	return val[i];
}

int n, q;
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 --){
		int &tp = last(v[i]);
		if(tp && tp < anc[i + 1][0]) anc[i][0] = tp;
		else anc[i][0] = anc[i + 1][0];
		tp = i;
	}
 
	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;
	}
}

Compilation message (stderr)

sumzero.cpp: In function 'void setIn(std::string)':
sumzero.cpp:29:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 | void setIn(string s){freopen(s.c_str(), "r", stdin);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp: In function 'void setOut(std::string)':
sumzero.cpp:30:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 | void setOut(string s){freopen(s.c_str(), "w", stdout);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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