Submission #249442

#	Time	Username	Problem	Language	Result	Execution time	Memory
249442		tqbfjotld	Cake 3 (JOI19_cake3)	C++14	5 / 100	4057 ms	1280 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n,m;
vector<pair<int,int> > cake;

struct node{
    int s,e;
    vector<int> v;
    vector<int> pref;
    node *l,*r;
    node (int _s, int _e){
        //printf("new nd %lld %lld\n",_s,_e);
        s = _s;
        e = _e;
        for (int x = s; x<=e; x++){
            v.push_back(-cake[x].second);
        }
        sort(v.begin(),v.end());
        pref.push_back(v[0]);
        for (int x = 1; x<v.size(); x++){
            pref.push_back(pref[x-1]+v[x]);
        }
        if (s!=e){
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
        }
    }
    int numBigger(int a, int b, int num){ ///number of elements >= num
        //printf("qu %lld %lld %lld\n",a,b,num);
        if (a<=s && e<=b){
            return upper_bound(v.begin(),v.end(),-num)-v.begin();
        }
        if (b<=(s+e)/2) return l->numBigger(a,b,num);
        if (a>(s+e)/2) return r->numBigger(a,b,num);
        return l->numBigger(a,b,num)+r->numBigger(a,b,num);
    }
    int sumBigger(int a, int b, int num){
        if (a<=s && e<=b){
            int t = upper_bound(v.begin(),v.end(),-num)-v.begin()-1;
            return t<=-1?0:-pref[t];
        }
        if (b<=(s+e)/2) return l->sumBigger(a,b,num);
        if (a>(s+e)/2) return r->sumBigger(a,b,num);
        return l->sumBigger(a,b,num)+r->sumBigger(a,b,num);
    }

}*root;

 main(){
    scanf("%lld%lld",&n,&m);
    for (int x = 0; x<n; x++){
        int a,b;
        scanf("%lld%lld",&a,&b);
        cake.push_back({b,a});
    }
    sort(cake.begin(),cake.end());
    root = new node(0,n-1);
    int ans = -999999999999999999LL;
    for (int x = 0; x<n; x++){
        for (int y = x+m-1; y<n; y++){
            ///find m-th largest element in range
            int l = 0;
            int r = 10000000001LL;
            while (l+1<r){
                int mid = (l+r)/2;
                if (root->numBigger(x,y,mid)>=m){
                    l = mid;
                }
                else r = mid;
            }
            //printf("l = %lld\n",l);
            //printf("numbigger x,y,l %lld\n",root->numBigger(x,y,l));
            int opt = root->sumBigger(x,y,l);
            opt -= (root->numBigger(x,y,l)-m)*l;
            opt -= 2*(cake[y].first-cake[x].first);
            //printf("try %lld-%lld, got %lld\n",x,y,opt);
            ans = max(ans,opt);
        }
    }
    printf("%lld",ans);

}

Compilation message (stderr)

cake3.cpp: In constructor 'node::node(long long int, long long int)':
cake3.cpp:22:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int x = 1; x<v.size(); x++){
                         ~^~~~~~~~~
cake3.cpp: At global scope:
cake3.cpp:51:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  main(){
       ^
cake3.cpp: In function 'int main()':
cake3.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~~~~
cake3.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~~~~

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