Submission #1016679

#TimeUsernameProblemLanguageResultExecution timeMemory
1016679LOLOLOMeasures (CEOI22_measures)C++17
100 / 100
286 ms45512 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (ll)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 2e5 + 100; ll st[N * 4][4], n, m, d; int a[N]; void upd(int id, int l, int r, int p, int val) { if (l == r) { st[id][0] = 1; st[id][1] = val - d; st[id][2] = val - d; st[id][3] = 0; return; } int m = (l + r) / 2; if (m >= p) { upd(id * 2, l, m, p, val); } else { upd(id * 2 + 1, m + 1, r, p, val); } st[id][0] = st[id * 2][0] + st[id * 2 + 1][0]; st[id][1] = max(st[id * 2][1], st[id * 2 + 1][1] - st[id * 2][0] * d); st[id][2] = min(st[id * 2][2], st[id * 2 + 1][2] - st[id * 2][0] * d); st[id][3] = max({st[id * 2][1] - st[id * 2 + 1][2] + st[id * 2][0] * d, st[id * 2][3], st[id * 2 + 1][3]}); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> d; vector <pair <int, int>> A; for (int i = 1; i <= n; i++) { cin >> a[i]; A.pb({a[i], i}); } for (int i = n + 1; i <= n + m; i++) { cin >> a[i]; A.pb({a[i], i}); } for (int i = 0; i < N * 4; i++) { st[i][1] = -1e16; st[i][2] = 1e16; } sort(all(A)); map <pair <int, int>, int> mp; int cnt = 1; for (auto x : A) { mp[x] = cnt; cnt++; } for (int i = 1; i <= n + m; i++) { upd(1, 1, n + m, mp[{a[i], i}], a[i]); if (i > n) { ll t = max((ll)0, st[1][3]); if (t % 2 == 0) { cout << t / 2 << " "; } else { cout << t / 2 << ".5 "; } } } return 0; } // dp[l][r][k1][k2] //
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...