Submission #912071

#	Time	Username	Problem	Language	Result	Execution time	Memory
912071		WH8	Fountain (eJOI20_fountain)	C++14	100 / 100	135 ms	32568 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vi vector<int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define int long long
#define endl '\n'
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cout << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);

#define maxn 100005
#define maxq 200005

vector<vector<pll>> qs(maxn);
int n, q;
int dia[maxn], cap[maxn]; 
int ans[maxq];

vector<vector<int>> al(maxn);

int os = 0;

vector<pll> cv {{1e15, 0}};

void dfs(int x){
	/*cout << endl;
	dg(x);
	dg(os);
	cout << "CV IS : ";
	for (auto it : cv) cout << it.f << "," << it.s << " | ";
	cout << endl;*/

	for (auto it : qs[x]){
		// answer queries
		int l = 0, r = cv.size() - 1, ptr, m;
		while (l <= r){
			m = (l + r) / 2;
			if (cv[m].f + os < it.f){
				r = m - 1;
			}
			else {
				l = m + 1;
				ptr = m;
			}
		}

		ans[it.s] = cv[ptr].s;
	}


	for (auto it : al[x]){
		// add offset 
		os += cap[it];
		cv.pb({cap[it] - os, it});
		dfs(it);
	}
	os -= cap[x];
	cv.pop_back();
}

int32_t main(){
	FASTIO
	cin >> n >> q;
	iloop(1, n+1) cin >> dia[i] >> cap[i];
	iloop(0, q){
		int c, v; cin >> c >> v;
		qs[c].pb({v, i});
	}
	
	stack<pll> st;
	iloop(1, n+1){
		while (!st.empty() and st.top().f < dia[i]){
			al[i].pb(st.top().s);
			st.pop();
		}
		st.push({dia[i], i});
	}

	while (!st.empty()){
		al[0].pb(st.top().s);
		st.pop();
	}
	
	/*iloop(0, n+1){
		dg(i);
		for (auto it : al[i]) cout << it << " ";
		cout << endl;
	}*/

	dfs(0);

	iloop(0, q) cout << ans[i] << endl;
}

Compilation message (stderr)

fountain.cpp: In function 'void dfs(long long int)':
fountain.cpp:65:21: warning: 'ptr' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |   ans[it.s] = cv[ptr].s;
      |                     ^

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