Submission #108034

#	Time	Username	Problem	Language	Result	Execution time	Memory
108034		dragonslayerit	Cake 3 (JOI19_cake3)	C++14	0 / 100	100 ms	8568 KiB

cake3

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

const int64_t INF=1e15+7;

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

std::map<int,int> cps;

int N,M;

const int MAXN=1<<18;

struct Node{
  int cnt;
  int64_t sum;
  Node():cnt(0),sum(0){
  }
}st[MAXN*2];
void st_add(int i,int c,int64_t v){
  //printf("st_add(%d,%d,%ld)\n",i,c,v);
  for(i+=MAXN;i>0;i>>=1){
    st[i].cnt+=c;
    st[i].sum+=v;
  }
}

void st_insert(int x,int c){
  //printf("st_insert(%d) x%d\n",x,c);
  st_add(cps[x],c,x*c);
}

int64_t st_sum(int w,int L,int R,int k){
  assert(st[w].cnt>=k);
  if(st[w].cnt==k){
    return st[w].sum;
  }
  int M=(L+R)/2;
  if(st[w<<1|1].cnt>=k){
    return st_sum(w<<1|1,M,R,k);
  }else{
    return st_sum(w<<1,L,M,k-st[w<<1|1].cnt)+st[w<<1|1].sum;
  }
}

void st_dump();

int64_t st_sum(int k){
  
  int64_t sum=0,cnt=0;
  for(int i=MAXN-1;i>=0&&cnt<k;i--){
    sum+=st[i+MAXN].sum;
    cnt+=st[i+MAXN].cnt;
  }
  assert(cnt==k);
  
  //st_dump();
  //printf("st_sum(%d)=%ld\n",k,sum);
  assert(sum==st_sum(1,0,MAXN,k));
  return st_sum(1,0,MAXN,k);
}

void st_dump(){
  for(int i=0;i<2*MAXN;i++){
    if(st[i].cnt) printf(" ST[%d](%d): %ld\n",i,st[i].cnt,st[i].sum);
  }
}

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){
    st_insert(cake[i].second,1);
    return;
    int64_t x=cake[i].second;
    low.insert(x);
  }
  void rem(int i){
    st_insert(cake[i].second,-1);
    return;
    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);
    return st_sum(M-2)+cake[l].second+cake[r].second;//+2LL*(cake[l].first-cake[r].first);
    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=0;//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});
    cps[V];
  }
  {
    int last=0;
    for(auto& it:cps){
      it.second=last++;
    }
    for(auto it:cps){
      //printf("V=%d: %dyh\n",it.first,it.second);
    }
  }
  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:94:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(low.size()&&high.size()<M-2){
                       ~~~~~~~~~~~^~~~
cake3.cpp:97: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:133: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(int64_t, int64_t)':
cake3.cpp:173:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(best.size()>M-2){
         ~~~~~~~~~~~^~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from cake3.cpp:5:
cake3.cpp:176:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(best.size()==M-2);
          ~~~~~~~~~~~^~~~~
cake3.cpp: In function 'int main()':
cake3.cpp:199:14: warning: variable 'it' set but not used [-Wunused-but-set-variable]
     for(auto it:cps){
              ^~
cake3.cpp:187: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:190: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