oj.uz

Submission #894240

# Submission time Handle Problem Language Result Execution time Memory
894240 2023-12-28T03:05:11 Z Minbaev Fountain (eJOI20_fountain) C++17
60 / 100
 59 ms 6408 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
	int n,m,k;
	
	cin>>n>>m;
	int v[n][2]{};
	
	for(int i = 0;i<n;i++){
		cin>>v[i][0]>>v[i][1];
	}
	
	if(m<=2000){		
		while(m--){
			int a,b;
			cin>>a>>b;
			
			int last = -1, cnt = b;
			for(int i = a - 1;i<n;i++){
				if((last!=-1&&v[last][0]>=v[i][0]))continue;
				if(v[i][1]>=cnt){
					cout<<i+1<<"\n";
					cnt = 0;
					break;
				}
				else{
					cnt -= v[i][1];
					last = i;
				}
			}
			if(cnt>0)cout<<0<<"\n";
		}
		return;
	}
	else{
		vector<int>pref(n+1);
		
		for(int i = 1;i<=n;i++){
			pref[i] = pref[i-1];
			pref[i] += v[i-1][1];
		}
		
		while(m--){
			int a,b;
			cin>>a>>b;
			
			int dif = pref[a - 1];
			int l = a,r = n,ans = 0;
			while(l<=r){
				int mid = (l+r) / 2;
				if(pref[mid] - dif >= b){
					ans = mid ;
					r = mid - 1;
				}
				else {
					l = mid + 1;
				}
			}
			cout<<ans<<"\n";
		}
		
	}
	
	
	
	
	
	
	
}

 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt;
	while(tt--)solve();

}

Compilation message

fountain.cpp: In function 'void solve()':
fountain.cpp:6:10: warning: unused variable 'k' [-Wunused-variable]
    6 |  int n,m,k;
      |          ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 6132 KB Output is correct
2 Correct 59 ms 6408 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 57 ms 6132 KB Output is correct
9 Correct 59 ms 6408 KB Output is correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -