Submission #1252906

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252906		namhh	Two Dishes (JOI19_dishes)	C++20	82 / 100	1315 ms	157080 KiB

dishes

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
const int N = 1e6+5;
int n,m,a[N],s[N],p[N],b[N],t[N],q[N],st[4*N],lazy[4*N],pre[N],pre1[N];
vector<int>adj[N];
void down(int id){
	if(lazy[id] != 0){
		st[2*id] += lazy[id];
		st[2*id+1] += lazy[id];
		lazy[2*id] += lazy[id];
		lazy[2*id+1] += lazy[id];
		lazy[id] = 0;
	}
}
void update(int id, int l, int r, int i, int val){
	down(id);
	if(l > i || r < i) return;
	if(l == r){
		st[id] = max(st[id],val);
		return;
	}
	int mid = (l+r)/2;
	update(2*id,l,mid,i,val);
	update(2*id+1,mid+1,r,i,val);
	st[id] = max(st[2*id],st[2*id+1]);
}
void update(int id, int l, int r, int u, int v, int val){
	if(l > v || r < u) return;
	if(l >= u && r <= v){
		st[id] += val;
		lazy[id] += val;
		return;
	}
	down(id);
	int mid = (l+r)/2;
	update(2*id,l,mid,u,v,val);
	update(2*id+1,mid+1,r,u,v,val);
	st[id] = max(st[2*id],st[2*id+1]);
}
int get(int id, int l, int r, int u, int v){
	down(id);
	if(l > v || r < u) return -1e18;
	if(l >= u && r <= v) return st[id];
	int mid = (l+r)/2;
	return max(get(2*id,l,mid,u,v),get(2*id+1,mid+1,r,u,v));
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
	    cin >> a[i] >> s[i] >> p[i];
	    pre[i] = pre[i-1]+a[i];
	}
	for(int i = 1; i <= m; i++){
		cin >> b[i] >> t[i] >> q[i];
		pre1[i] = pre1[i-1]+b[i];
	}
	for(int i = 1; i <= n; i++) s[i] = upper_bound(pre1,pre1+m+1,s[i]-pre[i])-pre1-1;
	for(int i = 1; i <= m; i++){
		int cc = upper_bound(pre,pre+n+1,t[i]-pre1[i])-pre;
		adj[cc].push_back(i);
	}
	for(int i = 1; i <= n+1; i++){
        for(int v: adj[i]){
        	int x = get(1,0,m,0,v-1);
        	update(1,0,m,v,x);
		}
		if(i == n+1){
			int aqua = get(1,0,m,0,m-1);
			update(1,0,m,m,aqua);
		}
	    int aqua = get(1,0,m,0,s[i]);
	    update(1,0,m,s[i]+1,aqua);
	    update(1,0,m,0,s[i],p[i]);
	    for(int v: adj[i]) update(1,0,m,v,m,q[v]);
    }
    cout << get(1,0,m,m,m);
}

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