Submission #931632

#	Time	Username	Problem	Language	Result	Execution time	Memory
931632		vjudge1	Fountain (eJOI20_fountain)	C++17	0 / 100	280 ms	12032 KiB

fountain

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(), x.end()

const int mod = 1e9 + 7;
const int N = 500001;

using namespace std;

ll n, m, t[800001], dp[200001], a, b;
pair <ll, ll> p[200001];

ll gcd (ll a, ll b){while (a > 0 && b > 0){if (a >= b){a %= b;}else{b %= a;}}return a + b;}
ll binpow (ll a, ll b){
	a %= mod;if (b == 0){return 1;}
	else if (b % 2 == 1){
		return binpow (a, b - 1) % mod * a % mod;
	}
	else{
		ll t = binpow (a, b / 2) % mod;
		return t * t % mod;
	}
}

void build (ll tl = 1, ll tr = n, ll v = 1){
	if (tl == tr){
		t[v] = p[tl].F;
		return;
	}
	ll tm = (tl + tr) / 2;
	build (tl, tm, v * 2);
	build (tm + 1, tr, v * 2 + 1);
	t[v] = max (t[v * 2], t[v * 2 + 1]);
}

ll get (ll l, ll r, ll tl = 1, ll tr = n, ll v = 1){
	if (r < tl || tr < l){
		return 0;
	}
	if (l <= tl && tr <= r){
		return t[v];
	}
	ll tm = (tl + tr) / 2;
	return max (get (l, r, tl, tm, v * 2), get (l, r, tm + 1, tr, v * 2 + 1));
}

void Jemirlan(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> p[i].F >> p[i].S;
	}
	build ();
	dp[n] = p[n].S;
	for (int i = n - 1; i >= 1; i--){
		ll l = i + 1, r = n;
		while (l <= r){
			ll md = (l + r) / 2;
			if (get (i + 1, md) > p[i].F){
				r = md - 1;
			}
			else{
				l = md + 1;
			}
		}
		dp[i] = p[i].S;
		if (l <= n){
			dp[i] += dp[l];
		}
	}
	for (int i = 1; i <= n; i++){
		cout << dp[i] << ' ';
	}
	while (m--){
		cin >> a >> b;
		if (dp[a] < b){
			cout << "0\n";
		}
		else{
			cout << "blmim\n";
		}
	}
}

signed main (/*JALEM*/){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll tt = 1;
//	cin >> tt;
	for (int i = 1; i <= tt; i++){
//		cout << "Case " << i << ": ";
		Jemirlan();
	}
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40