为什么会MLE
  • 板块灌水区
  • 楼主WYZ20030051
  • 当前回复6
  • 已保存回复6
  • 发布时间2024/2/28 19:42
  • 上次更新2024/2/28 21:39:51
查看原帖
为什么会MLE
526895
WYZ20030051楼主2024/2/28 19:42

rt,写法是没问题的,但是不知道是哪个小细节让我一直MLE,别人都跑 2M 左右,而我是 250+M .....

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<cassert>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<cstdlib>
#include<set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define int ll
int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		x=x*10+(ch-'0');
		ch=getchar();
	}
	return x*f;
}
const int MAXN=4e5+10;
int n;
struct node
{
    int s,p,opt;
    bool operator < (const node &x)const
	{
		return s!=x.s?s<x.s:opt<x.opt;
	}
}a[MAXN];
struct tree
{
	int minn,tag;
}tr[MAXN<<2];
void pushup(int k)
{
	tr[k].minn=min(tr[k<<1].minn,tr[k<<1|1].minn);
}
void pushdown(int k)
{
	if(tr[k].tag)
	{
		tr[k<<1].minn+=tr[k].tag;
		tr[k<<1|1].minn+=tr[k].tag;
		tr[k<<1].tag+=tr[k].tag;
		tr[k<<1|1].tag+=tr[k].tag;
		tr[k].tag=0;
	}
}
void modefy(int k,int l,int r,int le,int ri,int v)
{
	if(l<=le && ri<=r)
	{
		tr[k].minn+=v;
		tr[k].tag+=v;
		return ;
	}
	pushdown(k);
	int mid=le+ri>>1;
	if(l<=mid)
		modefy(k<<1,l,r,le,mid,v);
	if(r>mid)
		modefy(k<<1|1,l,r,mid+1,ri,v);
	pushup(k);
}
int query(int k,int l,int r,int le,int ri)
{
	if(l<=le && ri<=r)
		return tr[k].minn;
	pushdown(k);
	int res=1e9;
	int mid=le+ri>>1;
	if(l<=mid)
		res=min(res,query(k<<1,l,r,le,mid));
	if(r>mid)
		res=min(res,query(k<<1|1,l,r,mid+1,ri));
	return res;
}
stack<int>st[MAXN];
signed main()
{
    freopen("reporter.in","r",stdin);
    freopen("reporter.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++)
    {
    	int x=read(),y=read();
    	a[i]=(node){y,x,0};
	}
    for(int i=1;i<=n;i++)
    {
    	int x=read(),y=read();
    	a[i+n]=(node){y,x,1};
	}
	n*=2;
	sort(a+1,a+n+1);
	int ans=n/2;
	for(int i=1;i<=n;i++)
	{
		if(a[i].opt==0)
		{
			st[a[i].p].push(i);
			modefy(1,i,n,1,n,1);
		}
		else
		{
			if(st[a[i].p].empty())
			{
				modefy(1,i,n,1,n,-1);
				continue;
			}
			int x=st[a[i].p].top();
			modefy(1,x,n,1,n,-1);
			if(query(1,1,i,1,n)<0)
			{
				modefy(1,x,n,1,n,1);
				modefy(1,i,n,1,n,-1);
			}
			else
			{
				ans--;
				st[a[i].p].pop();
			}
		}
	}
	printf("%lld\n",ans);
    return 0;
}
2024/2/28 19:42
加载中...