http://acm.uestc.edu.cn/#/problem/show/1584

Washi与Sonochi的约定

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 131072/131072KB (Java/Others)

Submit Status
Sonochi，明年再一起看烟花。——WashioSumi

为了实现和Sonochi的约定，Washi必须要打败眼前强大的怪物。
怪物分布在二维平面上，
某个怪物的rank被定义为x坐标不大于其x坐标，且y坐标不大于其y坐标的怪物的数量。（不含其自身）
Washi要你输出n行，每行一个整数，分别代表rank为0~n−1的怪物数量。

Input

输入第一行为一个正整数n，
接下来n行，第ii行两个整数xi、yi，表示一个怪物的坐标。
保证输入的坐标两两不同。

Output

包含n行，每行一个整数，第ii行的数代表rank为i−1i−1的怪物数量

Sample Input Sample Output
5
1 1
5 1
7 1
3 3
5 5
1
2
1
1

Hint

1≤n≤100000
1≤xi≤100000

1≤yi≤100000

树状数组+排序

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#include <vector>

#include <algorithm>

using namespace std;

typedef long long ll;

int ran[];

int vis[],n;

struct Node

{

    int x,y;

}node[];

bool cmp(const Node &a,const Node &b)

{

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

    else return a.y<b.y;

}

int main()

{

    scanf("%d",&n);

    memset(vis,,sizeof(vis));

    memset(vis,,sizeof(ran));

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

    {

        scanf("%d%d",&node[i].x,&node[i].y);

    }

    sort(node,node+n,cmp);

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

    {

        int ans=;

        for(int j=node[i].y;j;j-=(j&-j))

            ans+=vis[j];

        ran[ans]++;

        for(int j=node[i].y;j<;j+=(j&-j))

            vis[j]++;

    }

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

    {

        printf("%d\n",ran[i]);

    }

    return ;

}

巴特西

UESTC 1584

Washi与Sonochi的约定

Input

Output

最新文章

热门文章