Submission #614014

#	Time	Username	Problem	Language	Result	Execution time	Memory
614014		karelisp	Fountain (eJOI20_fountain)	C++14	100 / 100	336 ms	56716 KiB

fountain

#include <bits/stdc++.h>
using namespace std;

int N, Q, up[100005][30];
long long D[100005], C[100005], suffix_max[100005], dp[100005][30];
int st[400005];
vector<int> adj[100005];

void build(int v=1, int start=1, int end=N){
	if(start==end){
		st[v] = D[start];
		return;
	}

	int mid = (start+end)/2;
	build(2*v, start, mid);
	build(2*v+1, mid+1, end);
	st[v] = max(st[2*v], st[2*v+1]);
}

int first_greater(int l, int r, int val, int v=1, int start=1, int end=N){
	if(l==start && r==end){
		if(st[v] <= val) return 0;

		while(start<end){
			int mid = (start+end)/2;
			if(st[2*v] > val){
				v = 2*v;
				end = mid;
			}
			else{
				v = 2*v+1;
				start = mid+1;
			}
		}
		return start;
	}

	int mid = (start+end)/2;
	if(r<=mid) return first_greater(l,r,val,2*v,start,mid);
	else if(l>mid) return first_greater(l,r,val,2*v+1,mid+1,end);
	else{
		int pos = first_greater(l,mid,val,2*v,start,mid);
		if(pos!=0)
			return pos;
		else
			return first_greater(mid+1,r,val,2*v+1,mid+1,end);
	}
}

void dfs(int v, int p){
	up[v][0] = p;
	dp[v][0] = C[v];

	for(int i=1; i<=ceil(log2(N)); i++){
		up[v][i] = up[up[v][i-1]][i-1];
		dp[v][i] = dp[v][i-1] + dp[up[v][i-1]][i-1];
	}

	for(auto u : adj[v])
		dfs(u,v);
}

int main(){
	scanf("%d%d", &N, &Q);
	for(int i=1; i<=N; i++)
		scanf("%lld%lld", &D[i], &C[i]);

	build();
	
	adj[0].push_back(N);
	for(int i=1; i<N; i++){
		int j = first_greater(i+1, N, D[i]); 
		adj[j].push_back(i);
	}
	
	C[0] = 1e9;
	dfs(0,0);

	for(int R, V, q=0; q<Q; q++){
		scanf("%d%d", &R, &V);
		for(int i=ceil(log2(N)); i>=0; i--){
			if(dp[R][i] < V){
				V -= dp[R][i];
				R = up[R][i];
			}
		}
		printf("%d\n", R);
	}

	return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d", &N, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~
fountain.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%lld%lld", &D[i], &C[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |   scanf("%d%d", &R, &V);
      |   ~~~~~^~~~~~~~~~~~~~~~

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