oj.uz

답안 #909956

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
909956 2024-01-17T16:41:05 Z dsyz Fountain (eJOI20_fountain) C++17
100 / 100
 118 ms 13352 KB 
#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.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 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 344 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 9412 KB Output is correct
2 Correct 84 ms 10848 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 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 344 KB Output is correct
8 Correct 75 ms 9412 KB Output is correct
9 Correct 84 ms 10848 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 44 ms 5072 KB Output is correct
12 Correct 118 ms 13352 KB Output is correct
13 Correct 97 ms 10932 KB Output is correct
14 Correct 80 ms 9912 KB Output is correct
15 Correct 71 ms 10416 KB Output is correct