Submission #719664

#TimeUsernameProblemLanguageResultExecution timeMemory
719664peijarMeasures (CEOI22_measures)C++17
0 / 100
216 ms11064 KiB
#include <bits/stdc++.h> #define int long long using namespace std; string to_string(string s) { return s; } template <typename T> string to_string(T v) { bool first = true; string res = "["; for (const auto &x : v) { if (!first) res += ", "; first = false; res += to_string(x); } res += "]"; return res; } void dbg_out() { cout << endl; } template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << to_string(H); dbg_out(T...); } #ifdef DEBUG #define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #else #define dbg(...) #endif struct Intervalle { int deb, fin, maxVal; bool operator<(Intervalle other) const { return deb < other.deb; } }; Intervalle fusion(Intervalle a, Intervalle b) { return Intervalle{a.deb, b.fin + (a.fin - b.deb), max(a.maxVal, b.maxVal + a.fin - b.deb)}; } signed main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int nbInit, nbRequetes, D; cin >> nbInit >> nbRequetes >> D; set<Intervalle> intervalles; int sol = 0; auto ajouteIntervalle = [&](int x) { Intervalle s{x, x + D, 0}; auto it = intervalles.lower_bound(s); if (it != intervalles.begin()) { --it; if (it->fin >= s.deb) { s = fusion(*it, s); intervalles.erase(it); } } while (true) { it = intervalles.lower_bound(s); if (it != intervalles.end() and it->deb <= s.fin) { s = fusion(s, *it); intervalles.erase(it); } else break; } sol = max(sol, s.maxVal); intervalles.insert(s); }; for (int i = 0; i < nbInit; ++i) { int x; cin >> x; ajouteIntervalle(x); } for (int i = 0; i < nbRequetes; ++i) { int x; cin >> x; ajouteIntervalle(x); cout << sol / 2. << ' '; } cout << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...