/ Randle /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 3ms 3.055 MiB
#2 Accepted 2ms 1.18 MiB
#3 Accepted 2ms 3.164 MiB
#4 Accepted 2ms 1.066 MiB
#5 Accepted 2ms 2.434 MiB
#6 Accepted 2ms 1.18 MiB
#7 Accepted 26ms 3.551 MiB
#8 Accepted 25ms 3.684 MiB
#9 Accepted 26ms 3.676 MiB
#10 Accepted 30ms 2.934 MiB

代码

#include<bits/stdc++.h>
inline const void read(int &a)
{
	a=0;char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')
	{
		a=(a<<1)+(a<<3)+c-'0';
		c=getchar();
	}
}
const int maxn=2e5;
int limit[maxn],lazy[maxn];
inline const void update(int p)
{
	limit[p]=std::max(limit[p<<1],limit[p<<1|1]);
}
inline const void push_col(int p)
{
	if(lazy[p])
	{
		limit[p<<1]+=lazy[p];limit[p<<1|1]+=lazy[p];
		lazy[p<<1]+=lazy[p];lazy[p<<1|1]+=lazy[p];
		lazy[p]=0;
	}
}
inline const int query(int p,int l,int r,int ll,int rr)
{
	if(l>rr||r<ll)return 0;
	if(l>=ll&&r<=rr)return limit[p];
	push_col(p);
	int mid=(l+r)>>1,ans=std::max(query(p<<1,l,mid,ll,rr),query(p<<1|1,mid+1,r,ll,rr));
	return ans;
}
inline const void modify(int p,int l,int r,int ll,int rr,int mark)
{
	if(l>rr||r<ll)return ;
	if(l>=ll&&r<=rr){lazy[p]+=mark;limit[p]+=mark;return ;}
	push_col(p);
	int mid=(l+r)>>1;
	modify(p<<1,l,mid,ll,rr,mark);modify(p<<1|1,mid+1,r,ll,rr,mark);
	update(p);
}
struct team
{
	int start,end,num;
}t[maxn];
inline const bool comp(const team&a,const team&b)
{
	if(a.end<b.end)return true;
	return false;
}
int main()
{
	memset(limit,0,sizeof(limit));
	int k,n,m,ans=0;
	read(k);read(n);read(m);
	for(int i=1;i<=k;i++){read(t[i].start);read(t[i].end);read(t[i].num);}
	std::sort(t+1,t+1+k,comp);
	for(int i=1;i<=k;i++)
	{
		int load=std::min(m-query(1,1,n,t[i].start,t[i].end-1),t[i].num);
		if(load)modify(1,1,n,t[i].start,t[i].end-1,load);
		ans+=load;
	}
	std::cout<<ans;
	return 0;
}

信息

递交者
类型
递交
题目
公交与怪兽 T2
题目数据
下载
语言
C++
递交时间
2017-10-03 20:27:47
评测时间
2017-10-03 20:27:47
评测机
分数
100
总耗时
124ms
峰值内存
3.684 MiB