제출 #1309193

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309193		ElayV13	Fountain (eJOI20_fountain)	C++20	100 / 100	540 ms	42880 KiB

fountain

//g++ -o sol sol.cpp
//C:\Users\Asus-1\OneDrive\Desktop
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define N 200001
const int INF = 1e18;
int n , q;
int d[100005] , c[100005];
int nxt[17][100005] , s[17][100005];
pair < int , int > get(int idx , int mid){
	int cur = c[idx];
	for(int i = 16;i >= 0;i--){
		if((1ll << i) & mid){
			cur += s[i][idx];
			idx = nxt[i][idx];
		}
	}
	return {cur , idx};
}
int st[17][100005] , lg[100005];
void buildst(){
	for(int i = 1;i <= n + 1;i++) st[0][i] = d[i];
	for(int i = 1;i < 17;i++)
	{
		for(int j = 1;j <= n + 1;j++)
		{
			if(j + (1ll << i) - 1 > (n + 1)) break;
			st[i][j] = max(st[i - 1][j] , st[i - 1][j + ((1ll << (i - 1)))]);
		}
	}
}
int get_max(int l , int r)
{
	int len = (r - l + 1);
	int LG = lg[len];
	return max(st[LG][l] , st[LG][r - (1ll << LG) + 1]);
}
signed main()
{
        ios_base::sync_with_stdio();
        cin.tie(0);
	cout.tie(0);
	lg[1] = 0;
	for(int i = 2;i < 100005;i++) lg[i] = lg[i / 2] + 1;
	cin >> n >> q;
	for(int i = 1;i <= n;i++) cin >> d[i] >> c[i];
	d[n + 1] = c[n + 1] = INF;
	buildst();
	for(int i = 1;i <= n;i++){
		int l = i , r = n + 1 , mn = INF;
		while(l <= r){
			int mid = (l + r) >> 1;
			if(get_max(i , mid) > d[i]){
				mn = min(mn , mid);
				r = mid - 1;
			}
			else l = mid + 1;
		}
		nxt[0][i] = mn;
		s[0][i] = c[mn];
	}
	for(int i = 1;i < 17;i++){
		for(int j = 1;j <= n;j++){
			nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
			int I = nxt[i - 1][j];
			s[i][j] = s[i - 1][j] + s[i - 1][I];
		}
	}
	while(q--){
		int idx , v;
		cin >> idx >> v;
		int l = 0 , r = n - idx + 1 , mn = INF;
		while(l <= r){
			int mid = (l + r) >> 1;
			pair < int , int > p = get(idx , mid);
			if(p.second == 0){
				mn = min(mn , mid);
				r = mid - 1;
				continue;
			}
			if(p.first >= v){
				mn = min(mn , mid);
				r = mid - 1;
			}
			else l = mid + 1;
		}
		int res = get(idx , mn).second;
		if(res == n + 1) res = 0;
		cout << res << "\n";
	}
}

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