Submission #813530

#	Time	Username	Problem	Language	Result	Execution time	Memory
813530		Acanikolic	Fountain (eJOI20_fountain)	C++14	60 / 100	1578 ms	52156 KiB

fountain

#include <bits/stdc++.h>
		 		
#define int long long 
		 
#define pb push_back 
		
#define F first
		 
#define S second
		 
using namespace std;
		 
const int N = 3e5+10;
		 
const int mod = 1e9+7;
		 
const int inf = 1e18;	

const int lg = 20;

vector<int>g[N];
int up[N][lg],sm[N][lg],vis[N];
pair<int,int>a[N];

void dfs(int x,int par) {
	vis[x] = 1;
	for(auto X:g[x]) {
		if(X != par) {
			dfs(X,x);
		}
	}
}
				
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	
	int n,Q;
	cin >> n >> Q;
	for(int i=1;i<=n;i++) cin >> a[i].F >> a[i].S;
	stack<pair<int,int>>st;
	for(int i=1;i<=n;i++) up[i][0] = i;
	for(int i=n;i>=1;i--) {
		while(st.size() && st.top().F <= a[i].F) st.pop();
		if(!st.empty()) {
			g[i].pb(st.top().S);
			up[i][0] = st.top().S;
			sm[i][0] = a[st.top().S].S;
			// /cout << i << " -> " << st.top().S << ' ' << a[st.top().S].S << endl;
			//g[st.top().S].pb(i);
		}
		st.push({a[i].F,i});
	}
	for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0);
	for(int j=1;j<lg;j++) {
		for(int i=1;i<=n;i++) {
			up[i][j] = up[up[i][j-1]][j-1];
			sm[i][j] = sm[i][j-1]+sm[up[i][j-1]][j-1];
		}
	}
	/*for(int i=1;i<=n;i++) {
		for(int j=0;j<lg;j++) cout << sm[i][j] << ' ';
		cout << endl;
	}*/
	while(Q--) {
		int index,val;
		cin >> index >> val;
		val -= a[index].S;
		for(int j=lg-1;j>=0;j--) {
			if(sm[index][j] <= val) {
				//cout << index << ' ' << j << ' ' << val << ' ' << sm[index][j] << endl;
				val -= sm[index][j];
				index = up[index][j];
			}
		}
		if(val > sm[index][0]) {
			cout << "0\n";
			continue;
		}
		if(val > 0) index = up[index][0];
		cout << index << '\n';
	}
    return 0; 
}

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