Submission #1194638

#TimeUsernameProblemLanguageResultExecution timeMemory
1194638LucaLucaMMeetings (IOI18_meetings)C++20
0 / 100
0 ms324 KiB
#include "meetings.h" #include <iostream> #include <vector> #include <algorithm> #include <cassert> #include <set> #define debug(x) #x << " = " << x << '\n'; using ll = long long; const ll INF = 1e18; struct RMQ { int n; std::vector<int> a; std::vector<std::vector<int>> rmq; int myMax(int x, int y) { if (x >= n) { return y; } if (y >= n) { return x; } return a[x] > a[y]? x : y; } RMQ() {} void build(const std::vector<int> &_a) { a = _a; n = (int) a.size(); int lg2 = std::__lg(n); rmq = std::vector<std::vector<int>>(lg2 + 1, std::vector<int>(n, n)); for (int i = 0; i < n; i++) { rmq[0][i] = i; } for (int j = 1; j <= lg2; j++) { for (int i = 0; i < n; i++) { rmq[j][i] = myMax(rmq[j - 1][i], rmq[j - 1][i + (1 << (j - 1))]); } } } int query(int l, int r) { int k = std::__lg(r - l + 1); return myMax(rmq[k][l], rmq[k][r - (1 << k) + 1]); } }; std::vector<ll> minimum_costs(std::vector<int> a, std::vector<int> L, std::vector<int> R) { int n = (int) a.size(); int q = (int) L.size(); std::vector<ll> answer(q, +INF); std::vector<ll> pref(n); std::vector<std::set<std::pair<int, int>>> lHere(n); std::vector<std::set<std::pair<int, int>>> rHere(n); RMQ rmq; rmq.build(a); auto solve = [&](auto &self, int l, int r) -> void { if (l > r) { return; } std::cout << "? " << l << ' ' << r << '\n'; int p = rmq.query(l, r); self(self, l, p - 1); self(self, p + 1, r); // raspund la query uri if (p - l < r - p) { for (int st = l; st <= p; st++) { // iau mereu l cel mai mare while (!lHere[st].empty() && (*lHere[st].rbegin()).first >= p) { auto [dr, index] = *lHere[st].lower_bound({p, 0}); if (dr <= r) { answer[index] = std::min(answer[index], pref[dr] + (ll) a[p] * (p - st + 1)); lHere[st].erase({dr, index}); rHere[dr].erase({st, index}); } else { break; } } } } else { for (int dr = p; dr <= r; dr++) { while (!rHere[dr].empty() && (*rHere[dr].rbegin()).first >= l) { // vreau l minim auto [st, index] = *rHere[dr].lower_bound({l, 0}); if (st <= p) { answer[index] = std::min(answer[index], pref[dr] + (ll) a[p] * (p - st + 1)); lHere[st].erase({dr, index}); rHere[dr].erase({st, index}); } else { break; } } } } // acum trebuie sa recalculez pref[l..r] // pref[l..p-1] ramane la fel // pref[p] ll c = p == l? 0 : pref[p - 1]; pref[p] = c + a[p]; // pref[p+1..r] for (int i = p + 1; i <= r; i++) { pref[i] += (ll) a[p] * (p - l + 1); } for (int i = p + 1; i <= r; i++) { pref[i] = std::min(pref[i], c + (ll) a[p] * (i - p + 1)); } }; auto addQueries = [&]() { for (int i = 0; i < n; i++) { lHere[i].clear(); rHere[i].clear(); } for (int i = 0; i < q; i++) { lHere[L[i]].insert({R[i], i}); rHere[R[i]].insert({L[i], i}); } }; addQueries(); solve(solve, 0, n - 1); std::reverse(a.begin(), a.end()); rmq.build(a); for (int i = 0; i < q; i++) { L[i] = n - 1 - L[i]; R[i] = n - 1 - R[i]; std::swap(L[i], R[i]); } addQueries(); solve(solve, 0, n - 1); return answer; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...