oj.uz

Submission #827338

# Submission time Handle Problem Language Result Execution time Memory
827338 2023-08-16T11:23:35 Z ZeroCool Fountain (eJOI20_fountain) C++14
100 / 100
 552 ms 37604 KB 
#include <bits/stdc++.h>
#define int long long
#define ll long long
#define ld long double
using namespace std;
 
const int mxn = 1e5 + 5;
const int SQRT = 500;
const int LOG = 20;
const int inf = 1e18;
const int mod = 998244353;
const ld eps = 1e-9;

int up[mxn][LOG];
int st[mxn][LOG];

void solve(int T){
	int n,q;
	cin>>n>>q;

	stack<pair<int,int> > qu;
	

	for(int i = 1;i<=n;i++){
		int l;
		cin>>l;
		cin>>st[i][0];

		while(qu.size() && l > qu.top().first){
			up[qu.top().second][0] = i;
			qu.pop();
		}
		qu.push({l,i});
	}
	for(int j = 1;j<LOG;j++){
		for(int i = 1;i<=n;i++){
			up[i][j] = up[up[i][j-1]][j-1];
			st[i][j] = st[i][j-1] + st[up[i][j-1]][j-1];
		}
	}

	while(q--){
		int a,b;
		cin>>a>>b;

		for(int i = LOG-1;i>=0;i--){
			if(st[a][i] < b){
				b -= st[a][i];
				a = up[a][i];

			}
		}

		cout<<a<<endl;
	}

}
int32_t main(){
	#ifdef ONLINE_JUDGE
    ios::sync_with_stdio(false);
    cin.tie(0);
	#endif
	int t = 1;
	//cin>>t;

	for(int i = 1;i<=t;i++)solve(i);
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 4 ms 580 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 33748 KB Output is correct
2 Correct 412 ms 31552 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 4 ms 580 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 374 ms 33748 KB Output is correct
9 Correct 412 ms 31552 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 197 ms 19972 KB Output is correct
12 Correct 552 ms 36808 KB Output is correct
13 Correct 451 ms 36428 KB Output is correct
14 Correct 421 ms 35640 KB Output is correct
15 Correct 396 ms 37604 KB Output is correct