/ Randle /

记录详情

Wrong Answer


  
# 状态 耗时 内存占用
#1 Wrong Answer 成绩取消 0ms 0 Bytes

代码

#include<bits/stdc++.h> 
using namespace std;
int tree[200100],limit[200100],lazy[200100];
struct side
{
	int be,ed,wei;
}s[100010];
int read()
{
	int num=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')
	{
		num*=10;
		num+=c-'0';
		c=getchar(); 
	}
	return num;
}
bool cmp(const side &a,const side &b)//以结束点为关键字排序 
{
	return a.ed<b.ed;
}
void update(int x)//维护最大值 
{
	limit[x]=max(limit[x<<1],limit[x<<1|1]);
} 
void push_col(int x)//推动懒惰标记 
{
	if(lazy[x])
	{
		lazy[x<<1]+=lazy[x];lazy[x<<1|1]+=lazy[x];
		limit[x<<1]+=lazy[x];limit[x<<1|1]+=lazy[x];
		lazy[x]=0;
	}
}
int query(int l,int r,int p,int ll,int rr)//查询ll到rr的最大值 
{
	if(l>rr||r<ll)return 0;//不在区间内
	if(l>=ll&&r<=rr){return limit[p];}//在区间内直接返回最值 
	push_col(p);//推懒惰标记
	int mid=(l+r)>>1;
	int ans=max(query(l,mid,p<<1,ll,rr),query(mid+1,r,p<<1|1,ll,rr));
	return ans;
}
void modify(int l,int r,int p,int ll,int rr,int load)
{
	if(l>rr||r<ll)return;
	if(l>=ll&&r<=rr)
	{
		limit[p]+=load;
		lazy[p]+=load;
		return;
	}
	push_col(p);
	int mid=(l+r)>>1;
	modify(l,mid,p<<1,ll,rr,load);
	modify(mid+1,r,p<<1|1,ll,rr,load);
	update(p);
}
int main()
{
	//freopen("测试数据.txt","r",stdin);
	int k,n,m;
	scanf("%d%d%d",&k,&n,&m);
	for(int i=1;i<=k;i++)
	{s[i].be=read();s[i].ed=read();s[i].wei=read();}	
	sort(s+1,s+k+1,cmp);
	int ans=0;
	for(int i=1;i<=k;i++)
	{
		int used=query(1,n,1,s[i].be,s[i].ed-1);//查询与本段重合的已经装载的人数 
		int load=min(m-used,s[i].wei);//能装下的人数 本队总人数
		ans+=load;//下车 
	//	std::cout<<load<<' ';
		modify(1,n,1,s[i].be,s[i].ed-1,load);//将装载人数加入
	}
	cout<<ans;
	return 0;	
}

信息

递交者
类型
递交
题目
公交与怪兽 T2
题目数据
下载
语言
C++
递交时间
2017-10-03 20:12:00
评测时间
2017-11-02 15:36:14
评测机
分数
0
总耗时
0ms
峰值内存
0 Bytes