Submission #974182

#	Time	Username	Problem	Language	Result	Execution time	Memory
974182		vjudge1	Fountain (eJOI20_fountain)	C++17	100 / 100	327 ms	29868 KiB

fountain

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40