oj.uz

Submission #1087378

# Submission time Handle Problem Language Result Execution time Memory
1087378 2024-09-12T14:56:44 Z MuhammadSaram Fountain (eJOI20_fountain) C++17
100 / 100
 442 ms 20076 KB 
#include <bits/stdc++.h>

using namespace std;

int main()
{
	int n,q,lg=17;
	cin>>n>>q;
	int nxt[n+1][lg];
	stack<int> st;
	int a[n],b[n],su[n+1][lg]={};
	for (int i=0;i<n;i++)
		cin>>a[i]>>b[i],su[i][0]=b[i];
	nxt[n][0]=n;
	for (int i=n-1;i>=0;i--)
	{
		while (!st.empty() && a[st.top()]<=a[i])
			st.pop();
		if (st.empty())
			nxt[i][0]=n;
		else
			nxt[i][0]=st.top();
		st.push(i);
	}
	for (int p=1;p<lg;p++)
		for (int i=0;i<=n;i++)
			nxt[i][p]=nxt[nxt[i][p-1]][p-1],su[i][p]=su[i][p-1]+su[nxt[i][p-1]][p-1];
	while (q--)
	{
		int id,x;
		cin>>id>>x;
		id--;
		for (int p=lg-1;p>=0 && id<n;p--)
			if (su[id][p]<x)
				x-=su[id][p],id=nxt[id][p];
		cout<<(id+1)%(n+1)<<endl;
	}

	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 3 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 17764 KB Output is correct
2 Correct 302 ms 16896 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 4 ms 604 KB Output is correct
7 Correct 3 ms 348 KB Output is correct
8 Correct 263 ms 17764 KB Output is correct
9 Correct 302 ms 16896 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 167 ms 10324 KB Output is correct
12 Correct 442 ms 20076 KB Output is correct
13 Correct 370 ms 19356 KB Output is correct
14 Correct 353 ms 18516 KB Output is correct
15 Correct 333 ms 18716 KB Output is correct