제출 #1281073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281073		silence25	Fountain (eJOI20_fountain)	C++20	30 / 100	275 ms	589824 KiB

fountain

#include "bits/stdc++.h"
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
const long long maxn = 1e5+10;
const long long inf = 1e9+7;
long long d[maxn];
long long c[maxn];
long long F[maxn];
long long n,q;
long long dp[maxn];
vector<long long>g[maxn];

void upd(long long x,long long idx){
	for(;x;x-=x&(-x))
		F[x]=idx;
}

long long get(long long x){
	long long res=inf;
	for(;x<=1e5+5;x+=x&(-x)){
		if(F[x]>0)
			res=min(res,F[x]);
	}
	return res;
}

void solve(){
	vector<long long>com;
	cin>>n>>q;
	for(long long i=1;i<=n;++i)
		F[i]=inf;
	for(long long i=1;i<=n;++i){
		cin>>d[i]>>c[i];
		com.pb(d[i]);
	}
	sort(com.begin(),com.end());
	com.erase(unique(all(com)),com.end());
	for(long long i=n;i>=1;--i){
		d[i]=lower_bound(all(com),d[i])-com.begin()+1;
		long long res=get(d[i]+1);
		if(res==inf){
			res=0;
		}
		else{
			g[i] = g[res];
			res=dp[res];
		}
		g[i].pb(i);
		dp[i]=res+c[i];
		upd(d[i],i);
	}
	for(long long i = 1;i<=n;++i)
		reverse(all(g[i]));
	while(q--){
		long long p,v;
		cin>>p>>v;
		vector<long long>k = g[p];
		long long l = 0,r = k.size()-1;
		long long ans = -1;
		while(l<=r){
			long long mid = l + (r-l)/2;
			if(dp[p] - dp[k[mid]] + c[k[mid]] >= v){
				ans = mid;
				r = mid-1;
			}else{
				l = mid+1;
			}
		}
		if(ans == -1){
			cout<<0<<endl;
		}else{
			cout<<k[ans]<<endl;
		}
	}
}

int main(){
	// freopen("file.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
}

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