Submission #108036

#TimeUsernameProblemLanguageResultExecution timeMemory
108036dragonslayeritCake 3 (JOI19_cake3)C++14
0 / 100
128 ms16896 KiB
#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); assert(cps.count(x)); assert(cps[x]>=0&&cps[x]<MAXN); 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); return sum; //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{ int ll,rr;//(ll,rr) for elements, [ll,rr] for query DataStruct():ll(0),rr(1){ } void add(int i){ st_insert(cake[i].second,1); } void rem(int i){ st_insert(cake[i].second,-1); } 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); } }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}); cps[V]; } { int last=0; for(auto& it:cps){ it.second=last++; } /* for(auto it:cps){ printf("V=%d: %dth\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)); assert(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 function 'int64_t brute(int64_t, int64_t)':
cake3.cpp:124: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:127:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   assert(best.size()==M-2);
          ~~~~~~~~~~~^~~~~
cake3.cpp: In function 'int main()':
cake3.cpp:138: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:141:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&V,&C);
     ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...