oj.uz

Submission #907134

# Submission time Handle Problem Language Result Execution time Memory
907134 2024-01-15T07:25:39 Z MilosMilutinovic Two Dishes (JOI19_dishes) C++14
5 / 100
 300 ms 98124 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];
		inc[id<<1]+=inc[id];
		inc[id<<1|1]+=inc[id];
		val[id<<1]+=inc[id];
		val[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;
		inc[id]+=v;
		val[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 269 ms 96384 KB Output is correct
2 Correct 300 ms 98124 KB Output is correct
3 Correct 96 ms 78992 KB Output is correct
4 Correct 189 ms 88404 KB Output is correct
5 Correct 11 ms 41564 KB Output is correct
6 Correct 242 ms 97524 KB Output is correct
7 Correct 42 ms 65988 KB Output is correct
8 Correct 58 ms 61196 KB Output is correct
9 Correct 92 ms 80180 KB Output is correct
10 Correct 239 ms 88724 KB Output is correct
11 Correct 70 ms 73412 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 39516 KB Output is correct
3 Correct 11 ms 43612 KB Output is correct
4 Correct 10 ms 41564 KB Output is correct
5 Correct 11 ms 41608 KB Output is correct
6 Correct 12 ms 41564 KB Output is correct
7 Correct 11 ms 41564 KB Output is correct
8 Correct 12 ms 41648 KB Output is correct
9 Correct 11 ms 41564 KB Output is correct
10 Correct 11 ms 41564 KB Output is correct
11 Incorrect 12 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 41564 KB Output is correct
2 Correct 10 ms 39516 KB Output is correct
3 Correct 11 ms 43612 KB Output is correct
4 Correct 10 ms 41564 KB Output is correct
5 Correct 11 ms 41608 KB Output is correct
6 Correct 12 ms 41564 KB Output is correct
7 Correct 11 ms 41564 KB Output is correct
8 Correct 12 ms 41648 KB Output is correct
9 Correct 11 ms 41564 KB Output is correct
10 Correct 11 ms 41564 KB Output is correct
11 Incorrect 12 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 41564 KB Output is correct
2 Correct 10 ms 39516 KB Output is correct
3 Correct 11 ms 43612 KB Output is correct
4 Correct 10 ms 41564 KB Output is correct
5 Correct 11 ms 41608 KB Output is correct
6 Correct 12 ms 41564 KB Output is correct
7 Correct 11 ms 41564 KB Output is correct
8 Correct 12 ms 41648 KB Output is correct
9 Correct 11 ms 41564 KB Output is correct
10 Correct 11 ms 41564 KB Output is correct
11 Incorrect 12 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 41564 KB Output is correct
2 Correct 10 ms 39516 KB Output is correct
3 Correct 11 ms 43612 KB Output is correct
4 Correct 10 ms 41564 KB Output is correct
5 Correct 11 ms 41608 KB Output is correct
6 Correct 12 ms 41564 KB Output is correct
7 Correct 11 ms 41564 KB Output is correct
8 Correct 12 ms 41648 KB Output is correct
9 Correct 11 ms 41564 KB Output is correct
10 Correct 11 ms 41564 KB Output is correct
11 Incorrect 12 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 41564 KB Output is correct
2 Correct 10 ms 39516 KB Output is correct
3 Correct 11 ms 43612 KB Output is correct
4 Correct 10 ms 41564 KB Output is correct
5 Correct 11 ms 41608 KB Output is correct
6 Correct 12 ms 41564 KB Output is correct
7 Correct 11 ms 41564 KB Output is correct
8 Correct 12 ms 41648 KB Output is correct
9 Correct 11 ms 41564 KB Output is correct
10 Correct 11 ms 41564 KB Output is correct
11 Incorrect 12 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 269 ms 96384 KB Output is correct
2 Correct 300 ms 98124 KB Output is correct
3 Correct 96 ms 78992 KB Output is correct
4 Correct 189 ms 88404 KB Output is correct
5 Correct 11 ms 41564 KB Output is correct
6 Correct 242 ms 97524 KB Output is correct
7 Correct 42 ms 65988 KB Output is correct
8 Correct 58 ms 61196 KB Output is correct
9 Correct 92 ms 80180 KB Output is correct
10 Correct 239 ms 88724 KB Output is correct
11 Correct 70 ms 73412 KB Output is correct
12 Correct 11 ms 41564 KB Output is correct
13 Correct 10 ms 39516 KB Output is correct
14 Correct 11 ms 43612 KB Output is correct
15 Correct 10 ms 41564 KB Output is correct
16 Correct 11 ms 41608 KB Output is correct
17 Correct 12 ms 41564 KB Output is correct
18 Correct 11 ms 41564 KB Output is correct
19 Correct 12 ms 41648 KB Output is correct
20 Correct 11 ms 41564 KB Output is correct
21 Correct 11 ms 41564 KB Output is correct
22 Incorrect 12 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 269 ms 96384 KB Output is correct
2 Correct 300 ms 98124 KB Output is correct
3 Correct 96 ms 78992 KB Output is correct
4 Correct 189 ms 88404 KB Output is correct
5 Correct 11 ms 41564 KB Output is correct
6 Correct 242 ms 97524 KB Output is correct
7 Correct 42 ms 65988 KB Output is correct
8 Correct 58 ms 61196 KB Output is correct
9 Correct 92 ms 80180 KB Output is correct
10 Correct 239 ms 88724 KB Output is correct
11 Correct 70 ms 73412 KB Output is correct
12 Correct 11 ms 41564 KB Output is correct
13 Correct 10 ms 39516 KB Output is correct
14 Correct 11 ms 43612 KB Output is correct
15 Correct 10 ms 41564 KB Output is correct
16 Correct 11 ms 41608 KB Output is correct
17 Correct 12 ms 41564 KB Output is correct
18 Correct 11 ms 41564 KB Output is correct
19 Correct 12 ms 41648 KB Output is correct
20 Correct 11 ms 41564 KB Output is correct
21 Correct 11 ms 41564 KB Output is correct
22 Incorrect 12 ms 41564 KB Output isn't correct
23 Halted 0 ms 0 KB -