제출 #950268

#제출 시각아이디문제언어결과실행 시간메모리
950268Tuanlinh123Cake 3 (JOI19_cake3)C++17
24 / 100
4035 ms25552 KiB
#include<bits/stdc++.h> #define ll long long #define pll pair<ll, ll> #define pb push_back #define mp make_pair #define fi first #define se second #define ld long double #define sz(a) ((ll)(a).size()) using namespace std; const ll maxn=200005, inf=1e18; ll n, m, v[maxn], c[maxn], p[maxn], lptr=1, rptr=0, ans=-inf; namespace SegTree { struct Node { ll cnt=0, sum=0; Node(){} Node(ll x): cnt(!!x), sum(x){} }; Node St[maxn*4]; void update(ll i, ll Start, ll End, ll idx, ll val) { if (Start>idx || End<idx) return; if (Start==End) {St[i]=Node(val); return;} ll mid=(Start+End)/2; if (mid>=idx) update(i*2, Start, mid, idx, val); else update(i*2+1, mid+1, End, idx, val); St[i].cnt=St[i*2].cnt+St[i*2+1].cnt; St[i].sum=St[i*2].sum+St[i*2+1].sum; } void update(ll idx, ll val){update(1, 1, n, idx, val);} ll query(ll i, ll Start, ll End, ll k) { if (Start==End) { if (!St[i].cnt) return -inf; return St[i].sum; } ll mid=(Start+End)/2; if (St[i*2+1].cnt>=k) return query(i*2+1, mid+1, End, k); return query(i*2, Start, mid, k-St[i*2+1].cnt)+St[i*2+1].sum; } ll query() {return query(1, 1, n, m);} } ll query(ll l, ll r) { while (l<lptr) lptr--, SegTree::update(p[lptr], v[lptr]); while (r>rptr) rptr++, SegTree::update(p[rptr], v[rptr]); while (l>lptr) SegTree::update(p[lptr], 0), lptr++; while (r<rptr) SegTree::update(p[rptr], 0), rptr--; ll res=SegTree::query()-c[r]+c[l]; ans=max(ans, res); return res; } void DnC(ll l, ll r, ll optl, ll optr) { if (l>r) return; ll mid=(l+r)/2, res=0, opt=optl; for (ll i=optl; i<=optr && i<=mid-m+1; i++) tie(res, opt)=max(mp(res, opt), mp(query(i, mid), i)); DnC(l, mid-1, 1, n), DnC(mid+1, r, 1, n); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (ll i=1; i<=n; i++) cin >> v[i] >> c[i], c[i]=c[i]*2; //sort { vector <pll> num; for (ll i=1; i<=n; i++) num.pb({c[i], v[i]}); sort(num.begin(), num.end()); for (ll i=0; i<sz(num); i++) tie(c[i+1], v[i+1])=num[i]; num.clear(); for (ll i=1; i<=n; i++) num.pb({v[i], i}); sort(num.begin(), num.end()); for (ll i=0; i<sz(num); i++) p[num[i].se]=i+1; } DnC(1, n, 1, n), cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...