NOIP2012借教室代码求调
  • 板块学术版
  • 楼主AladV
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/5/16 20:15
  • 上次更新2023/11/4 23:09:59
查看原帖
NOIP2012借教室代码求调
517444
AladV楼主2021/5/16 20:15

rt,目前就是WA on 19,其他都对了,求好心大佬指出错误。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
struct SegTree
{
   int l,r,minn,tag;
}t[N<<2];
int n,k,a[N];
int read()
{
   int x=0,f=1;
   char c=getchar();
   while(c<'0'||c>'9')
   {
   	if(c=='-') f=-1;
   	c=getchar();
   }
   while(c>='0'&&c<='9')
   {
   	x=(x<<1)+(x<<3)+(c^48);
   	c=getchar();
   }
   return x*f;
}
void BuildTree(int p,int l,int r)
{
   t[p].l=l,t[p].r=r;
   if(l==r){t[p].minn=a[l];return ;}
   int mid=(l+r)>>1;
   BuildTree(p<<1,l,mid);
   BuildTree(p<<1|1,mid+1,r);
   t[p].minn=min(t[p<<1].minn,t[p<<1|1].minn);
}
void pushdown(int p)
{
   if(t[p].tag)
   {
   	t[p<<1].tag+=t[p].tag;
   	t[p<<1].minn+=t[p].tag;
   	t[p<<1|1].tag+=t[p].tag;
   	t[p<<1|1].minn+=t[p].tag;
   	t[p].tag=0;
   }
}
int Query(int p,int l,int r)
{
   if(l<=t[p].l && t[p].r<=r)
   {
   	return t[p].minn;
   }
   int mid=(t[p].l+t[p].r)>>1;
   pushdown(p);
   int res=0x3f3f3f3f;
   if(l<=mid) res=min(res,Query(p<<1,l,r));
   if(mid<r) res=min(res,Query(p<<1|1,l,r));
   return res;
}
void Modify(int p,int l,int r,int d)
{
   if(l<=t[p].l && t[p].r<=r)
   {
   	t[p].tag+=d;
   	t[p].minn+=d;
   	return ;
   }
   int mid=(t[p].l+t[p].r)>>1;
   pushdown(p);
   if(l<=mid) Modify(p<<1,l,r,d);
   if(mid<r) Modify(p<<1|1,l,r,d);
   // return res;
   t[p].minn=min(t[p<<1].minn,t[p<<1|1].minn);
}
signed main()
{
   // freopen("P1083_19.in","r",stdin);
   n=read(),k=read();
   for(int i=1;i<=n;i++) a[i]=read();
   BuildTree(1,1,n);
   int cases=0;
   while(k--)
   {
   	cases++;
   	// cout<<t[1].l<<" "<<t[1].r<<" "<<t[1].minn<<endl;
   	int d=read(),l=read(),r=read();
   	int minans=Query(1,l,r);
   	if(minans>=d) Modify(1,l,r,-d);
   	else break;
   }
   // cout<<-1<<endl;
   if(cases) puts("-1"),cout<<cases<<endl,exit(0);
   else puts("0");
   return 0;
}
2021/5/16 20:15
加载中...