Submission #909956

#	Time	Username	Problem	Language	Result	Execution time	Memory
909956		dsyz	Fountain (eJOI20_fountain)	C++17	100 / 100	118 ms	13352 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,Q;
	cin>>N>>Q;
	pair<ll,ll> arr[N]; //dimater, capacity
	for(ll i = 0;i < N;i++){
		cin>>arr[i].first>>arr[i].second;
	}
	vector<pair<ll,pair<ll,ll> > > qu;
	for(ll q = 0;q < Q;q++){
		ll R,V;
		cin>>R>>V;
		R--;
		qu.push_back({R,{V,q}});
	}
	sort(qu.begin(),qu.end(),greater<pair<ll,pair<ll,ll> > >());
	ll ans[Q];
	ll ptr = N;
	deque<pair<pair<ll,ll>,ll> > dq;
	deque<ll> sufsum;
	for(ll q = 0;q < Q;q++){
		ll R = qu[q].first;
		ll V = qu[q].second.first;
		ll ind = qu[q].second.second;
		while(ptr >= 1 && ptr - 1 >= R){
			ptr--;
			while(!dq.empty() && dq.front().first.first <= arr[ptr].first){
				dq.pop_front();
				sufsum.pop_front();
			}
			dq.push_front({{arr[ptr].first,arr[ptr].second},ptr});
			if(sufsum.empty()) sufsum.push_front(arr[ptr].second);
			else sufsum.push_front(sufsum.front() + arr[ptr].second);
		}
		if(V > sufsum.front()){
			ans[ind] = 0; //flow of water ends in waterways
		}else{
			ll high = dq.size() - 1;
			ll low = -1;
			while(high - low > 1){ //binary search for minimum index with prefix sum >= V
				ll mid = (high + low) / 2;
				ll after = 0;
				if(mid < ll(sufsum.size()) - 1) after = sufsum[mid + 1];
				if(sufsum.front() - after >= V){
					high = mid;
				}else{
					low = mid;
				}
			}
			ans[ind] = dq[high].second + 1;
		}
	}
	for(ll q = 0;q < Q;q++){
		cout<<ans[q]<<'\n';
	}
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40