Submission #383214

#	Time	Username	Problem	Language	Result	Execution time	Memory
383214		MODDI	Fountain (eJOI20_fountain)	C++14	0 / 100	2 ms	492 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;
	bool sorted = true;
	for(int i = 0; i < n; i++){
		int a, b;
		cin>>a>>b;
		if(arr[arr.size() - 1].first < a)
			sorted = false;
		arr.pb(mp(a,b));
		water[i] = b;
	}
	if(sorted){
		vi pref;
		pref.pb(water[0]);
		for(int i = 1; i < n; i++)
			pref.pb(water[i] + pref[i - 1]);
		while(q--){
			int at, vol;
			cin>>at>>vol;
			at--;
			int l = 0, r = n - 1, mid;
			while(l <= r){
				mid = (l + r) / 2;
				if(water[mid] < vol)
					l = mid + 1;
				else
					r = mid - 1;
			}
			cout<<mid+1<<endl;
		}
		return 0;
	}
	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];
		}
	}
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:41:14: warning: 'mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |    cout<<mid+1<<endl;
      |              ^

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