Submission #637398

#	Time	Username	Problem	Language	Result	Execution time	Memory
637398		VitaliyFS	Fountain (eJOI20_fountain)	C++17	100 / 100	432 ms	47280 KiB

fountain

#include<bits/stdc++.h>

using namespace std;

#define fr first
#define sc second

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

const ll INF = 1000000000000000007, DIM = 200007, DIM2 = 27, MAXN = 100007, MOD = 1000000007;

ll tt, mid, res,f, b[DIM], R[DIM], dp[DIM2][DIM], par[DIM2][DIM], used[DIM], y, type, ptr, root, cnt, sum, pos, h, p, sx,sy, id, testcase, curans, nn, split, n, m, x, k1, k2, changecnt,k,l,r,v,u, l1,r1,l2,r2;
bool flag, flag2;
char c;
string s[DIM];
pll a[DIM];
stack<ll> q;

void solve() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		cin>>a[i].fr>>a[i].sc;
	}	
	for(int i=1;i<=n;i++){
		while(!q.empty() && a[q.top()].fr < a[i].fr) {
			R[q.top()] = i;
			q.pop();
		}
		q.push(i);
	}
	for(int i=n;i>=1;i--){
		par[0][i]=R[i];
		dp[0][i] = a[i].sc;
		for(int j=1;j<=20;j++) {
			par[j][i] = par[j - 1][par[j - 1][i]];
			dp[j][i] = dp[j - 1][i] + dp[j-1][par[j-1][i]];
		}
	}
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		for(int i=18;i>=0;i--) {
			if(y - dp[i][x]>0) {
				k=dp[i][x];
				y-=k;
				x=par[i][x];
			}
		}
		cout<<x<<'\n';
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	tt=1;
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	//cin>>tt;
	while(tt--) {
		solve();
	}
	return 0;
}

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