Submission #153148

#	Time	Username	Problem	Language	Result	Execution time	Memory
153148		username	Two Dishes (JOI19_dishes)	C++14	100 / 100	9806 ms	199852 KiB

dishes

#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()){
   ^~~

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9