Submission #398635

#	Time	Username	Problem	Language	Result	Execution time	Memory
398635		abacaba	Sum Zero (RMI20_sumzero)	C++14	0 / 100	1092 ms	13284 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 + 15;
int n, q, p[N];
int to[N];
map <int, vector <int>> ord;
int nxt[N];
int d[N];
bitset <N> used;
vector <int> g[N];
int par[N];

void dfs(int v) {
	used[v] = 1;
	for(int to : g[v]) {
		d[to] = d[v] + 1;
		par[to] = v;
		dfs(to);
	}
}

main() {
	memset(to, 0x3f, sizeof(to));
	memset(nxt, 0x3f, sizeof(nxt));
	ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> p[i];
		p[i] += p[i-1];
		ord[p[i]].pb(i);
	}
	ord[0].pb(0);
	for(int i = 0; i <= n; ++i) {
		int ind = upper_bound(ord[p[i]].begin(), ord[p[i]].end(), i) - ord[p[i]].begin();
		if(ind < ord[p[i]].size())
			to[i] = ord[p[i]][ind];
		nxt[i] = to[i];
	}
	for(int i = n; i >= 0; --i) {
		Min(nxt[i], nxt[i+1]);
		Min(to[i], nxt[i+1]);
		if(to[i] < inf)
			g[to[i]].pb(i);
	}
	for(int i = n; i >= 0; --i)
		if(!used[i])
			dfs(i);
	cin >> q;
	while(q--) {
		int l, r;
		cin >> l >> r;
		int res = 0;
		for(int i = l - 1; i <= r; ++i) {
			int v = i, cnt = 0;
			while(par[v] != 0 && par[v] <= r) {
				++cnt;
				v = par[v];
			}
			Max(res, cnt);
		}
		cout << res << endl;
	}
	return 0;
}

Compilation message (stderr)

sumzero.cpp:51:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   51 | main() {
      |      ^
sumzero.cpp: In function 'int main()':
sumzero.cpp:64:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   if(ind < ord[p[i]].size())
      |      ~~~~^~~~~~~~~~~~~~~~~~

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