Submission #1102787

#TimeUsernameProblemLanguageResultExecution timeMemory
1102787vladiliusMeasures (CEOI22_measures)C++17
0 / 100
1514 ms8012 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second struct ST{ vector<ll> a; vector<bool> b; int n; ST(int ns){ n = ns; a.resize(n + 1); b.resize(n + 1); } void upd(int p, ll x){ a[p] = x; b[p] = 1; } void add(int l, int r, int x){ for (int i = l; i <= r; i++){ a[i] += x; } } ll get1(int p){ return a[p]; } int get2(int p){ int sum = 0; for (int i = 1; i <= p; i++) sum += b[i]; return sum; } }; struct ST1{ vector<ll> a; int n; ST1(int ns){ n = ns; a.resize(n + 1); } void upd(int p, ll x){ a[p] = x; } void add(int l, int r, ll x){ for (int i = l; i <= r; i++){ a[i] += x; } } ll get(){ ll out = 0; for (int i = 1; i <= n; i++){ out = max(out, a[i]); } return out; } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout<<fixed<<setprecision(15); auto print = [&](ll x){ if (x % 2 == 0){ cout<<x / 2<<" "; } else { cout<<(x - 1) / 2<<".5 "; } }; int n, m, d; cin>>n>>m>>d; vector<int> a(n + 1), b(m + 1); vector<pii> all = {{0, 0}}; for (int i = 1; i <= n; i++){ cin>>a[i]; all.pb({a[i], i}); } for (int i = 1; i <= m; i++){ cin>>b[i]; all.pb({b[i], i + n}); } sort(all.begin(), all.end()); vector<int> p(all.size()); for (int i = 1; i < all.size(); i++) p[all[i].ss] = i; // f[i] = x[i] - d * i // t[i] = x[j] - x[i] + d * (i - j) int N = (int) all.size() - 1; ST T(N); ST1 T1(N); int cc = 0; vector<int> r(N + 1); set<int> st; auto add = [&](int x){ cc++; int i = p[cc]; ll vi = x - 1LL * d * (T.get2(i) + 1); T.upd(i, vi); T.add(i + 1, N, -d); auto it = st.lower_bound(i); if (it != st.begin()){ int j = *prev(it); ll vj = T.get1(j); T1.add(i + 1, N, d); T1.add(max(i, r[j]) + 1, N, -d); if (vj >= vi){ while (true){ auto it1 = st.upper_bound(j); if (it1 == st.end()) break; int k = *it1; if (T.get1(k) <= vj){ r[j] = r[k]; T1.add(k, r[k], all[j].ff - all[k].ff + 1LL * d * (T.get2(k) - T.get2(j))); st.erase(it1); continue; } break; } T1.upd(i, all[j].ff - x + 1LL * d * (T.get2(i) - T.get2(j))); r[j] = max(r[j], i); return; } T1.add(i + 1, r[j], x - all[j].ff); r[i] = r[j]; r[j] = i - 1; } T1.upd(i, 0); r[i] = max(r[i], i); while (true){ it = st.lower_bound(i); if (it == st.end()) break; int k = *it; if (T.get1(k) <= vi){ r[i] = r[k]; T1.add(k, r[k], x - all[k].ff + 1LL * d * (T.get2(k) - T.get2(i))); st.erase(it); continue; } break; } st.insert(i); }; for (int i = 1; i <= n; i++){ add(a[i]); } for (int i = 1; i <= m; i++){ add(b[i]); print(T1.get()); } }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for (int i = 1; i < all.size(); i++) p[all[i].ss] = i;
      |                     ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...