oj.uz

Submission #1015782

# Submission time Handle Problem Language Result Execution time Memory
1015782 2024-07-06T18:57:50 Z elotelo966 Fountain (eJOI20_fountain) C++17
100 / 100
 195 ms 65104 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4612 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 59220 KB Output is correct
2 Correct 183 ms 58448 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4612 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 133 ms 59220 KB Output is correct
9 Correct 183 ms 58448 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 54 ms 38680 KB Output is correct
12 Correct 195 ms 65104 KB Output is correct
13 Correct 124 ms 64552 KB Output is correct
14 Correct 106 ms 63864 KB Output is correct
15 Correct 83 ms 64336 KB Output is correct