Submission #1015782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015782		elotelo966	Fountain (eJOI20_fountain)	C++17	100 / 100	195 ms	65104 KiB

fountain

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define OYY LLONG_MAX
#define mod 998244353
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 100005
#define fi first
#define se second

int d[lim],c[lim];

int up[lim][35],sz[lim][35];

int tree[4*lim];
int tut=-1,l;

inline void build(int node,int start,int end){
	if(start==end){
		tree[node]=d[start];
		return ;
	}
	build(node*2,start,mid),build(node*2+1,mid+1,end);
	tree[node]=max(tree[node*2],tree[node*2+1]);
}

inline void query(int node,int start,int end,int l,int r,int ara){
	if(start>end || start>r || end<l || tree[node]<ara || ~tut)return ;
	if(start>=l && end<=r && start==end){
		tut=start;
		return ;
	}
	query(node*2,start,mid,l,r,ara),query(node*2+1,mid+1,end,l,r,ara);
}

int32_t main(){
	faster
	int n,q;cin>>n>>q;
	l=ceil(log2(n));
	FOR{
		cin>>d[i]>>c[i];
	}
	
	build(1,1,n);
	
	
	FOR{
		tut=-1;
		query(1,1,n,i,n,d[i]+1);
		if(tut==-1)tut=0;
		up[i][0]=tut;
		sz[i][0]=c[tut];
		if(!tut)sz[i][0]=INT_MAX;
	}
	
	for(int i=n;i>=1;i--){
		for(int j=1;j<=l;j++){
			up[i][j]=up[up[i][j-1]][j-1];
			sz[i][j]=sz[i][j-1]+sz[up[i][j-1]][j-1];
		}
	}
	/*
	FOR{
		cout<<i<<endl;
		for(int j=0;j<=l;j++)cout<<up[i][j]<<" ";
		cout<<endl;
	}
	
	FOR{
		cout<<i<<endl;
		for(int j=0;j<=l;j++)cout<<sz[i][j]<<" ";
		cout<<endl;
	}*/
	
	while(q--){
		int x,cost;cin>>x>>cost;
		if(c[x]>=cost){
			cout<<x<<'\n';
			continue;
		}
		cost-=c[x];
		int cur=0;
		for(int i=l;i>=0;i--){
			if(cur+sz[x][i]<cost){
				cur+=sz[x][i];
				x=up[x][i];
			}
		}
		cout<<up[x][0]<<'\n';
	}
	return 0;
}

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