Submission #640103

#TimeUsernameProblemLanguageResultExecution timeMemory
640103BlagojFountain (eJOI20_fountain)C++14
60 / 100
1057 ms524288 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef long double ld; int belong[100001]; int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); int n, q; cin >> n >> q; pair<int, short int> f[n + 1]; vector<pair<int, int>> v[n + 1]; for (int i = 1; i <= n; i++) { cin >> f[i].first >> f[i].second; } int counter = 1; for (int i = 1; i <= n; i++) { if (belong[i]) { continue; } int place = i, liquid = 0; v[counter].push_back({place, 0}); belong[place] = counter; liquid += f[place].second; bool possible = true; while (possible) { possible = false; for (int j = place; j <= n; j++) { if (f[j].first > f[place].first) { belong[j] = counter; possible = true; place = j; v[counter].push_back({j, liquid + 1}); liquid += f[j].second; break; } } } v[counter].push_back({0, liquid + 1}); counter++; } int start, hold; for (int i = 0; i < q; i++) { cin >> start >> hold; int moves = 100, sz = v[belong[start]].size(), minus = 0; int l = 0, r = sz; if (v[belong[start]][0].first != start) { while (l + 1 < r) { int mid = (l + r) / 2; if (v[belong[start]][mid].first == start) { l = mid; break; } if (v[belong[start]][mid].first > start) { r = mid; } if (v[belong[start]][mid].first < start) { l = mid; } } minus = v[belong[start]][l].second - 1; } r = sz; while (moves--) { if (l + r < sz) { if (hold >= v[belong[start]][l + r].second - minus) { l += r; } } r = max(r / 2, 1); } cout << v[belong[start]][l].first << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...