Submission #208138

#	Time	Username	Problem	Language	Result	Execution time	Memory
208138		achibasadzishvili	Cake 3 (JOI19_cake3)	C++17	24 / 100	538 ms	262148 KiB

cake3

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
multiset<ll>st;
pair<ll,ll>a[200005];
ll n,m,ans=-9999999999999999,mid,ra,kk,pp,raod,sum1,sum2,ff;
bool lst[1000005];
struct node {
    vector<int>v,b;
    vector<ll>s1,s2;
    int num;
    node *l,*r;
    node() : num(0) , l(NULL) , r(NULL) {}
};
 
node *root = NULL;
 
void build(node *&x,int L,int R){
    if((int)(x -> v).size() == 1){
        lst[x -> num] = 1;
        return;
    }
    mid = (L + R) / 2;
    x -> l = new node();
    ra++;
    x -> l -> num = ra;
    x -> r = new node();
    ra++;
    x -> r -> num = ra;
    (*(x -> l)).v.pb(0);(*(x -> r)).v.pb(0);
    (*(x -> l)).b.pb(0);(*(x -> r)).b.pb(0);
    (*(x -> l)).s1.pb(0);(*(x -> r)).s1.pb(0);
    (*(x -> l)).s2.pb(0);(*(x -> r)).s2.pb(0);
    kk = (x -> v)[1];pp = 0;raod = 0;
    sum1 = 0,sum2 = 0;
    for(int i=1; i<(x -> v).size(); i++){
        if((x -> v)[i] != kk)pp = 1;
        if((x -> v)[i] <= mid){
            (x -> l -> v).pb((x -> v)[i]);
            sum1 += (x -> v)[i];
            raod++;
        }
        else {
            (x -> r -> v).pb((x -> v)[i]);
            sum2 += (x -> v)[i];
        }
        (x -> b).pb(raod);
        (x -> s1).pb(sum1);
        (x -> s2).pb(sum2);
    }
   
    if(pp == 0){lst[(x -> num)] = 1;return;}
    build(x -> l, L, mid);
    build(x -> r, mid + 1, R);
}
 
void sum(node *x,int L, int R,int s,int t,int maxraod){
    if(x == NULL)return;
    if(lst[x -> num] == 1){
        if((x -> v).size() == 0)return;
        if((x -> v)[1] == 0)return;
        ff += maxraod * (x -> v)[1];
        return;
    }
    if(t - s + 1 - ((x -> b)[t] - (x -> b)[s - 1]) >= maxraod){
        sum(x -> r,(L + R)/2 + 1,R , s - (x -> b)[s - 1] , t - (x -> b)[t] ,maxraod);
    }
    else {
        ff += (x -> s2)[t] - (x -> s2)[s - 1];
        sum(x -> l,L, (L + R) / 2 , (x -> b)[s - 1] + 1 , (x -> b)[t], maxraod - (t - s + 1 - ((x -> b)[t] - (x -> b)[s - 1])));
    }
}
void solve(ll l,ll r,ll x,ll y){
    l = max(l , x + m - 1);
    if(l > r)return;
    ll k = (l + r) / 2;
    ll mx = -9999999999999999 , ind = y;
    st.clear();
    ll cur = 0;
    for(int i=min(y , k - m + 1); i>=x; i--){
        ff = 0;
        sum(root , 1 , 1000000000 , i + 1 , k - 1 , m - 2);
        cur = ff + a[i].s + a[k].s - 2 * (a[k].f - a[i].f);
        if(cur > mx)
                mx = cur,
                ind = i;
    }
    if(mx == -9999999999999999)return;
    ans = max(ans , mx);
    if(l == r)return;
    solve(l , k , x , ind);
    solve(k + 1 , r , ind , y);
}
int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    
    for(int i=1; i<=n; i++){
        cin >> a[i].s >> a[i].f;
    }
    sort(a + 1 , a + n + 1);
    
    root = new node();
   
    (root -> v).pb(0);
    (root -> b).pb(0);
    (root -> s1).pb(0);
    (root -> s2).pb(0);
   
   
    root->num = 0;
   
    for(int i=1; i<=n; i++){
        (root -> v).pb(a[i].s);
    }
    cout << "\n\n";
    build(root,1 , 1000000000);
    
    solve(1 , n , 1 , n);
    
    cout << ans << '\n';
    
    
    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'void build(node*&, int, int)':
cake3.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<(x -> v).size(); i++){
                  ~^~~~~~~~~~~~~~~~

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