oj.uz

Submission #788700

# Submission time Handle Problem Language Result Execution time Memory
788700 2023-07-20T13:43:28 Z ThylOne Fountain (eJOI20_fountain) C++14
30 / 100
 192 ms 5588 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 3880 KB Output is correct
2 Correct 192 ms 5588 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 316 KB Output isn't correct
2 Halted 0 ms 0 KB -