oj.uz

Submission #574479

# Submission time Handle Problem Language Result Execution time Memory
574479 2022-06-08T15:36:27 Z blue Sum Zero (RMI20_sumzero) C++17
61 / 100
 123 ms 17876 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6100 KB Output is correct
2 Correct 7 ms 6100 KB Output is correct
3 Correct 8 ms 6128 KB Output is correct
4 Correct 8 ms 6100 KB Output is correct
5 Correct 8 ms 6156 KB Output is correct
6 Correct 9 ms 6088 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6100 KB Output is correct
2 Correct 7 ms 6100 KB Output is correct
3 Correct 8 ms 6128 KB Output is correct
4 Correct 8 ms 6100 KB Output is correct
5 Correct 8 ms 6156 KB Output is correct
6 Correct 9 ms 6088 KB Output is correct
7 Correct 113 ms 13896 KB Output is correct
8 Correct 121 ms 13408 KB Output is correct
9 Correct 119 ms 13172 KB Output is correct
10 Correct 108 ms 13884 KB Output is correct
11 Correct 115 ms 13348 KB Output is correct
12 Correct 123 ms 13208 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6100 KB Output is correct
2 Correct 7 ms 6100 KB Output is correct
3 Correct 8 ms 6128 KB Output is correct
4 Correct 8 ms 6100 KB Output is correct
5 Correct 8 ms 6156 KB Output is correct
6 Correct 9 ms 6088 KB Output is correct
7 Correct 113 ms 13896 KB Output is correct
8 Correct 121 ms 13408 KB Output is correct
9 Correct 119 ms 13172 KB Output is correct
10 Correct 108 ms 13884 KB Output is correct
11 Correct 115 ms 13348 KB Output is correct
12 Correct 123 ms 13208 KB Output is correct
13 Runtime error 75 ms 17876 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -