Submission #788700

#	Time	Username	Problem	Language	Result	Execution time	Memory
788700		ThylOne	Fountain (eJOI20_fountain)	C++14	30 / 100	192 ms	5588 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define debug(var) cerr<<"#"<<#var<<"="<<var<<endl;
struct Recip{
	int diametre;
	int capacite;
	int id;
	void read(int i){
		cin>>diametre;
		cin>>capacite;
		id=i;
	};
};
int solve(vector<Recip> &rec,vector<int> &prefix,int pos,int volume){
	int pref = 0;
	if(pos!=0){
		pref+=prefix[pos-1];
	}
	if((prefix[(int)prefix.size()-1]-pref)<volume){
		return 0;
	}
	int low = pos;
	int high = (int)prefix.size()-1;
	while((high-low)>1){
		int mid = (low+high)/2;
		int somme = prefix[mid]-pref;
		if(somme>volume){
			high = mid;
		}else if(somme<volume){
			low = mid;			
		}else{
			return rec[mid].id+1;
		}
	}
	if((prefix[low]-pref)>=volume){
		return rec[low].id+1;
	}else{
		return rec[high].id+1;
	}
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	int n,q;cin>>n>>q;
	vector<Recip> recipient(n);
	vector<int> pref(n);
	int act=0;
	for(int i = 0 ; i <n;i++){
		recipient[i].read(i);
		act+=recipient[i].capacite;
		pref[i]=act;
	}
	for(int i =0;i<q;i++){
		int pos,volume;
		cin>>pos;pos--;
		cin>>volume;
		cout<<solve(recipient,pref,pos,volume)<<endl;
	}
	
	
   
}

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