oj.uz

Submission #643562

# Submission time Handle Problem Language Result Execution time Memory
643562 2022-09-22T12:49:08 Z Ferid20072020 Fountain (eJOI20_fountain) C++17
30 / 100
 70 ms 4140 KB 
#include <bits/stdc++.h>

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n , query;
	cin >> n >> query;
	vector<int> prefix(n+1 , 0);
	vector<int> costs(n+1);
	for(int i=0 ; i<n ; i++){
		int x , cost;
		cin >> x >> cost;
		costs[i+1] = cost;
	}
	for(int i=1 ; i<=n ; i++){
		prefix[i] = prefix[i-1] + costs[i];
	}
	while(query--){
		int start , weight , best = 0;
		cin >> start >> weight;
		weight += prefix[start-1];
		int l = start , r = n;
		while(l <= r){
			int mid = l + (r - l) / 2;
			if(prefix[mid] >= weight){
				best = mid;
				r = mid - 1;
			} 
			else{
				l = mid + 1;
			}
		}
		cout << best << '\n';
	}
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 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 64 ms 4140 KB Output is correct
2 Correct 70 ms 4096 KB Output is correct

Subtask #3
0 / 40.0

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