oj.uz

Submission #908224

# Submission time Handle Problem Language Result Execution time Memory
908224 2024-01-16T09:53:27 Z shoryu386 Fountain (eJOI20_fountain) C++17
100 / 100
 790 ms 46536 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

main(){
	int n, q;
	cin >> n >> q;
	
	int diam[n], cap[n];
	for (int x = 0; x < n; x++) cin >> diam[x] >> cap[x];
	
	//2k decomp
	
	stack<int> stk;
	int nextLargest[n];
	
	for (int x = 0; x < n; x++) nextLargest[x] = n;
	
	for (int x = 0; x < n; x++){
		while (!stk.empty() && diam[x] > diam[stk.top()]){
			nextLargest[stk.top()] = x;
			stk.pop();
		}
		
		stk.push(x);
	}
	
	pair<int, int> twok[100007][25];
	memset(twok, -1, sizeof(twok));
	
	for (int x = 0; x < n; x++){
		twok[x][0] = {nextLargest[x], cap[x]};
		
		//cout << nextLargest[x] << ' ';
	}
	
	for (int z = 0; z < 24; z++){
		for (int x = 0; x < n; x++){
			if (twok[x][z].first != -1 && twok[ twok[x][z].first ][z].first != -1){
				twok[x][z+1] = { twok[ twok[x][z].first ][z].first, twok[x][z].second + twok[ twok[x][z].first ][z].second };
			}
		}
	}
	
	for (int x = 0; x < q; x++){
		int res, water; cin >> res >> water;
		res--;
		
		int cursum = water;
		for (int z = 24; z > -1; z--){
			if (twok[res][z].first != -1){
				if (cursum > twok[res][z].second){
					cursum -= twok[res][z].second;
					res = twok[res][z].first;
				}
			} 
		}
		
		if (res == n) cout << 0 << '\n';
		else cout << res+1 << '\n';
	}
	
	
	
	
}

Compilation message

fountain.cpp:6:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    6 | main(){
      | ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39508 KB Output is correct
2 Correct 29 ms 39592 KB Output is correct
3 Correct 38 ms 39336 KB Output is correct
4 Correct 41 ms 39592 KB Output is correct
5 Correct 33 ms 39596 KB Output is correct
6 Correct 37 ms 39512 KB Output is correct
7 Correct 33 ms 39512 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 44884 KB Output is correct
2 Correct 528 ms 45084 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 39508 KB Output is correct
2 Correct 29 ms 39592 KB Output is correct
3 Correct 38 ms 39336 KB Output is correct
4 Correct 41 ms 39592 KB Output is correct
5 Correct 33 ms 39596 KB Output is correct
6 Correct 37 ms 39512 KB Output is correct
7 Correct 33 ms 39512 KB Output is correct
8 Correct 529 ms 44884 KB Output is correct
9 Correct 528 ms 45084 KB Output is correct
10 Correct 31 ms 39516 KB Output is correct
11 Correct 259 ms 43212 KB Output is correct
12 Correct 790 ms 46456 KB Output is correct
13 Correct 583 ms 46124 KB Output is correct
14 Correct 523 ms 45452 KB Output is correct
15 Correct 490 ms 46536 KB Output is correct