Submission #1119292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119292		Dan4Life	Fountain (eJOI20_fountain)	C++17	100 / 100	768 ms	40268 KiB

fountain

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40