Wannafly模拟赛2

Contest

时间限制：1秒空间限制：131072K

题目描述

n支队伍一共参加了三场比赛。

一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。

求有多少组(x,y)，使得x自己觉得比y强，y自己也觉得比x强。

(x, y), (y, x)算一组。

输入描述:

第一行一个整数n，表示队伍数； 接下来n行，每行三个整数a[i], b[i], c[i]，分别表示i在第一场、第二场和第三场比赛中的名次；n 最大不超过200000

输出描述:

输出一个整数表示满足条件的(x,y)数；64bit请用lld

示例1

输入

输出

求三维偏序对，在二维的基础上可以进行，这个可以BIT+CDQ啊，但是超时妥妥的

超时代码

#include<stdio.h>

#include<bits/stdc++.h>

using namespace std;

#define maxn 200002

typedef long long ll;

int T,n,tot,id[maxn];

inline char _getchar()

{

    static const int BUFSIZE =  ;

    static char  buf[BUFSIZE] ;

    static char  *psta=buf, *pend=buf ;

    if (psta >= pend){

        psta = buf;

        pend = buf + fread(buf,,BUFSIZE,stdin);

        if (psta >= pend)

            return -;

    }

    return *psta++;

}

inline void read(int &x)

{

    char c;

    int ans=;

    for(c=getchar(); c<''||c>''; c=getchar());

    while(c>=''&&c<='')

        ans=(ans<<)+(ans<<)+(c-''),c=getchar();

    x=ans;

}

struct node

{

    int x,y,z,cnt,ans,id;

} p[maxn];

int cmpx(node a,node b)

{

    if(a.x!=b.x)return a.x<b.x;

    if(a.y!=b.y)return a.y<b.y;

    return a.z<b.z;

}

int cmpy(node a,node b)

{

    if(a.y!=b.y)return a.y<b.y;

    return a.z<b.z;

}

int cmpid(node a,node b)

{

    return a.id<b.id;

}

struct BIT

{

#define lowbit(x) (x&(-x))

    int b[maxn];

    void init()

    {

        memset(b,,sizeof(b));

    }

    void update(int x,int v)

    {

        while(x<=maxn)

        {

            b[x]+=v;

            x+=lowbit(x);

        }

    }

    int query(int x)

    {

        int ans=;

        while(x)

        {

            ans+=b[x];

            x-=lowbit(x);

        }

        return ans;

    }

    void clear(int x)

    {

        while(x<=maxn)

        {

            b[x]=;

            x+=lowbit(x);

        }

    }

} bit;

void CDQ(int l,int r)

{

    if(l==r)

    {

        p[l].ans+=p[l].cnt-;

        return ;

    }

    int mid=(l+r)>>;

    CDQ(l,mid);

    CDQ(mid+,r);

    sort(p+l,p+mid+,cmpy);

    sort(p+mid+,p+r+,cmpy);

    int j=l;

    for(int i=mid+; i<=r; i++)

    {

        for(; j<=mid&&p[j].y<=p[i].y; j++)

            bit.update(p[j].z,p[j].cnt);

        p[i].ans+=bit.query(p[i].z);

    }

    for(int i=l; i<j; i++)bit.update(p[i].z,-p[i].cnt);

    sort(p+l,p+r+,cmpy);

}

int main()

{

    read(n);

    bit.init();

    tot=;

    for(int i=; i<=n; i++)

    {

      read(p[i].x);

      read(p[i].y);

      read(p[i].z);

      p[i].ans=,p[i].id=i;

    }

    sort(p+,p+n+,cmpx);

    for(int i=; i<=n; i++)

    {

        if(i!=&&p[i-].x==p[i].x&&p[i-].y==p[i].y&&p[i-].z==p[i].z)

            p[tot].cnt++;

        else p[++tot]=p[i],p[tot].cnt=;

        id[p[i].id]=tot;

        p[tot].id=tot;

    }

    CDQ(,tot);

    sort(p+,p+tot+,cmpid);

    ll ans=1ll*n*(n-)/;

    for(int i=; i<=n; i++)

    ans-=p[id[i]].ans;

    printf("%lld",ans);

    return ;

}

为什么要CDQ啊，严重拖慢了时间啊，但是扔到CF上是可以AC的，谁让CF的机器跑的快呢

附上AC代码

#include<bits/stdc++.h>

using namespace std;

#define LL long long

const int maxn=;

const int K = ;

struct Point

{

    int x,y,z;

    bool operator < (const Point& rhs) const {return z<rhs.z;}

}p[maxn];

int n,c[maxn/K+][maxn/K+];

inline int lowbit(int x) {return x&(-x);}

int query2D(int qx,int qy)

{

    int ret=;

    while(qy)

    {

        ret+=c[qx][qy];

        qy-=lowbit(qy);

    }

    return ret;

}

int query1D(int qx,int qy)

{

    int ret=;

    while(qx)

    {

        ret+=query2D(qx,qy);

        qx-=lowbit(qx);

    }

    return ret;

}

void modify2D(int px,int py,int v)

{

    while(py<=(n/K))

    {

        c[px][py]+=v;

        py+=lowbit(py);

    }

}

void modify1D(int px,int py,int v)

{

    while(px<=(n/K))

    {

        modify2D(px,py,v);

        px+=lowbit(px);

    }

}

int X[maxn],Y[maxn];

int main()

{

    scanf("%d",&n);

    for(int i=;i<n;i++) scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);

    for(int i=;i<=n;i++) X[i]=n+,Y[i]=n+;

    sort(p,p+n);

    LL ans=(LL)n*(n-)/2LL;

    for(int i=;i<n;i++)

    {

        ans-=query1D(p[i].x/K,p[i].y/K);

        for(int j=p[i].x;j>p[i].x-(p[i].x%K);j--) if(Y[j]<p[i].y) ans--;

        for(int j=p[i].y;j>p[i].y-(p[i].y%K);j--) if(X[j]<=p[i].x-(p[i].x%K)) ans--;

        X[p[i].y]=p[i].x,Y[p[i].x]=p[i].y;

        modify1D((p[i].x+K-)/K,(p[i].y+K-)/K,);

    }

    printf("%lld\n",ans);

}

巴特西

Wannafly模拟赛2

题目描述

输入描述:

输出描述:

输入

输出

最新文章

热门文章