Submission #913413

#	Time	Username	Problem	Language	Result	Execution time	Memory
913413		blackscreen1	Fountain (eJOI20_fountain)	C++17	100 / 100	524 ms	38656 KiB

fountain

#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define ld long double
#define iloop(m, h) for (ll i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i != h; i += g)
#define jloop_(m, h, g) for (auto j = m; j != h; j += g)
#define kloop_(m, h, g) for (auto k = m; k != h; k += g)
#define lloop_(m, h, g) for (auto l = m; l != h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n, q;
	cin >> n >> q;
	ll d[n], c[n];
	iloop(0, n) cin >> d[i] >> c[i];
	ll twok[n][20], tot[n][20];
	memset(twok, -1, sizeof(twok));
	iloop(0, n) jloop(0, 20) tot[i][j] = INF;
	stack<ll> mono;
	iloop(n-1, -1) {
		while (mono.size() && d[mono.top()] <= d[i]) mono.pop();
		if (mono.size()) {
			twok[i][0] = mono.top();
			tot[i][0] = c[i] + c[twok[i][0]];
			jloop(1, 20) {
				if (twok[i][j-1] == -1) break;
				twok[i][j] = twok[twok[i][j-1]][j-1];
				if (twok[i][j] != -1) tot[i][j] = tot[i][j-1] + tot[twok[i][j-1]][j-1] - c[twok[i][j-1]];
			}
		}
		mono.push(i);
	}
	ll t1, t2;
	while (q--) {
		cin >> t1 >> t2;
		t1--;
		if (t2 <= c[t1]) {cout << t1+1 << "\n"; continue;}
		iloop(19, -1) {
			if (t1 == -1) break;
			if (t2 > tot[t1][i]) {
				t2 -= tot[t1][i] - c[twok[t1][i]];
				t1 = twok[t1][i];
			}
		}
		t1 = twok[t1][0];
		cout << t1+1 << "\n";
	}
}

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