Submission #723320

#TimeUsernameProblemLanguageResultExecution timeMemory
723320someoneMeasures (CEOI22_measures)C++14
0 / 100
131 ms21256 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int M = 1 << 18, N = 2 * M, INF = 1e18 + 42; struct Node { int mini, maxi, lazy, nb; } node[N]; pair<int, int> pii[N]; int n, m, d, a[N], id[N]; void applyOp(int i, int add) { node[i].mini += add; node[i].maxi += add; node[i].lazy += add; } void upd(int i) { node[i].mini = INF; node[i].maxi = -INF; if(node[i*2].nb) { node[i].mini = min(node[i].mini, node[i*2].mini); node[i].maxi = max(node[i].maxi, node[i*2].maxi); } if(node[i*2+1].nb) { node[i].mini = min(node[i].mini, node[i*2+1].mini); node[i].maxi = max(node[i].maxi, node[i*2+1].maxi); } } void addNew(int i, int deb, int fin, int p, int val) { if(fin <= p || p < deb) return; if(fin - deb == 1 && deb == p) { node[i].nb = 1; node[i].lazy = 0; node[i].mini += val; node[i].maxi += val; return; } applyOp(i*2, node[i].lazy); applyOp(i*2+1, node[i].lazy); node[i].lazy = 0; int mid = ((deb + fin) >> 1); addNew(i*2, deb, mid, p, val); addNew(i*2+1, mid, fin, p, val); node[i].nb = node[i*2].nb + node[i*2+1].nb; upd(i); } void update(int i, int deb, int fin, int l, int r, int add) { if(l <= deb && fin <= r) { applyOp(i, add); return; } if(node[i].nb == 0 || fin <= l || r <= deb) return; applyOp(i*2, node[i].lazy); applyOp(i*2+1, node[i].lazy); node[i].lazy = 0; int mid = ((deb + fin) >> 1); update(i*2, deb, mid, l, r, add); update(i*2+1, mid, fin, l, r, add); upd(i); } signed main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> d; for(int i = 0; i < n + m; i++) cin >> a[i]; for(int i = 0; i < n + m; i++) { pii[i].first = a[i]; pii[i].second = i; } sort(pii, pii + n + m); for(int i = 0; i < n + m; i++) id[pii[i].second] = i; for(int i = 0; i < n + m; i++) { addNew(1, 0, M, id[i], a[i]); update(1, 0, M, id[i]+1, M, -d); if(i >= n) { int diff = node[1].maxi - node[1].mini; if(diff & 1) cout << diff / 2 << ".5 "; else cout << diff / 2 << ' '; } } cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...