Submission #1092896

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092896		Sunbae	Fountain (eJOI20_fountain)	C++17	100 / 100	401 ms	25936 KiB

fountain

#include <bits/stdc++.h>
#define z exit(0)
using namespace std;
const int N = 1e5 + 5;
vector<int> g[N];
int a[N], b[N], dep[N], dp[N], st[N], up[N][17], sz, LOG;
void dfs(int u){
	for(int j = 1; j<LOG; ++j) up[u][j] = up[up[u][j-1]][j-1];
	for(int v: g[u]){
		dep[v] = dep[u] + 1; dp[v] = dp[u] + b[v]; dfs(v);
	}
}

int kth_anc(int u, int k){ for(int j = LOG-1; j>=0; --j) if(k>>j&1) u = up[u][j]; return u;}
signed main(){
	int n, q; scanf("%d %d", &n, &q); LOG = 32 - __builtin_clz(n);
	for(int i = 0; i<n; ++i) scanf("%d %d", a+i, b+i);
	for(int i = n-1; i>=0; --i){
		while(sz && a[st[sz-1]] <= a[i]) --sz;
		up[i][0] = sz ? st[sz-1] : n;
		st[sz++] = i;
	}	
	up[n][0] = n;
	for(int i = 0; i<n; ++i) g[up[i][0]].push_back(i);
	dfs(n);
	while(q--){
		int u, w; scanf("%d %d", &u, &w); --u;
		int low = 0, high = dep[u], ans;
		while(low <= high){
			int mid = low + ((high-low)>>1), anc = kth_anc(u, mid);
			int tmp = ((anc != n) ? dp[u] - dp[up[anc][0]] : 2e9);
			if(tmp >= w) high = mid-1, ans = anc;
			else low = mid+1;
		}
		if(ans < n) printf("%d\n", ans + 1);
		else puts("0");
	}
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:16:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  int n, q; scanf("%d %d", &n, &q); LOG = 32 - __builtin_clz(n);
      |            ~~~~~^~~~~~~~~~~~~~~~~
fountain.cpp:17:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |  for(int i = 0; i<n; ++i) scanf("%d %d", a+i, b+i);
      |                           ~~~~~^~~~~~~~~~~~~~~~~~~
fountain.cpp:27:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   int u, w; scanf("%d %d", &u, &w); --u;
      |             ~~~~~^~~~~~~~~~~~~~~~~
fountain.cpp:35:21: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   35 |   if(ans < n) printf("%d\n", ans + 1);
      |               ~~~~~~^~~~~~~~~~~~~~~~~

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