Submission #1279645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279645		blacktulip	Fountain (eJOI20_fountain)	C++17	100 / 100	192 ms	35968 KiB

fountain

//Hello!..
//dört böler altı artı iki ama ne böler altı ne böler iki
//Başarı, Boş Duranın Hakkı Değil... Koşturanın Hakkıdır. Hakan?
//Ne yapayım, elimden gelen bu :(
//S'il vous plait
#include <bits/stdc++.h>
using namespace std;

typedef long long lo; 

#define fi first
#define se second
#define endl "\n"
#define pb push_back
#define int long long
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define setrandom mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define getrandom(a,b) uniform_int_distribution<int>(a,b)(rng)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
#define _ << " " <<

const lo inf = 1000000000;
const lo li = 200005;
const lo mod = 1000000007;

int n,m,a[li],k,flag,t,d[li],c[li],fa[li][20],cap[li][20];
int cev;
string s;
vector<int> v;

int32_t main(){
	fio();
	cin>>n>>t;
	for(int i=1;i<=n;i++){
		cin>>d[i]>>c[i];
		cap[i][0]=c[i];
	}
	for(int j=0;j<=19;j++){
		fa[n+1][j]=n+1;
		cap[n+1][j]=inf;
	}
	stack<pair<int,int>> st;
	for(int i=n;i>=1;i--){
		while(st.size() && st.top().fi<=d[i])st.pop();
		if(st.size())fa[i][0]=st.top().se;
		else fa[i][0]=n+1;
		st.push({d[i],i});
	}
	for(int j=1;j<=19;j++){
		for(int i=1;i<=n;i++){
			fa[i][j]=fa[fa[i][j-1]][j-1];
			cap[i][j]=cap[i][j-1]+cap[fa[i][j-1]][j-1];
		}
	}
	while(t--){
		int x;
		cin>>x>>k;
		for(int i=19;i>=0;i--){
			if(cap[x][i]<k){
				k-=cap[x][i];
				x=fa[x][i];
			}
		}
		if(x==n+1)x=0;
		cout<<x<<endl;
	}
	return 0;
}

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