Submission #827338

#	Time	Username	Problem	Language	Result	Execution time	Memory
827338		ZeroCool	Fountain (eJOI20_fountain)	C++14	100 / 100	552 ms	37604 KiB

fountain

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
using namespace std;
 
const int mxn = 1e5 + 5;
const int SQRT = 500;
const int LOG = 20;
const int inf = 1e18;
const int mod = 998244353;
const ld eps = 1e-9;

int up[mxn][LOG];
int st[mxn][LOG];

void solve(int T){
	int n,q;
	cin>>n>>q;

	stack<pair<int,int> > qu;
	

	for(int i = 1;i<=n;i++){
		int l;
		cin>>l;
		cin>>st[i][0];

		while(qu.size() && l > qu.top().first){
			up[qu.top().second][0] = i;
			qu.pop();
		}
		qu.push({l,i});
	}
	for(int j = 1;j<LOG;j++){
		for(int i = 1;i<=n;i++){
			up[i][j] = up[up[i][j-1]][j-1];
			st[i][j] = st[i][j-1] + st[up[i][j-1]][j-1];
		}
	}

	while(q--){
		int a,b;
		cin>>a>>b;

		for(int i = LOG-1;i>=0;i--){
			if(st[a][i] < b){
				b -= st[a][i];
				a = up[a][i];

			}
		}

		cout<<a<<endl;
	}

}
int32_t main(){
	#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
	#endif
	int t = 1;
	//cin>>t;

	for(int i = 1;i<=t;i++)solve(i);
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40