oj.uz

Submission #907209

# Submission time Handle Problem Language Result Execution time Memory
907209 2024-01-15T08:45:31 Z MilosMilutinovic Two Dishes (JOI19_dishes) C++14
5 / 100
 317 ms 84432 KB 
#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,m,a[1000005],p[1000005],b[1000005],q[1000005];
ll s[1000005],t[1000005],pa[1000005],pb[1000005],mx[4000005],inc[4000005],val[4000005];
bool tag[4000005];
vector<pii> qs[1000005];

void pushdown(int id){
	if(tag[id]){
		mx[id<<1]=val[id];
		mx[id<<1|1]=val[id];
		val[id<<1]=val[id];
		val[id<<1|1]=val[id];
		inc[id<<1]=0;
		inc[id<<1|1]=0;
		tag[id<<1]=true;
		tag[id<<1|1]=true;
		inc[id]=0;
		tag[id]=false;
	}else{
		mx[id<<1]+=inc[id];
		mx[id<<1|1]+=inc[id];
		if(tag[id<<1]) val[id<<1]+=inc[id];
		else inc[id<<1]+=inc[id];
		if(tag[id<<1|1]) val[id<<1|1]+=inc[id];
		else inc[id<<1|1]+=inc[id];
		inc[id]=0;
	}
}

void rangeadd(int id,int l,int r,int ql,int qr,ll v){
	if(l>r||ql>qr||l>qr||r<ql) return;
	if(ql<=l&&r<=qr){
		mx[id]+=v;
		if(tag[id]) val[id]+=v;
		else inc[id]+=v;
		pushdown(id);
		return;
	}
	pushdown(id);
	int mid=(l+r)/2;
	rangeadd(id<<1,l,mid,ql,qr,v);
	rangeadd(id<<1|1,mid+1,r,ql,qr,v);
	mx[id]=max(mx[id<<1],mx[id<<1|1]);
}

void rangeset(int id,int l,int r,int ql,int qr,ll v){
	if(l>r||ql>qr||l>qr||r<ql) return;
	if(ql<=l&&r<=qr){
		mx[id]=v;
		val[id]=v;
		tag[id]=true;
		inc[id]=0;
		pushdown(id);
		return;
	}
	pushdown(id);
	int mid=(l+r)/2;
	rangeset(id<<1,l,mid,ql,qr,v);
	rangeset(id<<1|1,mid+1,r,ql,qr,v);
	mx[id]=max(mx[id<<1],mx[id<<1|1]);
}

ll query(int id,int l,int r,int qi){
	if(l==r) return mx[id];
	pushdown(id);
	int mid=(l+r)/2;
	ll ret=0;
	if(qi<=mid) ret=query(id<<1,l,mid,qi);
	else ret=query(id<<1|1,mid+1,r,qi);
	mx[id]=max(mx[id<<1],mx[id<<1|1]);
	return ret;
}

int main() {
	n=readint(); m=readint();
	for(int i=1;i<=n;i++){
		a[i]=readint();
		s[i]=readint();
		p[i]=readint();
	}
	for(int i=1;i<=m;i++){
		b[i]=readint();
		t[i]=readint();
		q[i]=readint();
	}
	for(int i=1;i<=n;i++) pa[i]=pa[i-1]+a[i];
	for(int i=1;i<=m;i++) pb[i]=pb[i-1]+b[i];
	for(int i=1;i<=n;i++){
		if(s[i]<pa[i]) continue;
		int l=1,r=m,pos=0;
		while(l<=r){
			int mid=(l+r)/2;
			if(pa[i]+pb[mid]<=s[i]) pos=mid,l=mid+1;
			else r=mid-1;
		}
		qs[i].pb(mp(pos,p[i]));
	}
	ll res=0;
	for(int i=1;i<=m;i++){
		if(t[i]<pb[i]) continue;
		int l=1,r=n,pos=0;
		while(l<=r){
			int mid=(l+r)/2;
			if(pa[mid]+pb[i]<=t[i]) pos=mid,l=mid+1;
			else r=mid-1;
		}
		res+=q[i];
		qs[pos+1].pb(mp(i-1,-q[i]));
	}
	for(int i=0;i<=n;i++){
		sort(qs[i].begin(),qs[i].end());
		vector<int> xs(1,m);
		for(auto&p:qs[i]){
			rangeadd(1,0,m,0,p.first,p.second);
			xs.push_back(p.first);
		}
		sort(xs.begin(),xs.end());
		xs.erase(unique(xs.begin(),xs.end()),xs.end());
		for(int j=1;j<(int)xs.size();j++){
			ll vl=query(1,0,m,xs[j-1]);
			ll vr=query(1,0,m,xs[j]);
			rangeset(1,0,m,xs[j-1]+1,xs[j],max(vl,vr));
		}
	}
	printf("%lld\n",query(1,0,m,m)+res);
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 82512 KB Output is correct
2 Correct 317 ms 84432 KB Output is correct
3 Correct 115 ms 61636 KB Output is correct
4 Correct 209 ms 74832 KB Output is correct
5 Correct 11 ms 41564 KB Output is correct
6 Correct 275 ms 83916 KB Output is correct
7 Correct 39 ms 59072 KB Output is correct
8 Correct 56 ms 52128 KB Output is correct
9 Correct 90 ms 61720 KB Output is correct
10 Correct 273 ms 81372 KB Output is correct
11 Correct 64 ms 61636 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 41564 KB Output is correct
2 Correct 10 ms 37468 KB Output is correct
3 Correct 10 ms 41564 KB Output is correct
4 Correct 11 ms 41564 KB Output is correct
5 Correct 11 ms 41564 KB Output is correct
6 Correct 12 ms 41560 KB Output is correct
7 Incorrect 10 ms 41564 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 41564 KB Output is correct
2 Correct 10 ms 37468 KB Output is correct
3 Correct 10 ms 41564 KB Output is correct
4 Correct 11 ms 41564 KB Output is correct
5 Correct 11 ms 41564 KB Output is correct
6 Correct 12 ms 41560 KB Output is correct
7 Incorrect 10 ms 41564 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 41564 KB Output is correct
2 Correct 10 ms 37468 KB Output is correct
3 Correct 10 ms 41564 KB Output is correct
4 Correct 11 ms 41564 KB Output is correct
5 Correct 11 ms 41564 KB Output is correct
6 Correct 12 ms 41560 KB Output is correct
7 Incorrect 10 ms 41564 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 41564 KB Output is correct
2 Correct 10 ms 37468 KB Output is correct
3 Correct 10 ms 41564 KB Output is correct
4 Correct 11 ms 41564 KB Output is correct
5 Correct 11 ms 41564 KB Output is correct
6 Correct 12 ms 41560 KB Output is correct
7 Incorrect 10 ms 41564 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 41564 KB Output is correct
2 Correct 10 ms 37468 KB Output is correct
3 Correct 10 ms 41564 KB Output is correct
4 Correct 11 ms 41564 KB Output is correct
5 Correct 11 ms 41564 KB Output is correct
6 Correct 12 ms 41560 KB Output is correct
7 Incorrect 10 ms 41564 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 82512 KB Output is correct
2 Correct 317 ms 84432 KB Output is correct
3 Correct 115 ms 61636 KB Output is correct
4 Correct 209 ms 74832 KB Output is correct
5 Correct 11 ms 41564 KB Output is correct
6 Correct 275 ms 83916 KB Output is correct
7 Correct 39 ms 59072 KB Output is correct
8 Correct 56 ms 52128 KB Output is correct
9 Correct 90 ms 61720 KB Output is correct
10 Correct 273 ms 81372 KB Output is correct
11 Correct 64 ms 61636 KB Output is correct
12 Correct 11 ms 41564 KB Output is correct
13 Correct 10 ms 37468 KB Output is correct
14 Correct 10 ms 41564 KB Output is correct
15 Correct 11 ms 41564 KB Output is correct
16 Correct 11 ms 41564 KB Output is correct
17 Correct 12 ms 41560 KB Output is correct
18 Incorrect 10 ms 41564 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 82512 KB Output is correct
2 Correct 317 ms 84432 KB Output is correct
3 Correct 115 ms 61636 KB Output is correct
4 Correct 209 ms 74832 KB Output is correct
5 Correct 11 ms 41564 KB Output is correct
6 Correct 275 ms 83916 KB Output is correct
7 Correct 39 ms 59072 KB Output is correct
8 Correct 56 ms 52128 KB Output is correct
9 Correct 90 ms 61720 KB Output is correct
10 Correct 273 ms 81372 KB Output is correct
11 Correct 64 ms 61636 KB Output is correct
12 Correct 11 ms 41564 KB Output is correct
13 Correct 10 ms 37468 KB Output is correct
14 Correct 10 ms 41564 KB Output is correct
15 Correct 11 ms 41564 KB Output is correct
16 Correct 11 ms 41564 KB Output is correct
17 Correct 12 ms 41560 KB Output is correct
18 Incorrect 10 ms 41564 KB Output isn't correct
19 Halted 0 ms 0 KB -