Submission #638399

#	Time	Username	Problem	Language	Result	Execution time	Memory
638399		Koful123	Fountain (eJOI20_fountain)	C++17	100 / 100	110 ms	18868 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define endl "\n"
#define mod 1000000007
#define int long long
#define double long double
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

void solve(){		

	int n,t;
	cin >> n >> t;

	vector<pair<int,int>> v(n),q[n];
	for(auto &[x,y] : v){
		cin >> x >> y;
	}

	vector<int> ans(t);
	for(int i=0;i<t;i++){
		int a,b; cin >> a >> b;
		q[a-1].pb({b,i});
	}

	vector<pair<int,pair<int,int>>> tmp;
	for(int i=n-1;i>=0;i--){
		while(tmp.size() && v[i].ff >= tmp.back().ss.ss){
			tmp.pop_back();
		}
		int add = (tmp.size() ? tmp.back().ff + v[i].ss : v[i].ss);
		tmp.push_back({add,{i,v[i].ff}});
		for(auto[x,y] : q[i]){
			if(x > add) ans[y] = 0;
			else{
				pair<int,pair<int,int>> p = {add-x,{1e18,1e18}};
				auto it = upper_bound(all(tmp),p);
				ans[y] = (*it).ss.ff + 1;
			}
		}
	}

	for(int x : ans){
		cout << x << endl;
	}
}

signed main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	int t = 1;
//	cin >> t;

	while(t--)
		solve();
	
	return 0;
}

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