Submission #108033

#	Time	Username	Problem	Language	Result	Execution time	Memory
108033		dragonslayerit	Cake 3 (JOI19_cake3)	C++14	24 / 100	4088 ms	10732 KiB

cake3

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cassert>
#include <set>
#include <stdint.h>

const int64_t INF=1e15+7;

std::vector<std::pair<int,int> > cake;

int N,M;

struct DataStruct{
  std::multiset<int> low,high;
  int ll,rr;//(ll,rr) for elements, [ll,rr] for query
  int64_t high_sum;
  DataStruct():ll(0),rr(1),high_sum(0){
  }
  void up(){
    int x=*low.rbegin();
    high_sum+=x;
    high.insert(x);
    low.erase(low.find(x));
  }
  void down(){
    int x=*high.begin();
    high_sum-=x;
    low.insert(x);
    high.erase(high.begin());
  }
  void balance(){
    while(low.size()&&high.size()<M-2){
      up();
    }
    while(high.size()>M-2){
      down();
    }
    while(low.size()&&high.size()&&*low.rbegin()>*high.begin()){
      up();
      down();
    }
  }
  void add(int i){
    int64_t x=cake[i].second;
    low.insert(x);
  }
  void rem(int i){
    int64_t x=cake[i].second;
    auto it=low.find(x);
    if(it!=low.end()){
      low.erase(it);
    }else{
      it=high.find(x);
      assert(it!=high.end());
      high_sum-=x;
      high.erase(it);
    }
  }
  int64_t query(int l,int r){
    if(r-l+1<M) return -INF;
    while(ll>l) add(ll--);
    while(rr<r) add(rr++);
    while(ll<l) rem(++ll);
    while(rr>r) rem(--rr);
    balance();
    assert(high.size()+low.size()==r-l-1);
    return high_sum+cake[l].second+cake[r].second+2LL*(cake[l].first-cake[r].first);
  }
  /*
  void dump(){
    for(int64_t x:low) printf("%ld ",x);
    printf("|");
    for(int64_t x:high) printf(" %ld",x);
    printf("\n");
  }
  */
}ds;

int64_t best=-INF;

//find ans for (l,r), which must be in range [low,high]
void solve(int l,int r,int low,int high){
  if(r-l<=1) return;
  int m=(l+r)/2;
  int64_t max=-INF;
  int maxi=-1;
  for(int i=low;i<=high;i++){
    int64_t res=ds.query(m,i);
    if(res>=max){
      maxi=i;
      max=res;
    }
  }
  best=std::max(best,max);
  //printf("best with l=%ld: %ld\n",m,max);
  solve(l,m,low,maxi);
  solve(m,r,maxi,high);
}
/*
int64_t brute(int64_t l,int64_t r){
  if(r-l+1<M) return -INF;
  std::multiset<int> best;
  for(int64_t i=l+1;i<r;i++){
    best.insert(cake[i].second);
  }
  while(best.size()>M-2){
    best.erase(best.begin());
  }
  assert(best.size()==M-2);
  best.insert(cake[l].second);
  best.insert(cake[r].second);
  int64_t sum=2LL*(cake[l].first-cake[r].first);
  for(int64_t x:best){
    sum+=x;
  }
  return sum;
}
*/
int main(){
  scanf("%d %d",&N,&M);
  for(int i=0;i<N;i++){
    int V,C;
    scanf("%d %d",&V,&C);
    cake.push_back({C,V});
  }
  std::sort(cake.begin(),cake.end());
  /*
    for(int l=0;l<N;l++){
    for(int r=0;r<N;r++){
    printf("%ld,%ld ",ds.query(l,r),brute(l,r));
    }
    printf("\n");
    }
  */
  solve(-1,N,0,N-1);
  /*
  for(int l=0;l<N;l++){
    for(int r=l;r<N;r++){
      best=std::max(best,brute(l,r));
    }
  }
  */
  printf("%ld\n",best);
  //ds.query(0,N-1),ds.dump();
  return 0;
}

Compilation message (stderr)

cake3.cpp: In member function 'void DataStruct::balance()':
cake3.cpp:34:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(low.size()&&high.size()<M-2){
                       ~~~~~~~~~~~^~~~
cake3.cpp:37:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(high.size()>M-2){
           ~~~~~~~~~~~^~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from cake3.cpp:5:
cake3.cpp: In member function 'int64_t DataStruct::query(int, int)':
cake3.cpp:68:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(high.size()+low.size()==r-l-1);
            ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
cake3.cpp: In function 'int main()':
cake3.cpp:122:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&N,&M);
   ~~~~~^~~~~~~~~~~~~~~
cake3.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&V,&C);
     ~~~~~^~~~~~~~~~~~~~~

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