Submission #153040

#	Time	Username	Problem	Language	Result	Execution time	Memory
153040		username	Two Dishes (JOI19_dishes)	C++14	100 / 100	5802 ms	241340 KiB

dishes

#pragma GCC optimize("O3")
#include<stdint.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define VIS(it,con) for(auto it=con.begin();it!=con.end();++it)
#define pob pop_back
#define pf push_front
#define pof pop_front
#define MIN(x,y) (x=min(x,(y)))
#define MAX(x,y) (x=max(x,(y)))
#define mid (l+r>>1)
#define lch (idx*2+1)
#define rch (idx*2+2)
/*****************************************************************************/
#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 RREP(i,j,k) for(int i=int(j)-1;i>=(k);--i)
#define ALL(a) a.begin(),a.end()
#define pb push_back
#define f first
#define s second
#define endl '\n'
//																#define __debug
#ifdef __debug
	#define IOS (void)0
	#define de(...) cerr<<__VA_ARGS__
	#define ar(a,s,t) {REP(__i,s,t)de(a[__i]<<' ');de(endl);}
#else
	#define IOS cin.tie(0),cout.tie(0),ios_base::sync_with_stdio(false)
	#define de(...) (void)0
	#define ar(...) (void)0
#endif
/***********************************default***********************************/
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 init(int l,int r,int idx){
	dat[idx]=0,t1[idx]=0,t2[idx]=-inf;
	if(l+1<r)init(l,mid,lch),init(mid,r,rch);
}

void upd1(int idx,int k){dat[idx]+=k,t1[idx]+=k,t2[idx]+=k;}

void upd2(int idx,int k){MAX(dat[idx],k),MAX(t2[idx],k);}

void psh(int idx){
	upd1(lch,t1[idx]),upd2(lch,t2[idx]);
	upd1(rch,t1[idx]),upd2(rch,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)upd1(idx,k);
	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)upd2(idx,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(){
	IOS;
	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]});
	}
	init(0,n+1,0);
	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 init(int_fast64_t, int_fast64_t, int_fast64_t)':
dishes.cpp:14:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:46:18: note: in expansion of macro 'mid'
  if(l+1<r)init(l,mid,lch),init(mid,r,rch);
                  ^~~
dishes.cpp:14:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:46:32: note: in expansion of macro 'mid'
  if(l+1<r)init(l,mid,lch),init(mid,r,rch);
                                ^~~
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:14:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:64: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:14:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:64: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:14:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:70: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:14:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:70: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:14:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:77:8: note: in expansion of macro 'mid'
   if(p<mid)return qr(l,mid,lch,p);
        ^~~
dishes.cpp:14:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:77:24: note: in expansion of macro 'mid'
   if(p<mid)return qr(l,mid,lch,p);
                        ^~~
dishes.cpp:14:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define mid (l+r>>1)
              ~^~
dishes.cpp:78:18: note: in expansion of macro 'mid'
   else return qr(mid,r,rch,p);
                  ^~~
dishes.cpp: At global scope:
dishes.cpp:82:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
dishes.cpp: In function 'int main()':
dishes.cpp:22: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:98:3: note: in expansion of macro 'REP'
   REP(j,0,v[i].size()){
   ^~~
dishes.cpp:22: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:103: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