Submission #105389

#	Time	Username	Problem	Language	Result	Execution time	Memory
105389		reality	Cake 3 (JOI19_cake3)	C++17	100 / 100	1689 ms	206328 KiB

cake3

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 1e6 + 5;
pair < ll , ll > s[N];
ll v[N];
ll ans = -1e18;
struct Nod {
    Nod * l, * r;
    int cnt;
    ll sum;
    Nod(void) {
        l = r = 0;
        cnt = 0;
        sum = 0;
    }
    Nod(int pos) {
        cnt = 1;
        sum = v[pos];
        l = r = 0;
    }
    Nod(Nod *L,Nod *R) {
        l = L;
        r = R;
        cnt = l->cnt + r->cnt;
        sum = l->sum + r->sum;
    }
};
typedef Nod * Node;
Node T[N];
Node build(int l,int r) {
    if (l == r)
        return new Nod();
    int m = (l + r) / 2;
    return new Nod(build(l,m),build(m+1,r));
}
Node update(int l,int r,int pos,Node Root) {
    if (l == r)
        return new Nod(pos);
    int m = (l + r) / 2;
    if (pos <= m)
        return new Nod(update(l,m,pos,Root->l),Root->r);
    else
        return new Nod(Root->l,update(m+1,r,pos,Root->r));
}
ll query(int need,Node Root1,Node Root2) {
    if (Root1->cnt - Root2->cnt == need)
        return Root1->sum - Root2->sum;
    if (Root1->l->cnt - Root2->l->cnt >= need)
        return query(need,Root1->l,Root2->l);
    else
        return query(need - (Root1->l->cnt - Root2->l->cnt),Root1->r,Root2->r) + Root1->l->sum - Root2->l->sum;
}
int m;
void Go(int l1,int r1,int l2,int r2) {
    if (l1 > r1 || l2 > r2)
        return;
    int m1 = (l1 + r1) / 2;
    pair < ll , int > bst = mp((ll)(-1e18),r2);
    for (int i = max(l2,m1 + m - 1);i <= r2;++i)
        smax(bst,mp(query(m,T[i],T[m1 - 1]) + s[m1].se - s[i].se,i));
    smax(ans,bst.fi);
    Go(l1,m1 - 1,l2,bst.se);
    Go(m1 + 1,r1,bst.se,r2);
}
int p[N];
int q[N];

int main(void) {
    int n;
    cin>>n>>m;
    for (int i = 1;i <= n;++i)
        cin>>s[i].fi>>s[i].se,s[i].se *= 2,p[i] = i,v[i] = s[i].fi;
    sort(s + 1,s + 1 + n,[&](auto a,auto b) {
            return a.se < b.se;
        });
    sort(p + 1,p + 1 + n,[&](int x,int y) {
            return s[x].fi > s[y].fi;
        });
    sort(v + 1,v + 1 + n,greater < ll > ());
    for (int i = 1;i <= n;++i)
        q[p[i]] = i;
    T[0] = build(1,n);
    for (int i = 1;i <= n;++i) {
        T[i] = update(1,n,q[i],T[i - 1]);
    }
    Go(1,n,1,n);
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76