제출 #1087378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087378		MuhammadSaram	Fountain (eJOI20_fountain)	C++17	100 / 100	442 ms	20076 KiB

fountain

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40