Submission #153148

#TimeUsernameProblemLanguageResultExecution timeMemory
153148usernameTwo Dishes (JOI19_dishes)C++14
100 / 100
9806 ms199852 KiB
#pragma GCC optimize("O3") #include<bits/stdc++.h> #define int int_fast64_t using namespace std; typedef pair<int,int> pii; #define REP(i,j,k) for(int i=(j);i<(k);++i) #define MAX(x,y) (x=max(x,(y))) #define mid (l+r>>1) #define lch (idx*2+1) #define rch (idx*2+2) #define pb push_back #define f first #define s second const int maxn=1<<20,inf=1ll<<60; int n,m,res=0,a[maxn],b[maxn],s[maxn],t[maxn],p[maxn],q[maxn],dat[maxn<<1],t1[maxn<<1],t2[maxn<<1]; vector<pii>v[maxn]; void upd(int idx,int k,int l){dat[idx]+=k,t1[idx]+=k,t2[idx]+=k,MAX(dat[idx],l),MAX(t2[idx],l);} void psh(int idx){ upd(lch,t1[idx],t2[idx]); upd(rch,t1[idx],t2[idx]); t1[idx]=0,t2[idx]=-inf; } void mnt(int idx){dat[idx]=max(dat[lch],dat[rch]);} void add(int l,int r,int idx,int a,int b,int k){ if(b<=l||r<=a)return; else if(a<=l&&r<=b)upd(idx,k,-inf); else psh(idx),add(l,mid,lch,a,b,k),add(mid,r,rch,a,b,k),mnt(idx); } void enh(int l,int r,int idx,int a,int b,int k){ if(b<=l||r<=a)return; else if(a<=l&&r<=b)upd(idx,0,k); else psh(idx),enh(l,mid,lch,a,b,k),enh(mid,r,rch,a,b,k),mnt(idx); } int qr(int l,int r,int idx,int p){ if(l+1==r)return dat[idx]; else{ psh(idx); if(p<mid)return qr(l,mid,lch,p); else return qr(mid,r,rch,p); } } main(){ cin>>n>>m; REP(i,0,n)cin>>a[i+1]>>s[i]>>p[i],a[i+1]+=a[i]; REP(i,0,m)cin>>b[i+1]>>t[i]>>q[i],b[i+1]+=b[i]; REP(i,0,n){ int x=upper_bound(b,b+m+1,s[i]-a[i+1])-1-b; if(x>=0)v[x].pb({i+1,p[i]}); } REP(i,0,m){ res+=q[i]; int x=upper_bound(a,a+n+1,t[i]-b[i+1])-1-a; if(x<n)v[i].pb({x+1,-q[i]}); } fill(t2,t2+(maxn<<1),-inf); REP(i,0,m+1){ REP(j,0,v[i].size()){ pii&x=v[i][j]; add(0,n+1,0,x.f,n+1,x.s); } if(i==m)return cout<<res+qr(0,n+1,0,n)<<endl,0; REP(j,0,v[i].size()){ pii&x=v[i][j]; if(x.f)enh(0,n+1,0,x.f,n+1,qr(0,n+1,0,x.f-1)); } } }

Compilation message (stderr)

dishes.cpp: In function 'void add(int_fast64_t, int_fast64_t, int_fast64_t, int_fast64_t, int_fast64_t, int_fast64_t)':
dishes.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:32:22: note: in expansion of macro 'mid'
  else psh(idx),add(l,mid,lch,a,b,k),add(mid,r,rch,a,b,k),mnt(idx);
                      ^~~
dishes.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:32:41: note: in expansion of macro 'mid'
  else psh(idx),add(l,mid,lch,a,b,k),add(mid,r,rch,a,b,k),mnt(idx);
                                         ^~~
dishes.cpp: In function 'void enh(int_fast64_t, int_fast64_t, int_fast64_t, int_fast64_t, int_fast64_t, int_fast64_t)':
dishes.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:38:22: note: in expansion of macro 'mid'
  else psh(idx),enh(l,mid,lch,a,b,k),enh(mid,r,rch,a,b,k),mnt(idx);
                      ^~~
dishes.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:38:41: note: in expansion of macro 'mid'
  else psh(idx),enh(l,mid,lch,a,b,k),enh(mid,r,rch,a,b,k),mnt(idx);
                                         ^~~
dishes.cpp: In function 'int_fast64_t qr(int_fast64_t, int_fast64_t, int_fast64_t, int_fast64_t)':
dishes.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:45:8: note: in expansion of macro 'mid'
   if(p<mid)return qr(l,mid,lch,p);
        ^~~
dishes.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:45:24: note: in expansion of macro 'mid'
   if(p<mid)return qr(l,mid,lch,p);
                        ^~~
dishes.cpp:8:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:46:18: note: in expansion of macro 'mid'
   else return qr(mid,r,rch,p);
                  ^~~
dishes.cpp: At global scope:
dishes.cpp:50:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
dishes.cpp: In function 'int main()':
dishes.cpp:6:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
dishes.cpp:65:3: note: in expansion of macro 'REP'
   REP(j,0,v[i].size()){
   ^~~
dishes.cpp:6:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,j,k) for(int i=(j);i<(k);++i)
                                   ^
dishes.cpp:70:3: note: in expansion of macro 'REP'
   REP(j,0,v[i].size()){
   ^~~
#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...