#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a;i < b;i++)
#define pii pair<int,int>
#define all(v) begin(v), end(v)
#define vi vector<int>
const int N = 100'005;
const int LN = 20;
struct PersistentSegTree
{ // Returns the sum of K largest elements in [l, r)
map<int,pii> cp;
// add log2(Q) is storage needed after some update query
int L[LN*N],R[LN*N],S[LN*N]; long long KS[LN*N];
int SZ = 1, roots[N], MX;
PersistentSegTree(int v[], int n) : MX(n) {
int tl = 0, tr = n, idx[n];pii sort_v[n];
rep(i, 0, n) sort_v[i] = {v[i], i};
sort(all(sort_v), greater<pii>());
rep(i,0,n)cp[i]=sort_v[i],idx[sort_v[i].second]=i;
roots[0] = build(tl, tr);
rep(i,0,n)roots[i+1]=update(roots[i],tl,tr,idx[i]);
}
int ver(int s, int ks, int l, int r) {
S[SZ]=s;KS[SZ]=ks;L[SZ]=l;R[SZ]=r;return SZ++;
}
int ver(int l, int r) {
S[SZ]=S[l]+S[r];KS[SZ]=KS[l]+KS[r];
L[SZ]=l;R[SZ]=r;return SZ++;
}
int build(int tl, int tr){
if (tl == tr) return ver(0, 0, -1, -1);
int tm = (tl+tr)/2;
return ver(build(tl, tm),build(tm + 1, tr));
}
int update(int idx, int tl, int tr, int pos){
if (tl == tr)
return ver(S[idx]+1,KS[idx]+cp[pos].first,-1,-1);
int tm = (tl + tr) / 2;
if (pos <= tm)
return ver(update(L[idx],tl,tm,pos),R[idx]);
return ver(L[idx],update(R[idx],tm+1,tr,pos));
}
long long kth(int vl, int vr, int tl, int tr, int k) {
if (tl == tr) return KS[vr]-KS[vl];
int tm = (tl+tr)/2,lc=S[L[vr]]-S[L[vl]];
if (lc >= k)return kth(L[vl], L[vr], tl, tm, k);
return KS[L[vr]]-KS[L[vl]]+kth(R[vl],
R[vr],tm+1,tr,k-lc);
}
long long kth(int l, int r, int k) {
return kth(roots[l], roots[r], 0, MX, k);
}
};
long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
long long int ans = 0;
PersistentSegTree pst(attraction, n);
function<long long(int, int)> C1 = [&](int k, int mid) -> long long
{
int days_rem = d - (mid - k + start - k);
if (days_rem <= 0)
return 0;
return pst.kth(k, mid + 1, days_rem);
// return mid - k;
};
function<long long(int, int)> C2 = [&](int mid, int k) -> long long
{
int days_rem = d - (k - mid + k - start);
if (days_rem <= 0)
return 0;
return pst.kth(mid, k + 1, days_rem);
// return k - mid;
};
// function<void(int, int, int, int)> dncg = [&](int l, int r, int optl, int optr)
// {
// if (l > r)
// return;
// int mid = (l + r) >> 1;
// pair<long long, int> best = {-1, -1};
// for (int k = optl; k <= min(mid, optr); k++)
// best = max(best, {C1(k, mid), k});
// // debug(dp, best, ndp);
// // debug(ans, best, mid);
// ans = max(best.first, ans);
// int opt = best.second;
// dncg(l, mid - 1, optl, opt);
// dncg(mid + 1, r, opt, optr);
// };
// function<void(int, int, int, int)> dncs = [&](int l, int r, int optl, int optr)
// {
// if (l > r)
// return;
// int mid = (l + r) >> 1;
// pair<long long, int> best = {-1, -1};
// for (int k = optr; k >= max(mid, optl); k--)
// best = max(best, {C2(mid, k), k});
// // debug(dp, best, ndp);
// // debug(ans, best, mid);
// ans = max(best.first, ans);
// int opt = best.second;
// dncs(l, mid - 1, optl, opt);
// dncs(mid + 1, r, opt, optr);
// };
if (d == 0)
return 0;
ans = attraction[start];
vector<array<int, 4>> dncg, dncs;
dncg.push_back({start + 1, n - 1, 0, start});
dncs.push_back({0, start - 1, start, n - 1});
while (!dncg.empty())
{
auto [l, r, optl, optr] = dncg.back();
dncg.pop_back();
if (l > r)
continue;
int mid = (l + r) >> 1;
pair<long long, int> best = {-1, -1};
for (int k = optl; k <= min(mid, optr); k++)
best = max(best, {C1(k, mid), k});
// debug(dp, best, ndp);
// debug(ans, best, mid);
ans = max(best.first, ans);
int opt = best.second;
dncg.push_back({mid + 1, r, opt, optr});
dncg.push_back({l, mid - 1, optl, opt});
}
while (!dncs.empty())
{
auto [l, r, optl, optr] = dncs.back();
dncs.pop_back();
if (l > r)
continue;
int mid = (l + r) >> 1;
pair<long long, int> best = {-1, -1};
for (int k = optr; k >= max(mid, optl); k--)
best = max(best, {C2(mid, k), k});
// debug(dp, best, ndp);
// debug(ans, best, mid);
ans = max(best.first, ans);
int opt = best.second;
dncs.push_back({mid + 1, r, opt, optr});
dncs.push_back({l, mid - 1, optl, opt});
}
// dncg(start + 1, n - 1, 0, start);
// dncs(0, start - 1, start, n - 1);
return ans;
}
컴파일 시 표준 에러 (stderr) 메시지
holiday.cpp: In constructor 'PersistentSegTree::PersistentSegTree(int*, int)':
holiday.cpp:7:21: error: no matching function for call to 'begin(std::pair<int, int> [n])'
7 | #define all(v) begin(v), end(v)
| ~~~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~
In file included from /usr/include/c++/11/bits/range_access.h:36,
from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from holiday.cpp:2:
/usr/include/c++/11/initializer_list:90:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::begin(std::initializer_list<_Tp>)'
90 | begin(initializer_list<_Tp> __ils) noexcept
| ^~~~~
/usr/include/c++/11/initializer_list:90:5: note: template argument deduction/substitution failed:
holiday.cpp:7:21: note: mismatched types 'std::initializer_list<_Tp>' and 'std::pair<int, int>*'
7 | #define all(v) begin(v), end(v)
| ~~~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from holiday.cpp:2:
/usr/include/c++/11/bits/range_access.h:51:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(_Container&)'
51 | begin(_Container& __cont) -> decltype(__cont.begin())
| ^~~~~
/usr/include/c++/11/bits/range_access.h:51:5: note: template argument deduction/substitution failed:
holiday.cpp:7:21: note: variable-sized array type 'std::pair<int, int> [n]' is not a valid template argument
7 | #define all(v) begin(v), end(v)
| ~~~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from holiday.cpp:2:
/usr/include/c++/11/bits/range_access.h:61:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.begin()) std::begin(const _Container&)'
61 | begin(const _Container& __cont) -> decltype(__cont.begin())
| ^~~~~
/usr/include/c++/11/bits/range_access.h:61:5: note: template argument deduction/substitution failed:
holiday.cpp:7:21: note: variable-sized array type 'std::pair<int, int> [n]' is not a valid template argument
7 | #define all(v) begin(v), end(v)
| ~~~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from holiday.cpp:2:
/usr/include/c++/11/bits/range_access.h:90:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::begin(_Tp (&)[_Nm])'
90 | begin(_Tp (&__arr)[_Nm]) noexcept
| ^~~~~
/usr/include/c++/11/bits/range_access.h:90:5: note: template argument deduction/substitution failed:
holiday.cpp:7:21: note: variable-sized array type 'long int' is not a valid template argument
7 | #define all(v) begin(v), end(v)
| ~~~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
from holiday.cpp:2:
/usr/include/c++/11/valarray:1217:5: note: candidate: 'template<class _Tp> _Tp* std::begin(std::valarray<_Tp>&)'
1217 | begin(valarray<_Tp>& __va) noexcept
| ^~~~~
/usr/include/c++/11/valarray:1217:5: note: template argument deduction/substitution failed:
holiday.cpp:7:21: note: mismatched types 'std::valarray<_Tp>' and 'std::pair<int, int> [n]'
7 | #define all(v) begin(v), end(v)
| ~~~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
from holiday.cpp:2:
/usr/include/c++/11/valarray:1228:5: note: candidate: 'template<class _Tp> const _Tp* std::begin(const std::valarray<_Tp>&)'
1228 | begin(const valarray<_Tp>& __va) noexcept
| ^~~~~
/usr/include/c++/11/valarray:1228:5: note: template argument deduction/substitution failed:
holiday.cpp:7:21: note: mismatched types 'const std::valarray<_Tp>' and 'std::pair<int, int> [n]'
7 | #define all(v) begin(v), end(v)
| ~~~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~
holiday.cpp:7:29: error: no matching function for call to 'end(std::pair<int, int> [n])'
7 | #define all(v) begin(v), end(v)
| ~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~
In file included from /usr/include/c++/11/bits/range_access.h:36,
from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from holiday.cpp:2:
/usr/include/c++/11/initializer_list:101:5: note: candidate: 'template<class _Tp> constexpr const _Tp* std::end(std::initializer_list<_Tp>)'
101 | end(initializer_list<_Tp> __ils) noexcept
| ^~~
/usr/include/c++/11/initializer_list:101:5: note: template argument deduction/substitution failed:
holiday.cpp:7:29: note: mismatched types 'std::initializer_list<_Tp>' and 'std::pair<int, int>*'
7 | #define all(v) begin(v), end(v)
| ~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from holiday.cpp:2:
/usr/include/c++/11/bits/range_access.h:71:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(_Container&)'
71 | end(_Container& __cont) -> decltype(__cont.end())
| ^~~
/usr/include/c++/11/bits/range_access.h:71:5: note: template argument deduction/substitution failed:
holiday.cpp:7:29: note: variable-sized array type 'std::pair<int, int> [n]' is not a valid template argument
7 | #define all(v) begin(v), end(v)
| ~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from holiday.cpp:2:
/usr/include/c++/11/bits/range_access.h:81:5: note: candidate: 'template<class _Container> constexpr decltype (__cont.end()) std::end(const _Container&)'
81 | end(const _Container& __cont) -> decltype(__cont.end())
| ^~~
/usr/include/c++/11/bits/range_access.h:81:5: note: template argument deduction/substitution failed:
holiday.cpp:7:29: note: variable-sized array type 'std::pair<int, int> [n]' is not a valid template argument
7 | #define all(v) begin(v), end(v)
| ~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~
In file included from /usr/include/c++/11/string:54,
from /usr/include/c++/11/bits/locale_classes.h:40,
from /usr/include/c++/11/bits/ios_base.h:41,
from /usr/include/c++/11/ios:42,
from /usr/include/c++/11/istream:38,
from /usr/include/c++/11/sstream:38,
from /usr/include/c++/11/complex:45,
from /usr/include/c++/11/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
from holiday.cpp:2:
/usr/include/c++/11/bits/range_access.h:100:5: note: candidate: 'template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::end(_Tp (&)[_Nm])'
100 | end(_Tp (&__arr)[_Nm]) noexcept
| ^~~
/usr/include/c++/11/bits/range_access.h:100:5: note: template argument deduction/substitution failed:
holiday.cpp:7:29: note: variable-sized array type 'long int' is not a valid template argument
7 | #define all(v) begin(v), end(v)
| ~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
from holiday.cpp:2:
/usr/include/c++/11/valarray:1239:5: note: candidate: 'template<class _Tp> _Tp* std::end(std::valarray<_Tp>&)'
1239 | end(valarray<_Tp>& __va) noexcept
| ^~~
/usr/include/c++/11/valarray:1239:5: note: template argument deduction/substitution failed:
holiday.cpp:7:29: note: mismatched types 'std::valarray<_Tp>' and 'std::pair<int, int> [n]'
7 | #define all(v) begin(v), end(v)
| ~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:95,
from holiday.cpp:2:
/usr/include/c++/11/valarray:1255:5: note: candidate: 'template<class _Tp> const _Tp* std::end(const std::valarray<_Tp>&)'
1255 | end(const valarray<_Tp>& __va) noexcept
| ^~~
/usr/include/c++/11/valarray:1255:5: note: template argument deduction/substitution failed:
holiday.cpp:7:29: note: mismatched types 'const std::valarray<_Tp>' and 'std::pair<int, int> [n]'
7 | #define all(v) begin(v), end(v)
| ~~~^~~
holiday.cpp:22:14: note: in expansion of macro 'all'
22 | sort(all(sort_v), greater<pii>());
| ^~~