제출 #1308831

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

fountain

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

#define int long long
const int INF = 1e18;
int n , q;
int d[100001] , c[100001];
int nxt[20][100001] , s[20][100001];
void build(){
	for(int i = 1;i <= n;i++){
		for(int j = i;j <= n;j++){
			if(d[j] > d[i]){
				nxt[0][i] = j;
				s[0][i] = c[i] + c[j];
				break;
			}
		}
	}
	for(int i = 1;i < 20;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] - c[I];
		}
	}
}
signed main()
{
	ios_base::sync_with_stdio();
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	for(int i = 1;i <= n;i++) cin >> d[i] >> c[i];
	build();
	while(q--){
		int idx , v;
		cin >> idx >> v;
		for(int i = 19;i >= 0;i--){
			if(nxt[i][idx] == 0) continue;
			if(v >= s[i][idx]){
				v -= s[i][idx];
				idx = nxt[i][idx];
				idx = nxt[0][idx];
			}
		}
		if(!idx){
			cout << idx << endl;
			continue;
		}
		int cur = idx;
		int res;
		while(1){
			if(v - c[cur] > 0){
				v -= c[cur];
				cur = nxt[0][cur];
				if(cur == 0){
					res = 0;
					break;
				}
			}
			else{
				res = cur;
				break;
			}
		}
		cout << res << endl;
	}
}

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