제출 #108318

#제출 시각아이디문제언어결과실행 시간메모리
108318Noam527모임들 (IOI18_meetings)C++17
컴파일 에러
0 ms0 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); } inline func progressf(int l, int r, ll st, ll d) { return func(1, d, st - d * l); } // 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); 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]); 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 (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) + (ll)a[v] * (1 - (v - S[v])); func tmp = T.progressf(v + 1, E[v], ll(a[v]) * (v - S[v] + 1), 0); tmp *= T.progressf(v + 1, E[v], -ll(a[v]) * (v - S[v] + 1), -a[v]); T.upd(v + 1, E[v], tmp, 0, 0, T.n - 1); T.minimize(v + 1, E[v], c); T.progress(v + 1, E[v], ll(v - S[v] + 1) * a[v], a[v]); } if (prev != -1 && prev < v) { for (const auto &i : Q[prev]) { if (prev < i.r) ans[i.i] = min(ans[i.i], ll(prev - i.l + 1) * a[prev] + T[i.r]); } } } ll cost(int l, int r, int i) { ll rtn = a[i], mx; mx = a[i]; for (int x = i + 1; x <= r; x++) { mx = max(mx, (ll)a[x]); rtn += mx; } mx = a[i]; for (int x = i - 1; x >= l; x--) { mx = max(mx, (ll)a[x]); rtn += mx; } return rtn; } ll bruteforce(int l, int r) { ll ans = inf; for (int i = l; i <= r; i++) ans = min(ans, cost(l, r, i)); return ans; } 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); 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); solve(root, -1); return ans; } #include <cstdio> #include <cstdlib> #include <vector> namespace { int read_int() { int x; if (scanf("%d", &x) != 1) { fprintf(stderr, "Error while reading input\n"); exit(1); } return x; } } // namespace int main() { int N = read_int(); int Q = read_int(); std::vector<int> H(N); for (int i = 0; i < N; ++i) { H[i] = read_int(); } std::vector<int> L(Q), R(Q); for (int j = 0; j < Q; ++j) { L[j] = read_int(); R[j] = read_int(); } std::vector<long long> C = minimum_costs(H, L, R); for (size_t j = 0; j < C.size(); ++j) { printf("%lld\n", C[j]); } return 0; }

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

meetings.cpp: In member function 'void mtree::init(const std::vector<int>&)':
meetings.cpp:145: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++) {
                  ~~^~~~~~~~~~~~
/tmp/ccLES5Q6.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccs1i4F6.o:meetings.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status