oj.uz

Submission #912071

# Submission time Handle Problem Language Result Execution time Memory
912071 2024-01-19T07:18:40 Z WH8 Fountain (eJOI20_fountain) C++14
100 / 100
 135 ms 32568 KB 
#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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7004 KB Output is correct
2 Correct 4 ms 7232 KB Output is correct
3 Correct 4 ms 7260 KB Output is correct
4 Correct 5 ms 7260 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct
6 Correct 6 ms 7232 KB Output is correct
7 Correct 4 ms 7260 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 28840 KB Output is correct
2 Correct 112 ms 28072 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7004 KB Output is correct
2 Correct 4 ms 7232 KB Output is correct
3 Correct 4 ms 7260 KB Output is correct
4 Correct 5 ms 7260 KB Output is correct
5 Correct 4 ms 7516 KB Output is correct
6 Correct 6 ms 7232 KB Output is correct
7 Correct 4 ms 7260 KB Output is correct
8 Correct 86 ms 28840 KB Output is correct
9 Correct 112 ms 28072 KB Output is correct
10 Correct 4 ms 7256 KB Output is correct
11 Correct 61 ms 14480 KB Output is correct
12 Correct 135 ms 32568 KB Output is correct
13 Correct 131 ms 20984 KB Output is correct
14 Correct 86 ms 18164 KB Output is correct
15 Correct 87 ms 18432 KB Output is correct