oj.uz

Submission #1092896

# Submission time Handle Problem Language Result Execution time Memory
1092896 2024-09-25T10:12:17 Z Sunbae Fountain (eJOI20_fountain) C++17
100 / 100
 401 ms 25936 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2656 KB Output is correct
3 Correct 1 ms 2656 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2912 KB Output is correct
7 Correct 2 ms 2824 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 23516 KB Output is correct
2 Correct 286 ms 22352 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2656 KB Output is correct
3 Correct 1 ms 2656 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 2 ms 2912 KB Output is correct
7 Correct 2 ms 2824 KB Output is correct
8 Correct 256 ms 23516 KB Output is correct
9 Correct 286 ms 22352 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct
11 Correct 124 ms 11256 KB Output is correct
12 Correct 401 ms 25936 KB Output is correct
13 Correct 298 ms 19024 KB Output is correct
14 Correct 93 ms 16976 KB Output is correct
15 Correct 64 ms 15836 KB Output is correct