Submission #246503

#	Time	Username	Problem	Language	Result	Execution time	Memory
246503		red1108	Two Dishes (JOI19_dishes)	C++17	5 / 100	502 ms	78708 KiB

dishes

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define fopen freopen("input.txt", "r", stdin)
#define eb emplace_back
#define em emplace
#define prec(a) cout<<fixed;cout.precision(a);
#define all(a) (a).begin(), (a).end()
typedef long long ll;typedef long double ld;typedef unsigned long long ul;typedef unsigned int ui;typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
const ll INF = 2e18;
const int inf = 2e9;
template<class T>
void pr(T t) {cerr << t << " ";}
template<class T, class ...Args>
void pr(T a, Args ...args) {cerr << a << " ";pr(args...);}
template<class ...Args>
void prl(Args ...args) {pr(args...);cerr << endl;}


int n, m;
struct In{
	ll ti, lim, cost;
}A[1000100], B[1000100];
ll ans;
vector<pll> ad[1000100];
ll asum[1000100],bsum[1000100];
ll seg[3000100], lazy[3000100], flag[3000100]; // 구간 max, +lazy, fix

void fprop(int x, int l, int r){
	if(flag[x]==-1) return ;
	seg[x] = flag[x];lazy[x]=0;
	if(l!=r){
		flag[x*2]=flag[x];
		flag[x*2+1] = flag[x];
		lazy[x*2]=lazy[x*2+1]=0;
	}
	flag[x]=-1;
}
void prop(int x, int l, int r){
	if(flag[x]!=-1){
		fprop(x,l,r);
		return ;
	}
	if(lazy[x]==0) return ;
	int m = (l+r)/2;
	if(l!=r){
		fprop(x*2, l,m);
		fprop(x*2+1,m+1,r);
		lazy[x*2]+=lazy[x];
		lazy[x*2+1]+=lazy[x];
	}
	seg[x]+=lazy[x];
	lazy[x]=0;
	return ;
}
void add(int x, int l, int r,int s, int e, ll v){
	prop(x,l,r);
	if(r<s||e<l) return ;
	if(s<=l&&r<=e){
		lazy[x]+=v;
		prop(x,l,r);
		return ;
	}
	add(x*2, l, (l+r)/2, s, e, v);add(x*2+1, (l+r)/2+1, r, s, e, v);
	seg[x] = max(seg[x*2], seg[x*2+1]);
}
ll get_val(int x, int l, int r, int i){
	prop(x,l,r);
	if(l==r) return seg[x];
	int  m = (l+r)/2;
	if(i<=m) return get_val(x*2, l, m,i);
	else return get_val(x*2+1, m+1, r, i);
}
int get_left(int x, int l, int r, ll v){
	prop(x,l,r);
	if(l==r) return l;
	int m = (l+r)/2, ret;

	if(seg[x*2]>=v){
		prop(x*2+1,m+1,r);
		ret = get_left(x*2, l,m, v);
	}
	else {
		prop(x*2,l,m);
		ret = get_left(x*2+1,m+1, r, v);
	}
	seg[x] = max(seg[x*2], seg[x*2+1]);
	return ret;
}
void gang_fix(int x, int l, int r, int s, int e, ll v){
	prop(x,l,r);
	if(r<s||e<l) return ;
	if(s<=l&&r<=e){
		flag[x] = v;
		prop(x,l,r);
		return ;
	}
	gang_fix(x*2,l,(l+r)/2,s,e,v);
	gang_fix(x*2+1,(l+r)/2+1,r,s,e,v);
	seg[x] = max(seg[x*2], seg[x*2+1]);
}
int main(){
	fastio;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>A[i].ti>>A[i].lim>>A[i].cost;
		asum[i]=asum[i-1]+A[i].ti;
	}
	for(int i=1;i<=m;i++){
		cin>>B[i].ti>>B[i].lim>>B[i].cost;
		bsum[i]=bsum[i-1]+B[i].ti;
	}
	for(int i=1;i<=n;i++){
		if(asum[i]>A[i].lim) continue;
		int j = upper_bound(bsum,bsum+m+1, A[i].lim-asum[i])-bsum-1;
		ans+=A[i].cost;
		ad[i-1].eb(j+1, -A[i].cost);
	}
	for(int i=1;i<=m;i++){
		if(bsum[i]>B[i].lim) continue;
		int j = upper_bound(asum,asum+n+1, B[i].lim-bsum[i])-asum-1;
		ad[j].eb(i,B[i].cost);
	}
	for(int i=1;i<=3000000;i++){
		flag[i]=-1;
	}
	for(int i=0;i<=n;i++){
		sort(all(ad[i]), [](pll &a,pll &b){return a.se>b.se;});
		for(auto j:ad[i]){
			if(j.se>=0){
				add(1,0,m,j.fi,m,j.se);
				continue;
			}
			else{
				ll t = get_val(1,0,m,j.fi-1);
				int ind = get_left(1,0,m,t-j.se);
				if(ind==m&&seg[1]<t-j.se){
					gang_fix(1,0,m,j.fi,m,t);
					continue;
				}
				if(j.fi<=ind-1) gang_fix(1,0,m,j.fi,ind-1,t);
				add(1,0,m,ind,m,j.se);
			}
		}
	}
	cout<<ans+seg[1];
}

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