46分,在线求调
查看原帖
46分,在线求调
1124954
BLty777楼主2024/12/1 17:47
#include <bits/stdc++.h>
#define int long long
#define ll p<<1
#define rr p<<1|1
using namespace std;
const int N=200005;
int k,n,c,ans;
struct stu{
	int l,r,m;
}s[N];
bool cmp(stu a,stu b){
	return a.r<b.r;
}
struct tree{
	int l,r,mx,tag;
}tr[4*N];
void pushup(int p){
	tr[p].mx=max(tr[ll].mx,tr[rr].mx);
	return ;
}
void build(int p,int l,int r){
	tr[p].l=l;
	tr[p].r=r;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(ll,l,mid);
	build(rr,mid+1,r);
	pushup(p);
}
void pushdown(int p){
	if(tr[p].tag){
		tr[ll].mx+=tr[p].tag;
		tr[rr].mx+=tr[p].tag;
		tr[ll].tag+=tr[p].tag;
		tr[rr].tag+=tr[p].tag;
		tr[p].tag=0;
	}
	return ;
}
void change(int p,int x,int y,int k){
	if(tr[p].l>=x&&tr[p].r<=y){
		tr[p].mx+=k;
		tr[p].tag+=k;
		return ;
	}
	pushdown(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if(x<=mid) change(ll,x,y,k);
	if(y>mid) change(rr,x,y,k);
	pushup(p);
}
int query(int p,int x,int y){
	if(tr[p].l>y||tr[p].r<x) return 0;
	if(tr[p].l>=x&&tr[p].r<=y){
		return tr[p].mx;
	}
	int mid=(tr[p].l+tr[p].r)>>1,num=LLONG_MIN;
	if(x<=mid) num=max(num,query(ll,x,y));
	if(y>mid) num=max(num,query(rr,x,y));
	return num;
}
signed main(){
	scanf("%lld%lld%lld",&k,&n,&c);
	for(int i=1;i<=k;i++){
		scanf("%lld%lld%lld",&s[i].l,&s[i].r,&s[i].m);
	}
	sort(s+1,s+k+1,cmp);
	build(1,1,n);
	for(int i=1;i<=k;i++){
		int mxx=query(1,s[i].l,s[i].r-1);
		int x=min(c-mxx,s[i].m);
		change(1,s[i].l,s[i].r-1,x);
		ans+=x;
	}
	printf("%lld",ans);
	return 0;
}
2024/12/1 17:47
加载中...