oj.uz

Submission #894543

# Submission time Handle Problem Language Result Execution time Memory
894543 2023-12-28T12:04:32 Z Nurislam Fountain (eJOI20_fountain) C++14
100 / 100
 208 ms 71236 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
///*                                                    __                    __                        __                    */
///*        ======     _      /| /|  __   _            /   |  |   /|  |   @  |    |  |  | /   /| |\  | /   |  |  @ | /        */
///* \-       ||  |_| |_     / |/ | |  | |_  |-        |   |--|  /-|  |   |  \ \  |==|  |-   /=| | \ | |   |--|  | |-         */
///*          ||  | | |_    /     | |__|  _| |_        \__ |  | /  |  |__ |  __|  |  |  | \ /  | |  \| \__ |  |  | | \        */
///*  
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<vi> vv;
const int N = 3e5;
vi g[N];
vii v(N);
int up[20][N];
int pr[N];
void dfs(int pos, int pre){
	pr[pos] += v[pos].ss;
	up[0][pos] = pre;
	for(int i = 1; i < 18; i++){
		up[i][pos] = up[i-1][up[i-1][pos]];
	}
	for(int to:g[pos]){
		if(to == pre)continue;
		pr[to] = pr[pos];
		dfs(to, pos);
	}
}
int isnp;
bool upper(int x, int sum){
	if(pr[isnp] - pr[up[0][x]] >= sum)return true;
	return false;
}
int lca(int pos, int sum){
	if(pr[pos] - pr[up[0][pos]] >= sum)return pos;
	for(int i = 17; i >= 0; i--){
		if(!upper(up[i][pos], sum)){
			pos = up[i][pos];
		}
	}
	return up[0][pos];
}
void solve(){
	int n, q;
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> v[i].ff >> v[i].ss;
	}
	stack<int> s;
	for(int i = n; i > 0; i--){
		while(!s.empty() && v[s.top()].ff <= v[i].ff)s.pop();
		if(s.empty()){
			g[0].pb(i);
		}else{
			g[s.top()].pb(i);
		}
		s.push(i);
	}
	dfs(0, -1);
	while(q--){
		int x, sum;
		cin >> x >> sum;
		isnp = x;
		cout << lca(x, sum) << '\n';
	}
}
main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int test = 1;
	//~ cin >> test;
	while(test--){
		solve();
	}
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 51032 KB Output is correct
2 Correct 8 ms 51036 KB Output is correct
3 Correct 9 ms 51036 KB Output is correct
4 Correct 8 ms 51036 KB Output is correct
5 Correct 10 ms 51036 KB Output is correct
6 Correct 9 ms 51036 KB Output is correct
7 Correct 8 ms 51036 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 69200 KB Output is correct
2 Correct 167 ms 69084 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 51032 KB Output is correct
2 Correct 8 ms 51036 KB Output is correct
3 Correct 9 ms 51036 KB Output is correct
4 Correct 8 ms 51036 KB Output is correct
5 Correct 10 ms 51036 KB Output is correct
6 Correct 9 ms 51036 KB Output is correct
7 Correct 8 ms 51036 KB Output is correct
8 Correct 160 ms 69200 KB Output is correct
9 Correct 167 ms 69084 KB Output is correct
10 Correct 8 ms 51036 KB Output is correct
11 Correct 77 ms 61268 KB Output is correct
12 Correct 208 ms 71236 KB Output is correct
13 Correct 194 ms 65048 KB Output is correct
14 Correct 198 ms 63572 KB Output is correct
15 Correct 119 ms 62584 KB Output is correct