oj.uz

Submission #907148

# Submission time Handle Problem Language Result Execution time Memory
907148 2024-01-15T07:33:37 Z MilosMilutinovic Two Dishes (JOI19_dishes) C++14
5 / 100
 331 ms 84176 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(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;
	if(qr<=mid) rangeadd(id<<1,l,mid,ql,qr,v);
	else if(ql>mid) rangeadd(id<<1|1,mid+1,r,ql,qr,v);
	else 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(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;
	if(qr<=mid) rangeset(id<<1,l,mid,ql,qr,v);
	else if(ql>mid) rangeset(id<<1|1,mid+1,r,ql,qr,v);
	else 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 259 ms 78496 KB Output is correct
2 Correct 331 ms 84176 KB Output is correct
3 Correct 86 ms 61720 KB Output is correct
4 Correct 189 ms 66640 KB Output is correct
5 Correct 11 ms 39512 KB Output is correct
6 Correct 229 ms 84076 KB Output is correct
7 Correct 38 ms 52964 KB Output is correct
8 Correct 54 ms 52304 KB Output is correct
9 Correct 87 ms 61636 KB Output is correct
10 Correct 229 ms 81492 KB Output is correct
11 Correct 72 ms 61632 KB Output is correct

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 39512 KB Output is correct
2 Correct 10 ms 37468 KB Output is correct
3 Correct 10 ms 41564 KB Output is correct
4 Correct 10 ms 41564 KB Output is correct
5 Correct 9 ms 39516 KB Output is correct
6 Correct 10 ms 39516 KB Output is correct
7 Correct 10 ms 41564 KB Output is correct
8 Correct 10 ms 41684 KB Output is correct
9 Correct 10 ms 41564 KB Output is correct
10 Correct 11 ms 41564 KB Output is correct
11 Incorrect 10 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 10 ms 39512 KB Output is correct
2 Correct 10 ms 37468 KB Output is correct
3 Correct 10 ms 41564 KB Output is correct
4 Correct 10 ms 41564 KB Output is correct
5 Correct 9 ms 39516 KB Output is correct
6 Correct 10 ms 39516 KB Output is correct
7 Correct 10 ms 41564 KB Output is correct
8 Correct 10 ms 41684 KB Output is correct
9 Correct 10 ms 41564 KB Output is correct
10 Correct 11 ms 41564 KB Output is correct
11 Incorrect 10 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 10 ms 39512 KB Output is correct
2 Correct 10 ms 37468 KB Output is correct
3 Correct 10 ms 41564 KB Output is correct
4 Correct 10 ms 41564 KB Output is correct
5 Correct 9 ms 39516 KB Output is correct
6 Correct 10 ms 39516 KB Output is correct
7 Correct 10 ms 41564 KB Output is correct
8 Correct 10 ms 41684 KB Output is correct
9 Correct 10 ms 41564 KB Output is correct
10 Correct 11 ms 41564 KB Output is correct
11 Incorrect 10 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 10 ms 39512 KB Output is correct
2 Correct 10 ms 37468 KB Output is correct
3 Correct 10 ms 41564 KB Output is correct
4 Correct 10 ms 41564 KB Output is correct
5 Correct 9 ms 39516 KB Output is correct
6 Correct 10 ms 39516 KB Output is correct
7 Correct 10 ms 41564 KB Output is correct
8 Correct 10 ms 41684 KB Output is correct
9 Correct 10 ms 41564 KB Output is correct
10 Correct 11 ms 41564 KB Output is correct
11 Incorrect 10 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 10 ms 39512 KB Output is correct
2 Correct 10 ms 37468 KB Output is correct
3 Correct 10 ms 41564 KB Output is correct
4 Correct 10 ms 41564 KB Output is correct
5 Correct 9 ms 39516 KB Output is correct
6 Correct 10 ms 39516 KB Output is correct
7 Correct 10 ms 41564 KB Output is correct
8 Correct 10 ms 41684 KB Output is correct
9 Correct 10 ms 41564 KB Output is correct
10 Correct 11 ms 41564 KB Output is correct
11 Incorrect 10 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 259 ms 78496 KB Output is correct
2 Correct 331 ms 84176 KB Output is correct
3 Correct 86 ms 61720 KB Output is correct
4 Correct 189 ms 66640 KB Output is correct
5 Correct 11 ms 39512 KB Output is correct
6 Correct 229 ms 84076 KB Output is correct
7 Correct 38 ms 52964 KB Output is correct
8 Correct 54 ms 52304 KB Output is correct
9 Correct 87 ms 61636 KB Output is correct
10 Correct 229 ms 81492 KB Output is correct
11 Correct 72 ms 61632 KB Output is correct
12 Correct 10 ms 39512 KB Output is correct
13 Correct 10 ms 37468 KB Output is correct
14 Correct 10 ms 41564 KB Output is correct
15 Correct 10 ms 41564 KB Output is correct
16 Correct 9 ms 39516 KB Output is correct
17 Correct 10 ms 39516 KB Output is correct
18 Correct 10 ms 41564 KB Output is correct
19 Correct 10 ms 41684 KB Output is correct
20 Correct 10 ms 41564 KB Output is correct
21 Correct 11 ms 41564 KB Output is correct
22 Incorrect 10 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 259 ms 78496 KB Output is correct
2 Correct 331 ms 84176 KB Output is correct
3 Correct 86 ms 61720 KB Output is correct
4 Correct 189 ms 66640 KB Output is correct
5 Correct 11 ms 39512 KB Output is correct
6 Correct 229 ms 84076 KB Output is correct
7 Correct 38 ms 52964 KB Output is correct
8 Correct 54 ms 52304 KB Output is correct
9 Correct 87 ms 61636 KB Output is correct
10 Correct 229 ms 81492 KB Output is correct
11 Correct 72 ms 61632 KB Output is correct
12 Correct 10 ms 39512 KB Output is correct
13 Correct 10 ms 37468 KB Output is correct
14 Correct 10 ms 41564 KB Output is correct
15 Correct 10 ms 41564 KB Output is correct
16 Correct 9 ms 39516 KB Output is correct
17 Correct 10 ms 39516 KB Output is correct
18 Correct 10 ms 41564 KB Output is correct
19 Correct 10 ms 41684 KB Output is correct
20 Correct 10 ms 41564 KB Output is correct
21 Correct 11 ms 41564 KB Output is correct
22 Incorrect 10 ms 41564 KB Output isn't correct
23 Halted 0 ms 0 KB -