Submission #709845

#	Time	Username	Problem	Language	Result	Execution time	Memory
709845		alvingogo	Two Dishes (JOI19_dishes)	C++14	100 / 100	6622 ms	376264 KiB

dishes

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
#define int long long
using namespace std;

const int inf=1e18;
struct ST{
	vector<pair<int,int> > st;
	void init(int x){
		st.resize(4*x);
	}
	void upd(int v,int x){
		st[v].fs+=x;
		st[v].sc+=x;
	}
	void pudo(int v){
		upd(2*v+1,st[v].sc);
		upd(2*v+2,st[v].sc);
		st[v].sc=0;
	}
	void pull(int v){
		st[v].fs=max(st[2*v+1].fs,st[2*v+2].fs);
	}
	void update(int v,int L,int R,int l,int r,int k){
		if(L==l && r==R){
			upd(v,k);
			return;
		}
		int m=(L+R)/2;
		pudo(v);
		if(r<=m){
			update(2*v+1,L,m,l,r,k);
		}
		else if(l>m){
			update(2*v+2,m+1,R,l,r,k);
		}
		else{
			update(2*v+1,L,m,l,m,k);
			update(2*v+2,m+1,R,m+1,r,k);
		}
		pull(v);
	}
	int query(int v,int L,int R,int l,int r){
		if(L==l && r==R){
			return st[v].fs;
		}
		pudo(v);
		int m=(L+R)/2;
		if(r<=m){
			return query(2*v+1,L,m,l,r);
		}
		else if(l>m){
			return query(2*v+2,m+1,R,l,r);
		}
		else{
			return max(query(2*v+1,L,m,l,m),query(2*v+2,m+1,R,m+1,r));
		}
	}
}st;

struct BIT{
	int n;
	vector<int> bt;
	void init(int x){
		n=x;
		bt.resize(n+1);
	}
	void update(int x,int y){
		for(;x>0;x-=(x&-x)){
			bt[x]+=y;
		}
	}
	int query(int x){
		int ans=0;
		for(;x<=n;x+=(x&-x)){
			ans+=bt[x];
		}
		return ans;
	}
}bt,bt2;


bool cmp(pair<int,int> a,pair<int,int> b){
	return a.sc!=b.sc?a.sc<b.sc:a.fs<b.fs;
}
signed main(){
    AquA;
	//freopen("07-10.txt","r",stdin);
	//freopen("ans.txt","w",stdout);
	int n,m;
	cin >> n >> m;
	vector<int> a(n+1),b(m+1),s(n+1),t(m+1),p(n+1),q(m+1);
	for(int i=1;i<=n;i++){
		cin >> a[i] >> s[i] >> p[i];
		a[i]+=a[i-1];
	}
	for(int j=1;j<=m;j++){
		cin >> b[j] >> t[j] >> q[j];
		b[j]+=b[j-1];
	}
	vector<pair<int,int> > gg;
	vector<int> oka(n+1),okb(m+1);
	vector<pair<int,int> > to;
	vector<int> vis(n+2);
	for(int i=1;i<=n;i++){
		oka[i]=upper_bound(b.begin(),b.end(),s[i]-a[i])-b.begin()-1;
		if(oka[i]<0){
			p[i]=0;
			continue;
		}
		to.push_back({oka[i],i});
	}
	for(int i=1;i<=m;i++){
		okb[i]=upper_bound(a.begin(),a.end(),t[i]-b[i])-a.begin()-1;
		if(okb[i]<0){
			q[i]=0;
			continue;
		}
		if(okb[i]>=n){
		}
		else{
			to.push_back({i-1,okb[i]+1});
		}
	}
	/*
	for(int i=1;i<=n;i++){
		cout << oka[i] << " ";
	}
	cout << "\n";
	for(int i=1;i<=n;i++){
		cout << okb[i] << " ";
	}
	cout << "\n";
	*/
	to.push_back({m,n+1});
	sort(to.begin(),to.end(),[&](pair<int,int> a,pair<int,int> b){
		return a<b;
	});
	to.erase(unique(to.begin(),to.end()),to.end());
	gg=to;
	sort(gg.begin(),gg.end(),cmp);
	int sz=gg.size();
	vector<int> newp(sz+1);
	st.init(sz+1);
	bt.init(sz);
	bt2.init(sz);
	st.update(0,0,sz,1,sz,-inf);
	vector<int> vis2(sz+1,0);
	vector<int> pu(n+1);
	for(int i=1;i<=n;i++){
		if(oka[i]>=0){
			int u=lower_bound(gg.begin(),gg.end(),pair<int,int>(-inf,i),cmp)-gg.begin()+1;
			st.update(0,0,sz,0,u-1,p[i]);
			bt.update(u,p[i]);
			pu[i]=u;
		}
	}
	for(auto &h:to){
		int flag=-1;
		if(!vis[h.sc] && h.fs==oka[h.sc]){
			vis[h.sc]=1;
			flag=h.sc;
		}
		h.sc=lower_bound(gg.begin(),gg.end(),h,cmp)-gg.begin()+1;
		if(flag>=0){
			newp[h.sc]=p[flag];
			vis2[h.sc]=pu[flag];
		}
	}
	int l=0;
	vector<int> dp(sz+1);
	for(int i=1;i<=m;i++){
		if(okb[i]>=0){
			okb[i]=lower_bound(gg.begin(),gg.end(),pair<int,int>(-inf,okb[i]+1),cmp)-gg.begin();
		}
	}
	for(int i=0;i<=m;i++){
		if(i>0 && okb[i]>=0){
			st.update(0,0,sz,0,okb[i],q[i]);
			bt2.update(okb[i],q[i]);
		}
		int lst=0;
		while(l<(int)to.size() && to[l].fs==i){
			int x=to[l].sc;
			dp[x]=st.query(0,0,sz,lst,x-1)-bt.query(x+1);
			st.update(0,0,sz,x,x,dp[x]+inf-bt2.query(x));
			if(vis2[x]){
				st.update(0,0,sz,0,vis2[x]-1,-newp[x]);
				bt.update(vis2[x],-newp[x]);
			}
			l++;
			lst=x;
		}
	}
	cout << dp[sz] << "\n";
    return 0;
}

• 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