WA #25 求条
查看原帖
WA #25 求条
703022
wuyixiang楼主2024/10/10 10:51
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[800005],a2[800005],a3[800005],a4[800005],L[800005],c,d,e,ans,dl[1600005],Cnt;
int tot;
struct node
{
    int ze,ye,len,xl,yl,id,add;
}tr[10000005];
struct tmp
{
    int xq,xz,yz,ad; 
}X[400005];
bool cmp(tmp f,tmp ff){
	return f.yz < ff.yz;
}
void pushup(int p)
{
	//cout << p << " " << tr[p * 2 + 1].len << " " << tr[p * 2 + 2].len << '\n';
	if(tr[p * 2 + 1].len >= tr[p * 2 + 2].len)tr[p].id = tr[p * 2 + 1].id;
	else tr[p].id = tr[p * 2 + 2].id;
	tr[p].len = max(tr[p * 2 + 1].len,tr[p * 2 + 2].len);
}
void build(int p,int x,int y)
{
    tr[p] = {L[x],L[y],0,x,y,0,0};
    if(x == y)
    {
    	tr[p].id = L[x];
    	return ;
	}
    build(p * 2 + 1,x,(x + y) >> 1);
    build(p * 2 + 2,((x + y) >> 1) + 1,y);
    pushup(p);
}
void pushdown(int x)
{
	if(tr[x].add != 0)
	{
		tr[x * 2 + 1].add += tr[x].add;
		tr[x * 2 + 2].add += tr[x].add;
		tr[x * 2 + 1].len += tr[x].add;
		tr[x * 2 + 2].len += tr[x].add;
		tr[x].add = 0;
	}
}
void jia(int x,int u,int v,int k)
{
	pushdown(x);
	if(L[u] <= tr[x].ze && tr[x].ye <= L[v])
	{
		tr[x].len += k,tr[x].add += k;
		return ;
	}
	int mid = (tr[x].xl + tr[x].yl) >> 1;
	if(u <= mid)jia(x * 2 + 1,u,min(v,mid),k);
	if(v > mid)jia(x * 2 + 2,max(u,mid + 1),v,k);
	pushup(x);
}
int ansl,ansr = 1;
signed main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++)
	{
		cin >> a[i] >> a2[i];
		if(a2[i] - a[i] == 1)
		{
			n --,i --;
			continue ;
		}
		if(a2[i] < 1e9)X[++Cnt] = {a[i] + 1,a2[i] - 1,a2[i] + 1,1};
		if(a2[i] < 1e9)X[++Cnt] = {a[i] + 1,a2[i] - 1,1000000000,-1};
		if(a[i] > 0)X[++Cnt] = {0,a[i] - 1,a[i] + 1,1};
		if(a[i] > 0)X[++Cnt] = {0,a[i] - 1,a2[i] - 1,-1};
		L[i] = a[i] + 1;
		L[i + n] = a2[i] - 1;
		L[i + 2 * n] = 0;
		L[i + 3 * n] = a[i] - 1;
	}
	if(!n)
	{
		cout << "0 1";
		return 0;
	}
	n *= 4;
	sort(X + 1,X + n + 1,cmp);
	sort(L + 1,L + n + 1);
	int tot = unique(L + 1,L + n + 1) - L - 1;
    build(0,1,tot); 
    for(int i = 1;i < Cnt;i ++)
    {
        int l = lower_bound(L + 1,L + tot + 1,X[i].xq) - L;
        int r = lower_bound(L + 1,L + tot + 1,X[i].xz) - L;
        jia(0,l,r,X[i].ad);
        if(tr[0].len > ans)
        	ans = tr[0].len,ansl = tr[0].id,ansr = X[i].yz;
        else if(tr[0].len == ans && tr[0].id < ansl)
        	ansl = tr[0].id,ansr = X[i].yz;
    }
    cout << ansl << " " << ansr;
}
2024/10/10 10:51
加载中...