Submission #163564

#TimeUsernameProblemLanguageResultExecution timeMemory
163564TadijaSebezTwo Dishes (JOI19_dishes)C++14
0 / 100
685 ms55352 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int N=1000050; const int M=2*N; const ll inf=9e18; ll ckmx(ll &a, ll b){ return a=max(a,b);} int ls[M],rs[M],tsz,root; ll lzy[M][2],mx[M]; void Upd(int c, ll x, int t){ t==0?mx[c]+=x,lzy[c][0]+=x,lzy[c][1]+=x:ckmx(mx[c],x),ckmx(lzy[c][1],x);} void Push(int c){ Upd(ls[c],lzy[c][0],0);Upd(ls[c],lzy[c][1],1);Upd(rs[c],lzy[c][0],0);Upd(rs[c],lzy[c][1],1);lzy[c][0]=0;lzy[c][1]=-inf;} void Set(int c, int ss, int se, int qs, int qe, ll x, int t) { if(qs>qe || qs>se || ss>qe) return; if(qs<=ss && qe>=se) return Upd(c,x,t); int mid=ss+se>>1; Push(c); Set(ls[c],ss,mid,qs,qe,x,t); Set(rs[c],mid+1,se,qs,qe,x,t); mx[c]=max(mx[ls[c]],mx[rs[c]]); } ll Get(int c, int ss, int se, int qi) { if(ss==se) return mx[c]; int mid=ss+se>>1;Push(c); return qi<=mid?Get(ls[c],ss,mid,qi):Get(rs[c],mid+1,se,qi); } void Build(int &c, int ss, int se) { c=++tsz;lzy[c][1]=-inf; if(ss==se) return; int mid=ss+se>>1; Build(ls[c],ss,mid); Build(rs[c],mid+1,se); } ll a[N],s[N],p[N],b[N],t[N],q[N]; vector<pair<int,ll>> Us[N]; int main() { int n,m; scanf("%i %i",&n,&m); for(int i=1;i<=n;i++) scanf("%lld %lld %lld",&a[i],&s[i],&p[i]),a[i]+=a[i-1]; for(int i=1;i<=m;i++) scanf("%lld %lld %lld",&b[i],&t[i],&q[i]),b[i]+=b[i-1]; for(int i=1;i<=n;i++) { int j=upper_bound(b,b+m+1,s[i]-a[i])-b-1; if(j>=0) Us[j].pb({i,p[i]}); } ll sum=0; for(int i=1;i<=m;i++) { sum+=q[i]; int j=upper_bound(a,a+n+1,t[i]-b[i])-a; if(j<=n) Us[i-1].pb({j,-q[i]}); } Build(root,0,n); for(int i=0;i<=m;i++) { sort(Us[i].begin(),Us[i].end()); for(auto u:Us[i]) Set(root,0,n,u.first,n,u.second,0); if(i==m) break; for(auto u:Us[i]) if(u.first) Set(root,0,n,u.first,n,Get(root,0,n,u.first-1),1); } printf("%lld\n",sum+Get(root,0,n,n)); return 0; }

Compilation message (stderr)

dishes.cpp: In function 'void Set(int, int, int, int, int, long long int, int)':
dishes.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
dishes.cpp: In function 'long long int Get(int, int, int, int)':
dishes.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;Push(c);
          ~~^~~
dishes.cpp: In function 'void Build(int&, int, int)':
dishes.cpp:33:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=ss+se>>1;
          ~~^~~
dishes.cpp: In function 'int main()':
dishes.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
dishes.cpp:43:65: 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("%lld %lld %lld",&a[i],&s[i],&p[i]),a[i]+=a[i-1];
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
dishes.cpp:44:65: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%lld %lld %lld",&b[i],&t[i],&q[i]),b[i]+=b[i-1];
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...