제출 #473098

#제출 시각아이디문제언어결과실행 시간메모리
473098jwvg0425휴가 (IOI14_holiday)C++17
0 / 100
54 ms65540 KiB
#include <stdio.h> #include <vector> #include <queue> #include <algorithm> #include <iostream> #include <string> #include <bitset> #include <map> #include <set> #include <tuple> #include <string.h> #include <math.h> #include <random> #include <functional> #include <assert.h> #include <math.h> #define all(x) (x).begin(), (x).end() #define xx first #define yy second using namespace std; using i64 = long long int; using ii = pair<int, int>; using ii64 = pair<i64, i64>; template<typename T> class PST { struct Node { int lidx, ridx; T value; Node() :value(T()), lidx(-1), ridx(-1) {} }; public: class iterator { public: iterator(PST<T>& p, int n) : pst(p), node(n) {} iterator& operator=(const iterator& other) { assert(&pst == &other.pst); node = other.node; return *this; } T get() const { return pst.node[node].value; } iterator left() const { return iterator(pst, pst.node[node].lidx); } iterator right() const { return iterator(pst, pst.node[node].ridx); } private: PST<T>& pst; int node; }; template<typename M> PST(int n_, const M& m) : n(n_), merge(m) { node.resize(2000000); } iterator it(int r) { return iterator(*this, root[r]); } int rmost() const { return n; } int update(int idx, const T& value) { return update((int)root.size() - 1, idx, value); } int update(int pre, int idx, const T& value) { root.emplace_back(_update(root[pre], idx, value, 0, n)); return (int)root.size() - 1; } T query(int k, int start, int end) { return _query(root[k], start, end, 0, n); } void init() { root.push_back(init(0, n)); } private: int init(int start, int end) { int idx = node.size(); node.emplace_back(); sz++; if (start != end) { int mid = (start + end) / 2; node[idx].lidx = init(start, mid); node[idx].ridx = init(mid + 1, end); } return idx; } int _update(int prev, int idx, const T& value, int start, int end) { if (idx < start || idx > end) return prev; int nidx = sz; node.emplace_back(); sz++; if (start == end) node[nidx].value = value; else { int mid = (start + end) / 2; node[nidx].lidx = _update(node[prev].lidx, idx, value, start, mid); node[nidx].ridx = _update(node[prev].ridx, idx, value, mid + 1, end); node[nidx].value = merge(node[node[nidx].lidx].value, node[node[nidx].ridx].value); } return nidx; } T _query(int idx, int start, int end, int left, int right) { if (start <= left && right <= end) return node[idx].value; int mid = (left + right) / 2; if (mid + 1 > end) return _query(node[idx].lidx, start, end, left, mid); if (mid < start) return _query(node[idx].ridx, start, end, mid + 1, right); return merge(_query(node[idx].lidx, start, end, left, mid), _query(node[idx].ridx, start, end, mid + 1, right)); } using Merge = function<T(const T&, const T&)>; Merge merge; vector<int> root; vector<Node> node; int n; int sz = 0; }; using Pt = pair<i64, int>; int n, s, d; auto tree = PST<Pt>(100005, [](const Pt& l, const Pt& r) { return Pt(l.xx + r.xx, l.yy + r.yy); }); vector<i64> arr; i64 get(int l, int r) { int cnt = min(r - l + 1, d + 2 * l - r - s); if (cnt <= 0) return 0; i64 res = 0; auto lx = tree.it(l - 1); auto rx = tree.it(r); int s = 0, e = 100005; int need = cnt; while (need > 0) { if (s == e) { res += rx.get().xx - lx.get().xx; break; } int m = (s + e) / 2; auto lr = lx.right(); auto rr = rx.right(); if (rr.get().yy - lr.get().yy >= need) { lx = lr; rx = rr; s = m + 1; continue; } need -= rr.get().yy - lr.get().yy; res += rr.get().xx - lr.get().xx; lx = lx.left(); rx = rx.left(); e = m; } return res; } i64 big[100005]; void f(int y1, int y2, int x1, int x2) { if (y1 > y2 || x1 > x2) return; i64 ans = -(1ll << 60); i64 ansp = x1; int y = (y1 + y2) / 2; for (int i = x1; i <= x2; i++) { i64 v = get(y, i); if (v > ans) { ans = v; ansp = i; } } big[y] = ans; f(y1, y - 1, x1, ansp); f(y + 1, y2, ansp, x2); } i64 solve() { for (int i = 0; i < n; i++) big[i] = -(1ll << 60); vector<ii64> byVal; for (int i = 0; i < n; i++) byVal.emplace_back(arr[i], i); sort(all(byVal)); vector<int> order(n); for (int i = 0; i < n; i++) order[byVal[i].yy] = i + 1; tree = PST<Pt>(100005, [](const Pt& l, const Pt& r) { return Pt(l.xx + r.xx, l.yy + r.yy); }); tree.init(); for (int i = 0; i < n; i++) tree.update(order[i], Pt(arr[i], 1)); f(1, s, 1, n); i64 ans = big[1]; for (int i = 1; i <= n; i++) ans = max(ans, big[i]); return ans; } long long int findMaxAttraction(int n_, int s_, int d_, int attraction[]) { n = n_; s = s_ + 1; d = d_; arr.resize(n); for (int i = 0; i < n; i++) arr[i] = attraction[i]; i64 ans = solve(); reverse(all(arr)); s = n + 1 - s; i64 ans2 = solve(); return max(ans, ans2); }

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

holiday.cpp: In instantiation of 'PST<T>::PST(int, const M&) [with M = <lambda(const Pt&, const Pt&)>; T = std::pair<long long int, int>]':
holiday.cpp:175:98:   required from here
holiday.cpp:169:6: warning: 'PST<std::pair<long long int, int> >::n' will be initialized after [-Wreorder]
  169 |  int n;
      |      ^
holiday.cpp:166:8: warning:   'PST<std::pair<long long int, int> >::Merge PST<std::pair<long long int, int> >::merge' [-Wreorder]
  166 |  Merge merge;
      |        ^~~~~
holiday.cpp:73:2: warning:   when initialized here [-Wreorder]
   73 |  PST(int n_, const M& m) : n(n_), merge(m)
      |  ^~~
holiday.cpp: In instantiation of 'PST<T>::PST(int, const M&) [with M = solve()::<lambda(const Pt&, const Pt&)>; T = std::pair<long long int, int>]':
holiday.cpp:265:94:   required from here
holiday.cpp:169:6: warning: 'PST<std::pair<long long int, int> >::n' will be initialized after [-Wreorder]
  169 |  int n;
      |      ^
holiday.cpp:166:8: warning:   'PST<std::pair<long long int, int> >::Merge PST<std::pair<long long int, int> >::merge' [-Wreorder]
  166 |  Merge merge;
      |        ^~~~~
holiday.cpp:73:2: warning:   when initialized here [-Wreorder]
   73 |  PST(int n_, const M& m) : n(n_), merge(m)
      |  ^~~
holiday.cpp: In instantiation of 'PST<T>::Node::Node() [with T = std::pair<long long int, int>]':
/usr/include/c++/10/ext/new_allocator.h:150:4:   required from 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = PST<std::pair<long long int, int> >::Node; _Args = {}; _Tp = PST<std::pair<long long int, int> >::Node]'
/usr/include/c++/10/bits/alloc_traits.h:512:17:   required from 'static void std::allocator_traits<std::allocator<_Tp1> >::construct(std::allocator_traits<std::allocator<_Tp1> >::allocator_type&, _Up*, _Args&& ...) [with _Up = PST<std::pair<long long int, int> >::Node; _Args = {}; _Tp = PST<std::pair<long long int, int> >::Node; std::allocator_traits<std::allocator<_Tp1> >::allocator_type = std::allocator<PST<std::pair<long long int, int> >::Node>]'
/usr/include/c++/10/bits/vector.tcc:115:30:   required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {}; _Tp = PST<std::pair<long long int, int> >::Node; _Alloc = std::allocator<PST<std::pair<long long int, int> >::Node>; std::vector<_Tp, _Alloc>::reference = PST<std::pair<long long int, int> >::Node&]'
holiday.cpp:113:20:   required from 'int PST<T>::init(int, int) [with T = std::pair<long long int, int>]'
holiday.cpp:106:22:   required from 'void PST<T>::init() [with T = std::pair<long long int, int>]'
holiday.cpp:266:12:   required from here
holiday.cpp:33:5: warning: 'PST<std::pair<long long int, int> >::Node::value' will be initialized after [-Wreorder]
   33 |   T value;
      |     ^~~~~
holiday.cpp:32:7: warning:   'int PST<std::pair<long long int, int> >::Node::lidx' [-Wreorder]
   32 |   int lidx, ridx;
      |       ^~~~
holiday.cpp:35:3: warning:   when initialized here [-Wreorder]
   35 |   Node() :value(T()), lidx(-1), ridx(-1) {}
      |   ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...