제출 #645910

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
645910		blue	Sum Zero (RMI20_sumzero)	C++17	61 / 100	513 ms	51948 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;

using vi = vector<int>;
using ll = long long;
using pii = pair<int, int>;
#define sz(x) int(x.size())

ll* c;
vi* children;

vi lst;

vector<pii> queries[400'001];
int* res;

void dfs(int u)
{

	// cerr << "dfs " << u << '\n';


	for(pii qr : queries[u])
	{
		// cerr << "qr " << qr.first << ' ' << qr.second << '\n';
		int bt = sz(lst);
		for(int e = 19; e >= 0; e--)
		{
			if(bt - (1<<e) >= 0 && lst[bt - (1<<e)] <= qr.second)
				bt -= (1<<e);
		}
		res[qr.first] = sz(lst) - bt;
	}

	
	lst.push_back(u);

	for(int v : children[u])
	{
		// cerr << "child " << v << '\n';
		dfs(v);
	}

	lst.pop_back();
}


int main()
{
	int N;
	cin >> N;

	ll d[N+1];
	c = d;
	c[0] = 0;
	for(int i = 1; i <= N; i++)
	{
		cin >> c[i];
		c[i] += c[i-1];
	}

	int lst[N+1];
	for(int i = 0; i <= N; i++)
		lst[i] = i;
	sort(lst, lst+N+1, [] (int u, int v)
	{
		if(c[u] == c[v])
			return u < v;
		return c[u] < c[v];
	});

	int nxt[N+1];
	for(int i = 0; i <= N; i++)
		nxt[i] = N+1;

	for(int i = 0; i+1 <= N; i++)
	{
		if(c[lst[i]] == c[lst[i+1]])
			nxt[lst[i]] = lst[i+1];
	}

	// for(int i = 0; i <= N; i++)
	// 	cerr << nxt[i] << ' ';
	// cerr << '\n';

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

	// for(int i = 0; i <= N; i++)
	// 	cerr << nxt[i] << ' ';
	// cerr << '\n';

	int Q;
	cin >> Q;

	// cerr << "done\n";

	// vector<pii> qrs[1+N];
	// queries = qrs;

	for(int j = 1; j <= Q; j++)
	{
		int L, R;
		cin >> L >> R;
		L--;

		queries[L].push_back({j, R});
	}

	vi chld[2+N];
	children = chld;

	for(int i = 0; i <= N; i++)
		children[nxt[i]].push_back(i);


	int rs[1+Q];
	res = rs;

	dfs(N+1);


	for(int j = 1; j <= Q; j++)
		cout << res[j] << '\n';
}

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