oj.uz

Submission #1119292

# Submission time Handle Problem Language Result Execution time Memory
1119292 2024-11-26T18:14:28 Z Dan4Life Fountain (eJOI20_fountain) C++17
100 / 100
 768 ms 40268 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
using ar2 = array<int,2>;
const int N = (int)1e6+10;
const int LG = 20;
int n, q, nxt;
int d[N], c[N], nx[N];
ar2 jmp[LG][N];
stack<int> S;

int32_t main(){
	cin >> n >> q;
	for(int i = 1; i <= n; i++) cin >> d[i] >> c[i];
	fill(nx,nx+n+1,n+1);
	for(int i = n; i >= 1; i--){
		while(sz(S) and d[i] >= d[S.top()]) S.pop();
		if(sz(S)) nx[i] = S.top();
		S.push(i);
	}
	for(int i = 1; i <= n; i++) jmp[0][i] = {nx[i], c[i]};
	for(int j = 1; j < LG; j++)
		for(int i = 1; i <= n; i++)
			nxt = jmp[j-1][i][0],
			jmp[j][i] = {jmp[j-1][nxt][0], jmp[j-1][i][1]+jmp[j-1][nxt][1]};
	for(int i = 1; i <= q; i++){
		int x, v; cin >> x >> v;
		for(int k = LG-1; k>=0; k--)
			if(jmp[k][x][0] and v>jmp[k][x][1])
				v-=jmp[k][x][1],x=jmp[k][x][0];
		if(x==n+1) x=0; cout << x << "\n";
	}
}

Compilation message

fountain.cpp: In function 'int32_t main()':
fountain.cpp:33:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   33 |   if(x==n+1) x=0; cout << x << "\n";
      |   ^~
fountain.cpp:33:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   33 |   if(x==n+1) x=0; cout << x << "\n";
      |                   ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 708 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 6 ms 852 KB Output is correct
7 Correct 5 ms 996 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 36940 KB Output is correct
2 Correct 534 ms 34608 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 708 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 5 ms 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 6 ms 852 KB Output is correct
7 Correct 5 ms 996 KB Output is correct
8 Correct 474 ms 36940 KB Output is correct
9 Correct 534 ms 34608 KB Output is correct
10 Correct 6 ms 1108 KB Output is correct
11 Correct 258 ms 21580 KB Output is correct
12 Correct 768 ms 40268 KB Output is correct
13 Correct 760 ms 39224 KB Output is correct
14 Correct 640 ms 38480 KB Output is correct
15 Correct 556 ms 38592 KB Output is correct