제출 #108291

#제출 시각아이디문제언어결과실행 시간메모리
108291Noam527모임들 (IOI18_meetings)C++17
41 / 100
712 ms48916 KiB
#include <bits/stdc++.h> #define CHECK cout << "ok" << endl #define finish(x) return cout << x << endl, 0 typedef long long ll; typedef long double ldb; const int md = 1e9 + 7; const ll inf = 1e18; const int OO = 0; const int OOO = 1; using namespace std; struct func { int a; ll b, c; func() { a = 1, b = c = 0; } func(int aa, ll bb, ll cc) : a(aa), b(bb), c(cc) {} // this * x func operator * (const func &x) const { return func(a * x.a, a * x.b + b, a * x.c + c); } // x * this void operator *= (const func &x) { a = x.a * a; b = x.a * b + x.b; c = x.a * c + x.c; } ll operator () (ll x, int i) const { return a * x + b * i + c; } }; struct segtree { int n; vector<ll> t; vector<int> ind; vector<func> tag; segtree() {} segtree(int sz) { init(sz); } void init(int sz) { n = max(2, sz); while (n != (n & -n)) n += (n & -n); t.resize(2 * n, 0); tag.resize(2 * n, func()); ind.resize(2 * n); for (int i = 0; i < n; i++) ind[i + n - 1] = i; for (int i = n - 2; i >= 0; i--) ind[i] = ind[2 * i + 1]; } void clear() { for (auto &i : t) i = 0; for (auto &i : tag) i = func(); } void push(int x) { t[x] = tag[x](t[x], ind[x]); if (x < n - 1) { tag[2 * x + 1] *= tag[x]; tag[2 * x + 2] *= tag[x]; } tag[x] = func(); } // assumes x has no tag void fix(int x) { push(2 * x + 1); t[x] = t[2 * x + 1]; } // a[i] = x void set(ll x, int i) { func f(0, 0, x); upd(i, i, f, 0, 0, n - 1); } // for each i in [l, r], add st + d * (i - l) void progress(int l, int r, ll st, ll d) { func f(1, d, st - d * l); upd(l, r, f, 0, 0, n - 1); } // for each i in monotonic [l, r], set a[i] = min(a[i], x) void minimize(int l, int r, ll x) { int m = last(l, r, x); if (m != -1) { func f(0, 0, x); upd(l, m, f, 0, 0, n - 1); } } void upd(int l, int r, const func &f, int node, int nl, int nr) { if (r < nl || nr < l) return; if (l <= nl && nr <= r) { tag[node] *= f; return; } push(node); int mid = (nl + nr) / 2; upd(l, r, f, 2 * node + 1, nl, mid); upd(l, r, f, 2 * node + 2, mid + 1, nr); fix(node); } // smallest i in [l, r] s.t a[i] >= x int last(int l, int r, ll x) { return last(l, r, x, 0, 0, n - 1); } int last(int l, int r, ll x, int node, int nl, int nr) { if (r < nl || nr < l) return -1; push(node); if (l <= nl && nr <= r && t[node] < x) return -1; if (nl == nr) return nl; int mid = (nl + nr) / 2, tmp; tmp = last(l, r, x, 2 * node + 2, mid + 1, nr); if (tmp != -1) return tmp; return last(l, r, x, 2 * node + 1, nl, mid); } ll operator [] (int i) const { int org = i; i += n - 1; ll rtn = t[i]; rtn = tag[i](rtn, org); i = (i - 1) / 2; while (i) { rtn = tag[i](rtn, org); i = (i - 1) / 2; } rtn = tag[0](rtn, org); return rtn; } }; struct mtree { int n; const ll b = 1 << 30; vector<ll> t; mtree() {} mtree(const vector<int> &a) { init(a); } void init(const vector<int> &a) { n = max(2, (int)a.size()); while (n != (n & -n)) n += (n & -n); t.resize(2 * n); for (int i = 0; i < a.size(); i++) t[i + n - 1] = b * a[i] + i; for (int i = n - 2; i >= 0; i--) t[i] = max(t[2 * i + 1], t[2 * i + 2]); } int query(int l, int r) const { ll mx = -1; for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) { if (!(l & 1)) mx = max(mx, t[l++]); if (r & 1) mx = max(mx, t[r--]); } if (l == r) mx = max(mx, t[l]); return mx % b; } ll vquery(int l, int r) const { ll mx = -1; for (l += n - 1, r += n - 1; l < r; l = (l - 1) / 2, r = (r - 1) / 2) { if (!(l & 1)) mx = max(mx, t[l++]); if (r & 1) mx = max(mx, t[r--]); } if (l == r) mx = max(mx, t[l]); return mx / b; } }; struct query { int l, r, i; query() {} query(int ll, int rr, int ii) : l(ll), r(rr), i(ii) {} }; const int mxn = 750005; int n; vector<int> a; int S[mxn], E[mxn], L[mxn], R[mxn], root; vector<query> Q[mxn]; vector<ll> ans; mtree M; segtree T; int preprocess(int l, int r) { if (l > r) return -1; int v = M.query(l, r); if (OO) { cout << "preprocessing in [" << l << ", " << r << "], v = " << v << '\n'; } S[v] = l; E[v] = r; L[v] = preprocess(l, v - 1); R[v] = preprocess(v + 1, r); return v; } void preprocess(const vector<int> &l, const vector<int> &r) { M.init(a); T.init(n); root = preprocess(0, n - 1); for (int i = 0; i < ans.size(); i++) { ans[i] = ll(r[i] - l[i] + 1) * M.vquery(l[i], r[i]); int v = M.query(l[i], r[i]); if (OO) { cout << "attaching query " << l[i] << " " << r[i] << " to " << v << '\n'; } Q[v].push_back(query(l[i], r[i], i)); } } void solve(int v, int prev) { if (v < 0 || n <= v) return; solve(L[v], v); solve(R[v], v); if (OO) cout << "solving " << v << " " << prev << '\n'; if (OO) { cout << "before:\n"; for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n'; } if (S[v] == v) T.set(a[v], v); else T.set(T[v - 1] + a[v], v); if (v < E[v]) { ll c = (v > 0 ? T[v - 1] : 0) + a[v] * (1 - (v - S[v])); T.progress(v + 1, E[v], ll(a[v]) * (v - S[v] + 1), 0); T.progress(v + 1, E[v], -ll(a[v]) * (v - S[v] + 1), -a[v]); T.minimize(v + 1, E[v], c); T.progress(v + 1, E[v], ll(v - S[v] + 1) * a[v], a[v]); } if (OO) { cout << "after:\n"; for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n'; } if (prev != -1 && prev < v) { for (const auto &i : Q[prev]) { if (prev < i.r) { if (OO) cout << "updating query " << i.l << " " << i.r << '\n'; ans[i.i] = min(ans[i.i], ll(prev - i.l + 1) * a[prev] + T[i.r]); } } } } vector<ll> minimum_costs(vector<int> H, vector<int> l, vector<int> r) { n = H.size(); a = H; ans.resize(l.size()); preprocess(l, r); if (OO) { cout << "preprocessed\n"; cout << "L: "; for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n'; cout << "R: "; for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n'; cout << "S: "; for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n'; cout << "E: "; for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n'; } solve(root, -1); // reverse reverse(a.begin(), a.end()); auto flip = [](int &x, int y) { x = y - 1 - x; }; for (int i = 0; i < n; i++) { flip(S[i], n); flip(E[i], n); swap(S[i], E[i]); flip(L[i], n); flip(R[i], n); swap(L[i], R[i]); } for (int i = 0; i < n; i++) { for (auto &j : Q[i]) { flip(j.l, n); flip(j.r, n); swap(j.l, j.r); } } reverse(Q, Q + n); reverse(S, S + n); reverse(E, E + n); reverse(L, L + n); reverse(R, R + n); M.init(a); T.clear(); flip(root, n); if (OO) { cout << "reversed\n"; cout << "L: "; for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n'; cout << "R: "; for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n'; cout << "S: "; for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n'; cout << "E: "; for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n'; cout << '\n'; cout << "current answers: "; for (const auto &i : ans) cout << i << " "; cout << '\n'; } solve(root, -1); return ans; }

컴파일 시 표준 에러 (stderr) 메시지

meetings.cpp: In member function 'void mtree::init(const std::vector<int>&)':
meetings.cpp:142:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < a.size(); i++)
                   ~~^~~~~~~~~~
meetings.cpp: In function 'void preprocess(const std::vector<int>&, const std::vector<int>&)':
meetings.cpp:201:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++) {
                  ~~^~~~~~~~~~~~
meetings.cpp: In function 'void solve(int, int)':
meetings.cpp:218:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
   ^~~
meetings.cpp:218:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:232:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
   ^~~
meetings.cpp:232:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << T[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:255:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
   ^~~
meetings.cpp:255:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:257:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
   ^~~
meetings.cpp:257:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:259:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
   ^~~
meetings.cpp:259:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:261:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
   ^~~
meetings.cpp:261:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:295:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
   ^~~
meetings.cpp:295:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << L[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:297:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
   ^~~
meetings.cpp:297:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << R[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:299:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
   ^~~
meetings.cpp:299:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << S[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:301:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
   ^~~
meetings.cpp:301:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (int i = 0; i < n; i++) cout << E[i] << " "; cout << '\n';
                                                    ^~~~
meetings.cpp:304:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   for (const auto &i : ans) cout << i << " "; cout << '\n';
   ^~~
meetings.cpp:304:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   for (const auto &i : ans) cout << i << " "; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...