제출 #126312

#제출 시각아이디문제언어결과실행 시간메모리
126312TadijaSebezCake 3 (JOI19_cake3)C++11
100 / 100
3405 ms89220 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const ll inf=1e18; const int N=200050; const int M=20*N; int v[N],c[N],id[N],idv[N],pos[N],n,m; int ls[M],rs[M],tsz,root[N],sz[M]; ll sum[M]; void Set(int p, int &c, int ss, int se, int qi, ll x) { c=++tsz;ls[c]=ls[p];rs[c]=rs[p];sum[c]=sum[p]+x;sz[c]=sz[p]+1; if(ss==se) return; int mid=ss+se>>1; if(qi<=mid) Set(ls[p],ls[c],ss,mid,qi,x); else Set(rs[p],rs[c],mid+1,se,qi,x); } ll Get(int p, int c, int ss, int se, int k) { ll ans=0; while(1) { if(ss==se){ if(k>0) ans+=sum[c];break;} int mid=ss+se>>1; int A=sz[ls[c]]-sz[ls[p]]; if(A<=k) k-=A,ans+=sum[ls[c]]-sum[ls[p]],ss=mid+1,p=rs[p],c=rs[c]; else se=mid,p=ls[p],c=ls[c]; } return ans; } ll Get(int l, int r) { return v[id[l]]+c[id[l]]+v[id[r]]-c[id[r]]+Get(root[l],root[r-1],1,n,m-2); } int nxt[N],pre[N]; vector<int> work[N]; void Del(int x) { int l=pre[x],r=nxt[x]; pre[x]=nxt[x]=0; nxt[l]=r; pre[r]=l; } void Add(int x) { int las=pre[0]; nxt[las]=x; pre[x]=las; pre[0]=x; nxt[x]=0; } int main() { scanf("%i %i",&n,&m); for(int i=1;i<=n;i++) scanf("%i %i",&v[i],&c[i]),c[i]*=2,id[i]=idv[i]=i; sort(id+1,id+1+n,[&](int i, int j){ return c[i]<c[j];}); sort(idv+1,idv+1+n,[&](int i, int j){ return v[i]>v[j];}); for(int i=1;i<=n;i++) pos[idv[i]]=i; for(int i=1;i<=n;i++) Set(root[i-1],root[i],1,n,pos[id[i]],v[id[i]]); vector<int> L,R; for(int i=1;i<=n;i++) if(i==1 || v[id[i]]+c[id[i]]>v[id[L.back()]]+c[id[L.back()]]) L.pb(i); for(int i=n;i>=1;i--) if(i==n || v[id[i]]-c[id[i]]>v[id[R.back()]]-c[id[R.back()]]) R.pb(i); reverse(R.begin(),R.end()); ll ans=-inf; for(int i=0,j=0;i<R.size();i++) { while(j<L.size() && R[i]-L[j]+1>=m) { Add(L[j]); work[i].pb(L[j]); j++; } reverse(work[i].begin(),work[i].end()); for(int x:work[i]) { while(pre[x]!=0 && Get(pre[x],R[i])<=Get(x,R[i])) Del(pre[x]); if(pre[x]!=0) { int top=(int)R.size()-1,bot=i+1,mid,ans=-1; while(top>=bot) { mid=top+bot>>1; if(Get(pre[x],R[mid])<=Get(x,R[mid])) ans=mid,top=mid-1; else bot=mid+1; } if(ans!=-1) work[ans].pb(x); else Del(x); } } if(nxt[0]!=0) ans=max(ans,Get(nxt[0],R[i])); } printf("%lld\n",ans); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp: In function 'void Set(int, int&, int, int, int, long long int)':
cake3.cpp:15:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
cake3.cpp: In function 'long long int Get(int, int, int, int, int)':
cake3.cpp:25:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:66:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0,j=0;i<R.size();i++)
                  ~^~~~~~~~~
cake3.cpp:68:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<L.size() && R[i]-L[j]+1>=m)
         ~^~~~~~~~~
cake3.cpp:83:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      mid=top+bot>>1;
          ~~~^~~~
cake3.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
cake3.cpp:56:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i",&v[i],&c[i]),c[i]*=2,id[i]=idv[i]=i;
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...