蒟蒻初学,莫名MLE,求助大佬
查看原帖
蒟蒻初学,莫名MLE,求助大佬
114288
lijia123楼主2021/8/8 21:48

输入应该没问题啊

#include<bits/stdc++.h>
#define len 200000
using namespace std;
struct sp{
	int l,r,d;
}tree[400011];
long long n,m,cnt=0,q=0,ans=0,an=0;
inline void build(int &p,int l,int r,int k)
 {
 	if(!p)  p=++cnt;
 	if(l==r)
 	{
 		tree[p].d++;
 		return;
 	}
 	int mid=l+r>>1;
 	if(k<=mid) build(tree[p].l,l,mid,k);
 	else build(tree[p].r,mid+1,r,k);
 	tree[p].d=tree[tree[p].l].d+tree[tree[p].r].d;
 }
 inline int cha(int p,int l,int r,int x,int y)
 {
 	if(!p) return 0;
 	if(x<l&&y>r) return tree[p].d;
 	int mid=(l+r)>>1,res=0;
 	if(x<=mid)res+=cha(tree[p].l,l,mid,x,y);
 	if(y>mid) res+=cha(tree[p].r,mid+1,r,x,y);
 	return res;
 }	
 inline void shan(int p,int l,int r,int x,int y)
 {
 	if(!p) return;
 	if(l==r)
 		tree[p].d=0;
 	int mid=(l+r)>>1;
 	if(x<=mid&&tree[tree[p].l].d) shan(tree[p].l,l,mid,x,y);
 	if(y>mid&&tree[tree[p].r].d) shan(tree[p].r,mid+1,r,x,y);
 	tree[p].d=tree[tree[p].l].d+tree[tree[p].r].d;
 }
 inline int query(int p,int l,int r,int k)
 {
 	if(!p) return 0;
 	if(l==r&&tree[p].d) return l;
 	int mid=(l+r)>>1;
 	if(k<=tree[tree[p].r].d) query(tree[p].r,mid+1,r,k);
 	else if(k>tree[tree[p].r].d) query(tree[p].l,l,mid,k-tree[tree[p].r].d);
 }
int main()
{
	int a2;	int root=0,m1;
	char a1[10];
	cin>>n>>m;
	m1=m;
	for(int i=1;i<=n;++i)
	{
	
		scanf("%s",a1);
		scanf("%d",&a2);
		if(a1[0]=='I'&&a2>=m1)
			build(root,1,1e+9,a2-q+len),an++;
		if(a1[0]=='A')
			m-=a2,q+=a2;
		if(a1[0]=='S')
		{
			m+=a2;q-=a2;
			int k1=cha(root,1,1e+9,1,len+m);	
			if(m>1&&k1>0)
			ans+=k1,shan(root,1,1e+9,1,len+m);
		}
		if(a1[0]=='F')
		{
			int k1=query(root,1,1e+9,a2)-len+q;
			if(k1<0||a2>an-ans) {
				cout<<"-1"<<endl;
				continue;
			}
			cout<<k1<<endl;
		}
	}
	cout<<ans<<endl;
} 
2021/8/8 21:48
加载中...