题目的输入是什么意思????
查看原帖
题目的输入是什么意思????
1122449
gmyinSU楼主2024/8/25 09:06

为什么题目要采用这么变态的方式进行输入??还分成好几组,就不能正常的一次输入一组数据进行评分吗 请问一下,题目的输入具体有什么要求,我该做的初始化全部做了(还差离散化),但为什么全部WA??

#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
using namespace std;
long long c,t;
const int N=1e5+5;
typedef long long ll;
ll n,m,k,d;
ll dp[N][2];//the max of the day i which continue from the first day to.,1 is running,0 is no running
struct node{
	ll l,r,sum,ltag;
	node(){
		l=r=sum=ltag=0;
	}
};
node nod[N<<2];
void build(ll id,ll l,ll r){
	nod[id].l=l;
	nod[id].r=r;
	if(l==r){
		nod[id].sum=0;
		return;
	}
	ll mid=(l+r)>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	nod[id].sum=max(nod[id<<1].sum,nod[id<<1|1].sum);
}
void spread(ll i){
	if(nod[i].ltag){
		nod[i<<1].ltag+=nod[i].ltag;
		nod[i<<1|1].ltag+=nod[i].ltag;
		nod[i<<1].sum+=nod[i].ltag;
		nod[i<<1|1].sum+=nod[i].ltag;
		nod[i].ltag=0;
	}
}
void addr(ll i,ll l,ll r,ll k){
	if(l<=nod[i].l && r>=nod[i].r){
		nod[i].sum+=k;
		nod[i].ltag+=k;
		return ;
	}
	spread(i);
	ll mid=(nod[i].l+nod[i].r)>>1;
	if(l<=mid)addr(i<<1,l,r,k);
	if(r>mid)addr(i<<1|1,l,r,k);
	nod[i].sum=max(nod[i<<1].sum,nod[i<<1|1].sum);
}//[l,r] += k
ll fmax(ll i,ll l,ll r){
	if(l>r)return 0;
	if(l<=nod[i].l && r>=nod[i].r){
		return nod[i].sum;
	}
	spread(i);
	ll mid=(nod[i].l+nod[i].r)>>1;
	ll ans=-1;
	if(l<=mid)ans=max(ans,fmax(i<<1,l,r));
	if(r>mid)ans=max(ans,fmax(i<<1|1,l,r));
	return ans;
}
vector<pair<ll,ll> > hx[N]; 
int main(){
	scanf("%lld%lld",&c,&t);
	while(t--){
		scanf("%lld%lld%lld%lld",&n,&m,&k,&d);
		for(int i = 1;i <= n;i++)hx[i].clear();
		for(int i=0;i<=n;i++)dp[i][1]=0,dp[i][0]=0;
		build(1,0,n+1);//WATCH OUT
		ll x,y,v;
		for(int i=1;i<=m;i++){
			scanf("%lld%lld%lld",&x,&y,&v);
			hx[x].push_back(make_pair(x-y+1,v));
		}
		ll ans=0;
		for(int i=1;i<=n;i++){
			for(auto j:hx[i])addr(1,1,j.first,j.second);
			//for(int l=max(1,i-k+1);l<=i;l++){
			dp[i][1]=fmax(1,max(1LL,i-k+1),i)-i*d;
			dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
			ans=max(ans,max(dp[i][1],dp[i][0]));
			addr(1,i+1,i+1,dp[i][0]+i*d);
		}
		printf("%lld\n",ans);
	}
	//for(int i=1;i<=n;i++)cout<<dp[i][1]<<' ';
	return 0;
}

2024/8/25 09:06
加载中...