Submission #383212

#	Time	Username	Problem	Language	Result	Execution time	Memory
383212		MODDI	Fountain (eJOI20_fountain)	C++14	30 / 100	1591 ms	2272 KiB

fountain

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
int n, q;
vector<pii> arr;
int parent[100000], water[100000];
int main(){
	cin>>n>>q;
	for(int i = 0; i < n; i++){
		int a, b;
		cin>>a>>b;
		arr.pb(mp(a,b));
		water[i] = b;
	}
	for(int i = 0; i < n; i++){
		bool f = false;
		for(int j = i + 1; j < n; j++){
			if(arr[i].first < arr[j].first)
			{
				f = true;
				parent[i] = j;
				break;
			}
			else
				continue;
		}
		if(!f)
		parent[i] = n;
		//cout<<"the parent of "<<i<<" is "<<parent[i]<<endl;
	}
	while(q--){
		int at, vol;
		cin>>at>>vol;
		at--;
		if(vol <= water[at])
		{
			cout<<at + 1<<endl;
			continue;
		}
		while(vol > 0){
			if(at == n){
				cout<<0<<endl;
				break;
			}
			if(vol - water[at] <= 0){
				cout<<at + 1<<endl;
				break;
			}
			vol -= water[at];
			at = parent[at];
		}
	}
}

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