第5个点WA,求调
  • 板块CF12D Ball
  • 楼主hzoi_Shadow
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/5/21 11:43
  • 上次更新2023/10/23 15:09:07
查看原帖
第5个点WA,求调
848964
hzoi_Shadow楼主2023/5/21 11:43
#include<bits/stdc++.h>
using namespace std;
struct student
{
    int b,i,r,id;
}a[2000002];
int c[2000002];
bool cmp1(student a,student b)
{
    return a.b<b.b;
}
bool cmp2(student a,student b)
{
    return a.i>b.i;
}
int lowbit(int x)
{
    return (x&(-x));
}
int getsum(int x)
{
	int ans=0,i;
	for(i=x;i>0;i-=lowbit(i))
	{
		ans=max(ans,c[i]);
	}
	return ans;
} 
void add(int n,int x,int key)
{
	int i;
	for(i=x;i<=n;i+=lowbit(i))
	{
		c[i]=max(c[i],key);
	}
} 
int main()
{
    int n,i,j,num=1,ans=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i].b;
    }
    for(i=1;i<=n;i++)
    {
        cin>>a[i].i;
    }
    for(i=1;i<=n;i++)
    {
        cin>>a[i].r;
    }
    sort(a+1,a+1+n,cmp1);
    a[1].id=1;
    for(i=2;i<=n;i++)
    {
        if(a[i].b==a[i-1].b)
        {
            a[i].id=num;
        }
        else
        {
            num++;
            a[i].id=num;
        }
    }
    sort(a+1,a+1+n,cmp2);
    i=1;
    while(i<=n)
    {
        for(j=i;j<=n;j++)
        {
            if(a[i].i==a[j].i)
            {
                if(getsum(a[j].id+1)>a[j].r)
                {
                    ans++;
                }
            }
            else
            {
                break;
            }
        }
        for(j=i;j<=n;j++)
        {
            if(a[i].i==a[j].i)
            {
                add(num,a[j].id,a[j].r);
            }
            else
            {
                break;
            }
        }
        i=j;
    }
    cout<<ans;
	return 0;
}
2023/5/21 11:43
加载中...