Submission #108027

#	Time	Username	Problem	Language	Result	Execution time	Memory
108027		dragonslayerit	Cake 3 (JOI19_cake3)	C++14	0 / 100	4 ms	388 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(){
    high_sum+=*low.rbegin();
    high.insert(*low.rbegin());
    low.erase(low.find(*low.rbegin()));
  }
  void down(){
    high_sum-=*high.begin();
    low.insert(*high.begin());
    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){
    int x=cake[i].second;
    low.insert(x);
  }
  void rem(int i){
    int x=cake[i].second;
    if(low.count(x)){
      low.erase(low.find(x));
    }else{
      assert(high.count(x));
      high_sum-=x;
      high.erase(high.find(x));
    }
  }
  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(int x:low) printf("%d ",x);
    printf("|");
    for(int x:high) printf(" %d",x);
    printf("\n");
  }
}ds;

int64_t best=0;

//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=%d: %d\n",m,max);
  solve(l,m,low,maxi);
  solve(m,r,maxi,high);
}

int64_t brute(int l,int r){
  if(r-l+1<M) return -INF;
  std::set<int> best;
  for(int i=l+1;i<r;i++){
    best.insert(cake[i].second);
  }
  while(best.size()>M-2){
    best.erase(best.begin());
  }
  best.insert(cake[l].second);
  best.insert(cake[r].second);
  int64_t sum=2LL*(cake[l].first-cake[r].first);
  for(int 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);
  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:32:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(low.size()&&high.size()<M-2){
                       ~~~~~~~~~~~^~~~
cake3.cpp:35: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:64:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(high.size()+low.size()==r-l-1);
            ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~
cake3.cpp: In function 'int64_t brute(int, int)':
cake3.cpp:102:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(best.size()>M-2){
         ~~~~~~~~~~~^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:115: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:118: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: 0 / 5
• Subtask 2: 0 / 19
• Subtask 3: 0 / 76