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