Submission #574479

#	Time	Username	Problem	Language	Result	Execution time	Memory
574479		blue	Sum Zero (RMI20_sumzero)	C++17	61 / 100	123 ms	17876 KiB

sumzero

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int mx = 100'000;

vi children[1+mx+2];
vi queries[1+mx];

vi res(1+mx);

vi st;

vi R(1+mx);

void dfs(int u)
{
	// cerr << "dfs " << u << '\n';

	for(int j : queries[u])
	{

		if(st.empty())
			res[j] = 0;
		else if(st.back() > R[j])
			res[j] = 0;
		else
		{

			int lo = 0, hi = sz(st) - 1;
			while(lo != hi)
			{
				int mid = (lo+hi)/2;
				if(st[mid] > R[j])
					lo = mid+1;
				else
					hi = mid;
			}
			res[j] = sz(st) - lo;

		}
		
	}

	st.push_back(u);

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

	st.pop_back();
}

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

	//pos i = consider sum c[1] + ... + c[i]           jump from l-1 to r for interval [l, r]

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

	int Q;
	cin >> Q;

	for(int q = 1; q <= Q; q++)
	{
		int L;
		cin >> L >> R[q];
		queries[L-1].push_back(q);
	}

	vpll pos;
	for(int i = 0; i <= N; i++)
		pos.push_back({c[i], i});
	sort(pos.begin(), pos.end());

	c.clear();

	vi A(1+N+1);
	int ct = 0;
	for(int i = 0; i <= N; i++)
	{
		if(i == 0 || pos[i].first != pos[i-1].first)
			ct++;

		A[pos[i].second] = ct;
	}

	A[N+1] = 0;

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


	vi jump(1+N+1, N+1);
	vi lastocc(1+N+1, N+1);


	for(int i = N; i >= 0; i--)
	{
		jump[i] = min(lastocc[A[i]], jump[i+1]);

		children[jump[i]].push_back(i);
		lastocc[A[i]] = i;
	}

	jump.clear();
	lastocc.clear();

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

	// for(int z : children[1+N])
	// 	cerr << z << ' ';
	// cerr << '\n';

	dfs(1+N);

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


}

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