제출 #579073

#제출 시각아이디문제언어결과실행 시간메모리
579073tranxuanbach휴가 (IOI14_holiday)C++17
53 / 100
752 ms17732 KiB
#ifndef FEXT #include "holiday.h" #endif #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define endl '\n' #define fi first #define se second #define For(i, l, r) for (auto i = (l); i < (r); i++) #define ForE(i, l, r) for (auto i = (l); i <= (r); i++) #define FordE(i, l, r) for (auto i = (l); i >= (r); i--) #define Fora(v, a) for (auto v: (a)) #define bend(a) (a).begin(), (a).end() #define isz(a) ((signed)(a).size()) using ll = long long; using ld = long double; using pii = pair <int, int>; using vi = vector <int>; using vpii = vector <pii>; using vvi = vector <vi>; struct segment_tree{ pair <int, ll> seg[1 << 18]; void build(int id, int l, int r){ if (l == r){ seg[id] = make_pair(0, 0); return; } int mid = (l + r) >> 1; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); seg[id] = make_pair(0, 0); } void update(int id, int l, int r, int i, int val){ if (l == r){ seg[id].fi++; seg[id].se += val; return; } int mid = (l + r) >> 1; if (i <= mid){ update(id * 2, l, mid, i, val); } else{ update(id * 2 + 1, mid + 1, r, i, val); } seg[id] = make_pair(seg[id * 2].fi + seg[id * 2 + 1].fi, seg[id * 2].se + seg[id * 2 + 1].se); } ll sum_max(int id, int l, int r, int x){ if (x >= seg[id].fi){ return seg[id].se; } if (l == r or x <= 0){ return 0; } int mid = (l + r) >> 1; if (seg[id * 2 + 1].fi > x){ return sum_max(id * 2 + 1, mid + 1, r, x); } else{ return sum_max(id * 2, l, mid, x - seg[id * 2 + 1].fi) + seg[id * 2 + 1].se; } } } seg; const int N = 1e5 + 5, M = 3e5 + 5; #define left __left__ #define right __right__ int left[N], right[N]; pair <int, ll> ansleft[M], ansright[M]; int pos[N]; int idxopt = -1; void dnc(int n, int a[], pair <int, ll> ans[], int l, int r, int optl, int optr, queue <tuple <int, int, int, int>> &qu){ int mid = (l + r) >> 1; ans[mid] = make_pair(-1, 0); if (optl < idxopt){ seg.build(1, 0, n - 1); idxopt = 0; seg.update(1, 0, n - 1, pos[idxopt], a[idxopt]); } ForE(opt, optl, optr){ while (idxopt < opt){ idxopt++; seg.update(1, 0, n - 1, pos[idxopt], a[idxopt]); } ll val = seg.sum_max(1, 0, n - 1, mid - opt); if (ans[mid].fi == -1 or ans[mid].se < val){ ans[mid] = make_pair(opt, val); } } if (l < mid){ qu.emplace(l, mid - 1, optl, ans[mid].fi); } if (mid < r){ qu.emplace(mid + 1, r, ans[mid].fi, optr); } } void findMaxAttractionStart1(int n, int a[], pair <int, ll> ans[]){ // cout << "findMaxAttractionStart1 " << n << endl; // For(i, 0, n){ // cout << a[i] << ' '; // } cout << endl; { vpii b; For(i, 0, n){ b.emplace_back(a[i], i); } sort(bend(b)); For(i, 0, n){ pos[b[i].se] = i; } } queue <tuple <int, int, int, int>> qu; qu.emplace(0, 2 * n, 0, n - 1); while (!qu.empty()){ int l, r, optl, optr; tie(l, r, optl, optr) = qu.front(); qu.pop(); dnc(n, a, ans, l, r, optl, optr, qu); } For(i, 2 * n + 1, M){ ans[i] = ans[i - 1]; } // For(i, 0, 10){ // cout << i << ' ' << ans[i].fi << ' ' << ans[i].se << endl; // } } ll findMaxAttraction(int n, int start, int d, int a[]){ ll ans = 0; FordE(i, start, 0){ left[start - i] = a[i]; } findMaxAttractionStart1(start + 1, left, ansleft); ForE(dl, 0, d){ ans = max(ans, ansleft[dl].se); } if (start < n - 1){ For(i, start + 1, n){ right[i - start - 1] = a[i]; } findMaxAttractionStart1(n - start - 1, right, ansright); ForE(dl, 0, d){ int dr = d - dl - ansleft[dl].fi - 1; if (!(0 <= dr and dr <= d)){ continue; } // cout << "dl dr left " << dl << ' ' << dr << endl; // cout << ansleft[dl].fi << ' ' << ansleft[dl].se << ' ' << ansright[dr].fi << ' ' << ansright[dr].se << endl; ans = max(ans, ansleft[dl].se + ansright[dr].se); } } For(i, start, n){ right[i - start] = a[i]; } findMaxAttractionStart1(n - start, right, ansright); ForE(dr, 0, d){ ans = max(ans, ansright[dr].se); } if (start > 0){ FordE(i, start - 1, 0){ left[start - 1 - i] = a[i]; } findMaxAttractionStart1(start, left, ansleft); ForE(dr, 0, d){ int dl = d - dr - ansright[dr].fi - 1; if (!(0 <= dl and dl <= d)){ continue; } // cout << "dl dr right " << dl << ' ' << dr << endl; // cout << ansleft[dl].fi << ' ' << ansleft[dl].se << ' ' << ansright[dr].fi << ' ' << ansright[dr].se << endl; ans = max(ans, ansleft[dl].se + ansright[dr].se); } } return ans; } #ifdef FEXT int a[100005]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); freopen("KEK.inp", "r", stdin); freopen("KEK.out", "w", stdout); int n, start, d; cin >> n >> start >> d; For(i, 0, n){ cin >> a[i]; } ll ans = findMaxAttraction(n, start, d, a); cout << ans << endl; } #endif /* ==================================================+ INPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ OUTPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...