Submission #908224

#	Time	Username	Problem	Language	Result	Execution time	Memory
908224		shoryu386	Fountain (eJOI20_fountain)	C++17	100 / 100	790 ms	46536 KiB

fountain

#include <bits/stdc++.h>
using namespace std;

#define int long long

main(){
	int n, q;
	cin >> n >> q;
	
	int diam[n], cap[n];
	for (int x = 0; x < n; x++) cin >> diam[x] >> cap[x];
	
	//2k decomp
	
	stack<int> stk;
	int nextLargest[n];
	
	for (int x = 0; x < n; x++) nextLargest[x] = n;
	
	for (int x = 0; x < n; x++){
		while (!stk.empty() && diam[x] > diam[stk.top()]){
			nextLargest[stk.top()] = x;
			stk.pop();
		}
		
		stk.push(x);
	}
	
	pair<int, int> twok[100007][25];
	memset(twok, -1, sizeof(twok));
	
	for (int x = 0; x < n; x++){
		twok[x][0] = {nextLargest[x], cap[x]};
		
		//cout << nextLargest[x] << ' ';
	}
	
	for (int z = 0; z < 24; z++){
		for (int x = 0; x < n; x++){
			if (twok[x][z].first != -1 && twok[ twok[x][z].first ][z].first != -1){
				twok[x][z+1] = { twok[ twok[x][z].first ][z].first, twok[x][z].second + twok[ twok[x][z].first ][z].second };
			}
		}
	}
	
	for (int x = 0; x < q; x++){
		int res, water; cin >> res >> water;
		res--;
		
		int cursum = water;
		for (int z = 24; z > -1; z--){
			if (twok[res][z].first != -1){
				if (cursum > twok[res][z].second){
					cursum -= twok[res][z].second;
					res = twok[res][z].first;
				}
			} 
		}
		
		if (res == n) cout << 0 << '\n';
		else cout << res+1 << '\n';
	}
	
	
	
	
}

Compilation message (stderr)

fountain.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main(){
      | ^~~~

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