oj.uz

Submission #907207

# Submission time Handle Problem Language Result Execution time Memory
907207 2024-01-15T08:44:17 Z MilosMilutinovic Two Dishes (JOI19_dishes) C++14
5 / 100
 300 ms 84180 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]);
			if(vl>vr) rangeset(1,0,m,xs[j-1],xs[j],vl);
		}
	}
	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 270 ms 78676 KB Output is correct
2 Correct 300 ms 84180 KB Output is correct
3 Correct 84 ms 61636 KB Output is correct
4 Correct 182 ms 66464 KB Output is correct
5 Correct 10 ms 39516 KB Output is correct
6 Correct 239 ms 84076 KB Output is correct
7 Correct 38 ms 52932 KB Output is correct
8 Correct 57 ms 52124 KB Output is correct
9 Correct 86 ms 61500 KB Output is correct
10 Correct 235 ms 81492 KB Output is correct
11 Correct 66 ms 61704 KB Output is correct

Subtask #2
0 / 3.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 39.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 78676 KB Output is correct
2 Correct 300 ms 84180 KB Output is correct
3 Correct 84 ms 61636 KB Output is correct
4 Correct 182 ms 66464 KB Output is correct
5 Correct 10 ms 39516 KB Output is correct
6 Correct 239 ms 84076 KB Output is correct
7 Correct 38 ms 52932 KB Output is correct
8 Correct 57 ms 52124 KB Output is correct
9 Correct 86 ms 61500 KB Output is correct
10 Correct 235 ms 81492 KB Output is correct
11 Correct 66 ms 61704 KB Output is correct
12 Correct 11 ms 39516 KB Output is correct
13 Correct 10 ms 37508 KB Output is correct
14 Correct 11 ms 41560 KB Output is correct
15 Correct 10 ms 41560 KB Output is correct
16 Correct 10 ms 39516 KB Output is correct
17 Correct 11 ms 39632 KB Output is correct
18 Correct 11 ms 41564 KB Output is correct
19 Correct 10 ms 41560 KB Output is correct
20 Correct 11 ms 41564 KB Output is correct
21 Correct 11 ms 41564 KB Output is correct
22 Incorrect 11 ms 41564 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 78676 KB Output is correct
2 Correct 300 ms 84180 KB Output is correct
3 Correct 84 ms 61636 KB Output is correct
4 Correct 182 ms 66464 KB Output is correct
5 Correct 10 ms 39516 KB Output is correct
6 Correct 239 ms 84076 KB Output is correct
7 Correct 38 ms 52932 KB Output is correct
8 Correct 57 ms 52124 KB Output is correct
9 Correct 86 ms 61500 KB Output is correct
10 Correct 235 ms 81492 KB Output is correct
11 Correct 66 ms 61704 KB Output is correct
12 Correct 11 ms 39516 KB Output is correct
13 Correct 10 ms 37508 KB Output is correct
14 Correct 11 ms 41560 KB Output is correct
15 Correct 10 ms 41560 KB Output is correct
16 Correct 10 ms 39516 KB Output is correct
17 Correct 11 ms 39632 KB Output is correct
18 Correct 11 ms 41564 KB Output is correct
19 Correct 10 ms 41560 KB Output is correct
20 Correct 11 ms 41564 KB Output is correct
21 Correct 11 ms 41564 KB Output is correct
22 Incorrect 11 ms 41564 KB Output isn't correct
23 Halted 0 ms 0 KB -