Submission #719689

#TimeUsernameProblemLanguageResultExecution timeMemory
719689peijarMeasures (CEOI22_measures)C++17
100 / 100
535 ms33228 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 template <class T> class Fenwick { public: int lim; vector<T> bit; Fenwick(int n) : lim(n + 1), bit(lim) {} void upd(int pos, T val) { for (pos++; pos < lim; pos += pos & -pos) bit[pos] += val; } T sum(int r) { // < r T ret = 0; for (; r; r -= r & -r) ret += bit[r]; return ret; } T sum(int l, int r) { // [l, r) return sum(r) - sum(l); } }; const int MAXN = 2e6; int iDeb[MAXN], iFin[MAXN], lazyAdd[MAXN], maxDiff[MAXN], minVal[MAXN], maxVal[MAXN]; void pull(int node) { maxVal[node] = max(maxVal[2 * node], maxVal[2 * node + 1]); minVal[node] = min(minVal[2 * node], minVal[2 * node + 1]); maxDiff[node] = max({maxDiff[2 * node], maxDiff[2 * node + 1], maxVal[2 * node + 1] - minVal[2 * node]}); } void push(int node) { if (!lazyAdd[node]) return; int x = lazyAdd[node]; lazyAdd[node] = 0; maxVal[node] += x; minVal[node] += x; if (iDeb[node] < iFin[node]) { lazyAdd[2 * node] += x; lazyAdd[2 * node + 1] += x; } } void build(int node, int l, int r) { iDeb[node] = l, iFin[node] = r; maxVal[node] = -1e18; minVal[node] = 1e18; if (l == r) return; build(2 * node, l, (l + r) / 2); build(2 * node + 1, (l + r) / 2 + 1, r); } void active(int node, int pos, int val) { push(node); if (iDeb[node] > pos or iFin[node] < pos) return; if (iDeb[node] == iFin[node]) { minVal[node] = maxVal[node] = val; return; } active(2 * node, pos, val); active(2 * node + 1, pos, val); pull(node); } void rangeAdd(int node, int l, int r, int x) { push(node); if (iDeb[node] > r or iFin[node] < l) { return; } if (iDeb[node] >= l and iFin[node] <= r) { lazyAdd[node] = x; push(node); return; } rangeAdd(2 * node, l, r, x); rangeAdd(2 * node + 1, l, r, x); pull(node); } string affiche(int x) { if (x % 2) return to_string(x / 2) + ".5"; return to_string(x / 2); } signed main(void) { ios_base::sync_with_stdio(false); cin.tie(0); int nbPersonnes, nbRequetes, D; cin >> nbPersonnes >> nbRequetes >> D; vector<pair<int, int>> positions(nbPersonnes + nbRequetes); vector<int> toAdd; for (int i = 0; i < nbPersonnes; ++i) { int x; cin >> x; positions[i] = pair(x, i); toAdd.push_back(x); } for (int i = 0; i < nbRequetes; ++i) { int x; cin >> x; positions[i + nbPersonnes] = pair(x, nbPersonnes + i); toAdd.push_back(x); } sort(positions.begin(), positions.end()); build(1, 0, nbPersonnes + nbRequetes - 1); Fenwick<int> activated(nbPersonnes + nbRequetes); for (int i = 0; i < nbPersonnes + nbRequetes; ++i) { int pos = lower_bound(positions.begin(), positions.end(), pair(toAdd[i], i)) - positions.begin(); assert(positions[pos] == pair(toAdd[i], i)); int bef = activated.sum(pos); activated.upd(pos, 1); active(1, pos, D * bef - toAdd[i]); rangeAdd(1, pos + 1, nbPersonnes + nbRequetes - 1, D); if (i >= nbPersonnes) cout << affiche(maxDiff[1]) << ' '; } 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...