oj.uz

Submission #637398

# Submission time Handle Problem Language Result Execution time Memory
637398 2022-09-01T15:55:09 Z VitaliyFS Fountain (eJOI20_fountain) C++17
100 / 100
 432 ms 47280 KB 
#include<bits/stdc++.h>

using namespace std;

#define fr first
#define sc second

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

const ll INF = 1000000000000000007, DIM = 200007, DIM2 = 27, MAXN = 100007, MOD = 1000000007;

ll tt, mid, res,f, b[DIM], R[DIM], dp[DIM2][DIM], par[DIM2][DIM], used[DIM], y, type, ptr, root, cnt, sum, pos, h, p, sx,sy, id, testcase, curans, nn, split, n, m, x, k1, k2, changecnt,k,l,r,v,u, l1,r1,l2,r2;
bool flag, flag2;
char c;
string s[DIM];
pll a[DIM];
stack<ll> q;

void solve() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		cin>>a[i].fr>>a[i].sc;
	}	
	for(int i=1;i<=n;i++){
		while(!q.empty() && a[q.top()].fr < a[i].fr) {
			R[q.top()] = i;
			q.pop();
		}
		q.push(i);
	}
	for(int i=n;i>=1;i--){
		par[0][i]=R[i];
		dp[0][i] = a[i].sc;
		for(int j=1;j<=20;j++) {
			par[j][i] = par[j - 1][par[j - 1][i]];
			dp[j][i] = dp[j - 1][i] + dp[j-1][par[j-1][i]];
		}
	}
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		for(int i=18;i>=0;i--) {
			if(y - dp[i][x]>0) {
				k=dp[i][x];
				y-=k;
				x=par[i][x];
			}
		}
		cout<<x<<'\n';
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	tt=1;
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	//cin>>tt;
	while(tt--) {
		solve();
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6868 KB Output is correct
2 Correct 4 ms 6996 KB Output is correct
3 Correct 4 ms 7124 KB Output is correct
4 Correct 5 ms 7188 KB Output is correct
5 Correct 5 ms 7252 KB Output is correct
6 Correct 6 ms 7284 KB Output is correct
7 Correct 5 ms 7252 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 44056 KB Output is correct
2 Correct 276 ms 41492 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6868 KB Output is correct
2 Correct 4 ms 6996 KB Output is correct
3 Correct 4 ms 7124 KB Output is correct
4 Correct 5 ms 7188 KB Output is correct
5 Correct 5 ms 7252 KB Output is correct
6 Correct 6 ms 7284 KB Output is correct
7 Correct 5 ms 7252 KB Output is correct
8 Correct 252 ms 44056 KB Output is correct
9 Correct 276 ms 41492 KB Output is correct
10 Correct 5 ms 7252 KB Output is correct
11 Correct 128 ms 28632 KB Output is correct
12 Correct 432 ms 47168 KB Output is correct
13 Correct 324 ms 46904 KB Output is correct
14 Correct 167 ms 46124 KB Output is correct
15 Correct 137 ms 47280 KB Output is correct