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;
}