oj.uz

Submission #974182

# Submission time Handle Problem Language Result Execution time Memory
974182 2024-05-03T04:52:05 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 327 ms 29868 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
	ll n,q;
	cin>>n>>q;
	
	vector<pair<ll,ll>> problem(n+2);
	for(ll i=1; i<=n; i++){
		ll u,v;
		cin>>u>>v;
		
		problem[i] = {u,v};
	}
	
	vector<pair<ll,ll>> query(q+2);
	vector<ll> cari[n+2];
	
	for(ll i=0; i<q; i++){
		ll u,v;
		cin>>u>>v;
		
		query[i] = {u,v};
		cari[u].push_back(v);
	}
	
	
	deque<ll> arr;
	deque<ll> suffix;
	map<pair<ll,ll>, ll> mp;
	
	
	for(ll i=n; 1<=i; i--){
		
		while(!arr.empty() && problem[arr[0]].first <= problem[i].first){
			arr.pop_front();
			suffix.pop_front();
		}
		
		arr.push_front(i);
		suffix.push_front(problem[i].second);
		
		if(suffix.size() != 1){
			suffix[0] += suffix[1];
		}
		
		if(cari[i].empty())continue;
		
		for(auto k : cari[i]){
			if(suffix[0] <k){
				mp[{i,k}] = 0;
				continue;
			}else if(k <= problem[i].second){
				mp[{i,k}] = i;
				continue;
			}
			
			ll l=0,r=suffix.size()-1, mid, last=r;
			while(l <= r){
				
				mid = l + (r-l)/2;
				ll tmp = suffix[0];
				if(mid != suffix.size()-1){
					tmp -= suffix[mid+1];
				}
				if(k <= tmp){
					//gak bisa
					r = mid - 1;
					last = mid;
					
				}else{
					//bisa
					l = mid + 1;
				}
			}
			
			mp[{i,k}] = arr[last];
			
		}
		
	}
	
	for(ll i=0; i<q; i++){
		cout<<mp[query[i]]<<"\n";
	}
	
	return 0;
}

Compilation message

fountain.cpp: In function 'int main()':
fountain.cpp:64:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     if(mid != suffix.size()-1){
      |        ~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 20640 KB Output is correct
2 Correct 212 ms 22380 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 176 ms 20640 KB Output is correct
9 Correct 212 ms 22380 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 110 ms 13516 KB Output is correct
12 Correct 327 ms 29868 KB Output is correct
13 Correct 248 ms 27992 KB Output is correct
14 Correct 259 ms 27544 KB Output is correct
15 Correct 232 ms 27732 KB Output is correct