oj.uz

Submission #894334

# Submission time Handle Problem Language Result Execution time Memory
894334 2023-12-28T06:16:51 Z Minbaev Fountain (eJOI20_fountain) C++17
100 / 100
 276 ms 79528 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pii pair<int,int>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
#define f first
#define s second
#define pii pair<int,int>
template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;}
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update> ordered_set;
const int mod= 1e17 +7;
const int N=1e5*4;

int binpow (int a, int n) {
	if (n == 0)
		return 1;
	if (n % 2 == 1)
		return binpow (a, n-1) * a;
	else {
		int b = binpow (a, n/2);
		return b * b;
	}
}
vector<pii>v;
int n, q, timer;
int tin[N], tout[N];
int sum[N];
int up[20][N];
vector <int> g[N];

void dfs(int v, int pr) {
    tin[v] = ++timer;
    up[0][v] = pr;
    for (int i = 1; i <= 17; i++) {
        up[i][v] = up[i - 1][ up[i - 1][v] ];
    }
    for (int to : g[v]) {
        if (to == pr) continue;
        dfs(to, v);
    }
    tout[v] = timer;
}
int ind;
bool upper(int a, int b) {
    //true up
    if(sum[ind] - sum[up[0][a]] >= b)return true;
    else return false;
    
}

int lca(int a, int b) {
    
    if(sum[a]-sum[up[0][a]]>=b)return a;
    
    for (int i = 17; i >= 0; i--) {
        if (!upper(up[i][a], b)) {
            a = up[i][a];
        }
    }
    return up[0][a];

}

void dfs1(int x,int pr){
	sum[x] += v[x].s;
	
	for(auto to:g[x]){
		if(to==pr)continue;
	
		sum[to] = sum[x];
		
		dfs1(to,x);
		
	}
}
	
	
	
	
void solve(){

	
	cin>>n>>q;
	v.pb({0,mod});
	for(int i = 1;i <= n;i++){
		int a,b;
		cin>>a>>b;
		v.pb({a,b});
	}
	stack<int>s;
	for(int i=n;i>0;--i)
	{	
		while(!s.empty() and v[s.top()].f<=v[i].f)
		{
			s.pop();
		}
		if(s.empty())
		{
			g[0].pb(i);
		}
		else
		{
			g[s.top()].pb(i);
		}
		s.push(i);
	}
	
	dfs(0,0);
	dfs1(0,-1);
	
	
	while(q--){
		int a,b;
		cin>>a>>b;
		//~ cout<<sum[a]<<" "<<sum[up[0][a]]<<" ";
		ind = a;
		cout<<lca(a,b)<<"\n";
	}
	
	
	
	
}

 signed main()
{
//	freopen("seq.in", "r", stdin);
//  freopen("seq.out", "w", stdout);
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
	int tt=1;//cin>>tt;
	while(tt--)solve();

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 51800 KB Output is correct
2 Correct 7 ms 51804 KB Output is correct
3 Correct 7 ms 51976 KB Output is correct
4 Correct 7 ms 51804 KB Output is correct
5 Correct 9 ms 52060 KB Output is correct
6 Correct 8 ms 51804 KB Output is correct
7 Correct 9 ms 52060 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 77508 KB Output is correct
2 Correct 146 ms 74828 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 51800 KB Output is correct
2 Correct 7 ms 51804 KB Output is correct
3 Correct 7 ms 51976 KB Output is correct
4 Correct 7 ms 51804 KB Output is correct
5 Correct 9 ms 52060 KB Output is correct
6 Correct 8 ms 51804 KB Output is correct
7 Correct 9 ms 52060 KB Output is correct
8 Correct 185 ms 77508 KB Output is correct
9 Correct 146 ms 74828 KB Output is correct
10 Correct 7 ms 51804 KB Output is correct
11 Correct 75 ms 62740 KB Output is correct
12 Correct 236 ms 79528 KB Output is correct
13 Correct 232 ms 73556 KB Output is correct
14 Correct 276 ms 72016 KB Output is correct
15 Correct 109 ms 71368 KB Output is correct