/ Randle /

记录详情

Wrong Answer


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

代码

#include<bits/stdc++.h> 
using namespace std;
int tree[200100];
int maxx[200100];
int 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)
{
	maxx[x] = max(maxx[x << 1],maxx[x << 1 | 1]);
} 
void push_col(int x)
{
	if(lazy[x])
	{
		lazy[x<<1]+=lazy[x];lazy[x<<1|1]+=lazy[x];
		maxx[x<<1]+=lazy[x];maxx[x<<1|1]+=lazy[x];
		lazy[x]=0;
	}
}
int ask(int l,int r,int p,int ll,int rr)
{
	if(l > rr || r < ll)return 0;
	if(l >= ll && r <= rr)
	{
		return maxx[p];
	}
	push_col(p);
	int mid = (l + r) >> 1;
	int ans = max(ask(l,mid,p << 1,ll,rr),ask(mid + 1,r,p << 1 | 1,ll,rr));
	update(p);
	return ans;
}
void modify(int l,int r,int p,int ll,int rr,int kk)
{
	if(l>rr|| r < ll)return;
	if(l>=ll&& r <= rr)
	{
		maxx[p] += kk;
		lazy[p] += kk;
		return;
	}
	push_col(p);
	int mid=(l+r)>>1;
	modify(l,mid,p<<1,ll,rr,kk);
	modify(mid+1,r,p<<1|1,ll,rr,kk);
	update(p);
}
int main()
{
	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 op=ask(1,n,1,s[i].be,s[i].ed-1);
		int zz=min(m-op,s[i].wei);
		ans+=zz;
		modify(1,n,1,s[i].be,s[i].ed-1,zz);
	}
	cout<<ans;
	return 0;	
}

信息

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