Submission #399220

#	Time	Username	Problem	Language	Result	Execution time	Memory
399220		abacaba	Sum Zero (RMI20_sumzero)	C++14	61 / 100	857 ms	24660 KiB

sumzero

// 石室詩士施氏, 嗜獅, 誓食十獅。
// 氏時時適市視獅。
// 十時, 適十獅適市。
// 是時, 適施氏適市。
// 氏視是十獅, 恃矢勢, 使是十獅逝世。
// 氏拾是十獅屍, 適石室。
// 石室濕, 氏使侍拭石室。
// 石室拭, 氏始試食是十獅。
// 食時, 始識是十獅, 實十石獅屍。
// 試釋是事。
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define f first
#define se second
 
template <typename T> void Max(T &a, T b) {
	a = max(a, b);
}
 
template <typename T> void Min(T &a, T b) {
	a = min(a, b);
}
 
const int inf = 0x3f3f3f3f;
const int N = 4e5 + 2;
int n, q, p[N], to[N];
int qs[N], last[N];
int d[N], l, r, mid;
int sz;
int R[N], prv[N], head[N], prvqs[N];
 
void dfs(int v) {
	to[sz++] = v;
	for(int i = qs[v]; i != -1; i = prvqs[i]) {
		l = 0, r = sz - 1;
		p[i] = -inf;
		while(l <= r) {
			mid = l + r >> 1;
			if(to[mid] <= R[i])
				r = mid - 1, Max(p[i], d[v] - d[to[mid]]);
			else
				l = mid + 1;
		}
	}
	for(int to = head[v]; to != -1; to = prv[to]) {
		d[to] = d[v] + 1;
		dfs(to);
	}
	--sz;
}
 
int main() {
	memset(head, -1, sizeof(head));
	memset(prv, -1, sizeof(prv));
	memset(qs, -1, sizeof(qs));
	memset(prvqs, -1, sizeof(prvqs));
	memset(last, -1, sizeof(last));
	ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	// freopen("input.txt", "r", stdin);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> p[i];
		p[i] += p[i-1];
		d[i] = p[i];
	}
	d[0] = 0;
	sort(d, d + n + 1);
	fill(to, to + n + 2, n + 1);
	for(int i = n, ind; i >= 0; --i) {
		ind = lower_bound(d, d + n + 1, p[i]) - d;
		if(last[ind] != -1)
			Min(to[i], last[ind]);
		Min(to[i], to[i+1]);
		prv[i] = head[to[i]];
		head[to[i]] = i;
		last[ind] = i;
	}
	cin >> q;
	for(int i = 1; i <= q; ++i) {
		int l;
		cin >> l >> R[i];
		prvqs[i] = qs[l - 1];
		qs[l - 1] = i;
	}
	d[n+1] = 0;
	dfs(n + 1);
	for(int i = 1; i <= q; ++i)
		cout << p[i] << endl;
	return 0;
}

Compilation message (stderr)

sumzero.cpp: In function 'void dfs(int)':
sumzero.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |    mid = l + r >> 1;
      |          ~~^~~

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