数据似乎有点水，O(N(N+3))都能过~O~
#include <cstdio>
int n,x[15001];
struct node{
int x,y,ans;
};
node a[15001];
int main(){
//freopen("a.in","r",stdin);

scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].y);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(a[j].x<=a[i].x and a[j].y<=a[i].y) ++a[i].ans;
for(int i=1;i<=n;++i) x[a[i].ans]++;
for(int i=1;i<=n;++i) printf("%d\n",x[i]);
return 0;
}

我短任我短

#include<algorithm>
#include<iostream>
#include<cstdio>
#define BITSIZE (32000)
using namespace std;
struct POINT {int x,y;} pt[15010];
int n;
int bit[32010];
int ans[15010];
void add (int p,int val) {while(p<=BITSIZE) {bit[p]+=val;p+=p&-p;}return;}
int qrys(int p) {int sum=0;while(p>0) {sum+=bit[p];p-=p&-p;}return sum;} 
bool cmp(POINT tma,POINT tmb) {if (tma.x==tmb.x) return tma.y<tmb.y;else return tma.x<tmb.x;}
int main () {
    
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>pt[i].x>>pt[i].y;
    sort(pt+1,pt+n+1,cmp);
    for(int i=1;i<=n;i++) {
        ans[qrys(pt[i].y)]++;
        add(pt[i].y,1); 
    }
    for(int i=0;i<n;i++) cout<<ans[i]<<endl;
    return 0;
    
}

用了个SBT，看了题解原来树状数组就行……

#include <cstdio>
#include <cstring>
#include <algorithm>

#define rep(id,a,b) for(int id=(a);id<(b);++id)

using namespace std;

struct Node
{
int v;
int s[2];
Node* c[2];

Node (int _v) : v (_v)
{
s[0] = s[1] = 0;
c[0] = c[1] = 0;
}

Node* rot (int d)
{
Node* tp = c[d ^ 1];
c[d ^ 1] = tp->c[d];
tp->c[d] = this;
s[d ^ 1] = tp->s[d];
tp->s[d] += (1 + s[d]);
return tp;
}
};

struct SBT
{
Node* root;

SBT() : root (0) {}

void insert (int v)
{
root = _insert (v, root);
}
Node* _insert (int v, Node* cur)
{
if (!cur) return new Node (v);
int f = (v < cur->v) ? 0 : 1;
cur->c[f] = _insert (v, cur->c[f]);
++cur->s[f];
if (cur->c[f]->s[f] > cur->s[f ^ 1]) return cur->rot (f ^ 1);
else if (cur->c[f]->s[f ^ 1] > cur->s[f ^ 1])
{
cur->c[f] = cur->c[f]->rot (f);
return cur->rot (f ^ 1);
}
else return cur;
}

int ask (int v)
{
int res (0);
Node* cur = root;
while (cur)
{
if (v < cur->v) cur = cur->c[0];
else
{
res += (cur->s[0] + 1);
cur = cur->c[1];
}
}
return res;
}
};

struct Point
{
int x, y;
bool operator < (const Point& ot) const
{
return x < ot.x || (x == ot.x && y < ot.y);
}
bool operator == (const Point& ot) const
{
return x == ot.x && y == ot.y;
}
};

const int maxN = 15000 + 5;

int N;
Point pt[maxN];
int ans[maxN] = {0};

void input()
{
scanf ("%d", &N);
rep (i, 0, N) scanf ("%d%d", &pt[i].x, &pt[i].y);
}

void solve()
{
sort (pt, pt + N);
SBT sbt;
int left (0), right (0);
while (left < N)
{
while (pt[right + 1] == pt[left]) ++right;
int tp = sbt.ask (pt[left].y);
ans[tp + right - left] += (right - left + 1);
rep (i, left, right + 1) sbt.insert (pt[left].y);
left = right = right + 1;
}
rep (i, 0, N) printf ("%d\n", ans[i]);
}

int main()
{
input();
solve();
return 0;
}

朴素的算法：
var n,i,j,ans:longint;
s:array[0..15000]of longint;
x,y:array[1..15000]of longint;
begin
readln(n);
for i:=1 to n do
readln(x[i],y[i]);
for i:=1 to n do
begin
ans:=0;
for j:=1 to n do
begin
if (i<>j)and(x[i]>=x[j])and(y[i]>=y[j]) then inc(ans);
end;
inc(s[ans]);
end;
for i:=0 to n-1 do
writeln(s[i]);
end.

#include"iostream"
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=32005;
struct node{
int x,y;
};
node pos[N];
int n;
int ans[N];
ll res;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>pos[i].x>>pos[i].y;
for(int i=0;i<n;i++)
{
res=0;
for(int j=0;j<n;j++)
{
if(pos[j].x<=pos[i].x&&pos[j].y<=pos[i].y&&i!=j)
res++;
}
ans[res]++;
}
for(int i=0;i<n;i++)
cout<<ans[i]<<endl;
return 0;
}

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int x[5005],y[5005];
int n,k;
int a[5005];
int main (){
freopen ("trench.in","r",stdin);
freopen ("trench.out","w",stdout);
scanf ("%d",&n);

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

k=0;
for (int j=0;j<n;j++)

if (i!=j && x[i]>=x[j] && y[i]>=y[j])
k++;

a[k]++;

}
for (int i=0;i<n;i++)
printf ("%d\n",a[i]);

return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,tot[150001],toto,sum[150001];
struct hao{
int x,y;
};
hao a[150001];
int comp(const hao & a,const hao & b)
{
if(a.y<b.y) return 1;
if(a.y>b.y) return 0;
if(a.x<b.x) return 1;
if(a.x>b.x) return 0;
return 0;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+n+1,comp);
for(int i=1;i<=n;i++)
{
sum[a[i].x]++;
for(int j=1;j<=a[i].x;j++)
toto+=sum[j];
tot[toto]++;
toto=0;
}
for(int i=1;i<=n;i++)
cout<<tot[i]<<endl;
}

#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
double x[n];
double y[n];
for(int i=0;i<n;i++)
{
cin>>x[i];
cin>>y[i];
}
int count[n];
for(int i=0;i<n;i++)
{
count[i]=0;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if((x[j]<=x[i])&&(y[j]<=y[i])&&((x[i]!=x[j])||(y[i]!=y[j]))) count[i]++;
}
}
int b[n];
for(int i=0;i<n;i++)
{
b[i]=0;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(count[j]==i)
b[i]++;
}
}
for(int i=0;i<n;i++)
{
cout<<b[i]<<endl;
}
return 0;
}
水题

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

struct Pointnode
{
int x,y;
inline bool operator == (Pointnode b)
{
return x==b.x&&y==b.y;
}
}Point[15000];

int N,M,ans[15000],tree[32000];

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

void update(int pos,int delta)
{
for(;pos<=M;pos+=lowbit(pos))
tree[pos]+=delta;
}

int query(int pos)
{
int ans=0;
for(;pos;pos-=lowbit(pos))
ans+=tree[pos];
return ans;
}

bool cmp(Pointnode a,Pointnode b)
{
return a.x==b.x?a.y<b.y:a.x<b.x;
}

int main()
{
scanf("%d",&N);
for(int i=0;i<N;i++)
{
scanf("%d%d",&Point[i].x,&Point[i].y);
M=max(M,Point[i].y);
}
sort(Point,Point+N,cmp);
memset(ans,0,sizeof(ans));
memset(tree,0,sizeof(tree));
for(int i=0,count;i<N;i++)
{
for(count=1;Point[i]==Point[i+1]&&i+1<N;i++,count++);
ans[query(Point[i].y)+count-1]+=count;
update(Point[i].y,count);
}
for(int i=0;i<N;i++)
printf("%d\n",ans[i]);
return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

struct Pointnode
{
int x,y;
inline bool operator == (Pointnode b)
{
return x==b.x&&y==b.y;
}
}Point[15000];

int N,M,ans[15000],tree[32000];

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

void update(int pos,int delta)
{
for(;pos<=M;pos+=lowbit(pos))
tree[pos]+=delta;
}

int query(int pos)
{
int ans=0;
for(;pos;pos-=lowbit(pos))
ans+=tree[pos];
return ans;
}

bool cmp(Pointnode a,Pointnode b)
{
return a.x==b.x?a.y<b.y:a.x<b.x;
}

int main()
{
scanf("%d",&N);
for(int i=0;i<N;i++)
{
scanf("%d%d",&Point[i].x,&Point[i].y);
M=max(M,Point[i].y);
}
sort(Point,Point+N,cmp);
memset(ans,0,sizeof(ans));
memset(tree,0,sizeof(tree));
for(int i=0,count;i<N;i++)
{
for(count=1;Point[i]==Point[i+1]&&i+1<N;i++,count++);
ans[query(Point[i].y)+count-1]+=count;
update(Point[i].y,count);
}
for(int i=0;i<N;i++)
printf("%d\n",ans[i]);
return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 784 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 780 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 788 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 780 KiB, score = 10
测试数据 #4: Accepted, time = 109 ms, mem = 784 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 788 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 784 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 788 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 784 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 784 KiB, score = 10
Accepted, time = 139 ms, mem = 788 KiB, score = 100
代码
var
i,j,k,n,m,tot:longint;
a:array[0..15005] of longint;
x,y:array[1..15005] of longint;
procedure qsort(l,r:longint);
var
i,j,t,mid,m2:longint;
begin
i:=l; j:=r;
m2:=y[(l+r) shr 1];
mid:=x[(l+r) shr 1];
while i<=j do
begin
while (x[i]<mid) or ((x[i]=mid) and (y[i]<m2)) do
inc(i);
while (x[j]>mid) or ((x[j]=mid) and (y[j]>m2)) do
dec(j);
if i<=j then
begin
t:=x[i];
x[i]:=x[j];
x[j]:=t;
t:=y[i];
y[i]:=y[j];
y[j]:=t;
inc(i);
dec(j);
end;
end;
if i<r then qsort(i,r);
if j>l then qsort(l,j);
end;
begin
readln(n);
for i:=1 to n do
readln(x[i],y[i]);
qsort(1,n);
fillchar(a,sizeof(a),0);
for i:=1 to n do
begin
tot:=0;
for j:=1 to i-1 do
if y[i]>=y[j] then
inc(tot);
inc(a[tot]);
end;
for i:=0 to n-1 do
writeln(a[i]);
end.

#include<iostream>
using namespace std;
int a[15000][3];
main()
{
int n,sum,i,j;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i][0]>>a[i][1];
a[i][2]=0;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(i==j)
continue;
if(a[j][0]<=a[i][0]&&a[j][1]<=a[i][1])
a[i][2]++;
}
for(i=0;i<n;i++)
{
sum=0;
for(j=0;j<n;j++)
if(a[j][2]==i)
sum++;
cout<<sum<<endl;
}
}

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 420 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 420 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 420 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 420 KiB, score = 10
测试数据 #4: Accepted, time = 156 ms, mem = 416 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 416 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 416 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 416 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 416 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 416 KiB, score = 10
Accepted, time = 171 ms, mem = 420 KiB, score = 100

#include <stdio.h>
int arr[15000][3];
int main(){
int num,count,i,k;
scanf("%d",&num);
for(i=0;i<num;i++){
scanf("%d %d",&arr[i][0],&arr[i][1]);
arr[i][2]=0;
}
for(i=0;i<num;i++){
for(k=0;k<num;k++){
if(i==k)
continue;
if(arr[k][0]<=arr[i][0] && arr[k][1]<=arr[i][1])
arr[i][2]++;
}
}
for(i=0;i<num;i++){
count=0;
for(k=0;k<num;k++)
if(arr[k][2]==i)
count++;
printf("%d\n",count);
}
return 0;
}

完全不用优化

测试数据 #0: Accepted, time = 15 ms, mem = 896 KiB, score = 10

测试数据 #1: Accepted, time = 15 ms, mem = 896 KiB, score = 10

测试数据 #2: Accepted, time = 31 ms, mem = 896 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 896 KiB, score = 10

测试数据 #4: Accepted, time = 265 ms, mem = 900 KiB, score = 10

测试数据 #5: Accepted, time = 0 ms, mem = 896 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 900 KiB, score = 10

测试数据 #7: Accepted, time = 0 ms, mem = 896 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 896 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 900 KiB, score = 10

Accepted, time = 371 ms, mem = 900 KiB, score = 100

代码

var
a,b,f,c:array[1..10000]of longint;
n,i,j:longint;
begin
read(n);
for i:=1 to n do read(a[i],b[i]);
for i:=1 to n do for j:=1 to n do
if (i<>j)and(a[i]>=a[j])and(b[i]>=b[j]) then inc(f[i]);
for i:=1 to n do inc(c[f[i]+1]);
for i:=1 to n do writeln(c[i]);
end.