记录信息
评测状态 Accepted
题目 P1066 弱弱的战壕
递交时间 2015-10-30 15:23:24
代码语言 C++
评测机 VijosEx
消耗时间 141 ms
消耗内存 772 KiB
评测时间 2015-10-30 15:23:27
评测结果
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 768 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 768 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 768 KiB, score = 10
测试数据 #4: Accepted, time = 62 ms, mem = 764 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 764 KiB, score = 10
测试数据 #6: Accepted, time = 3 ms, mem = 764 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 772 KiB, score = 10
测试数据 #8: Accepted, time = 1 ms, mem = 764 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 764 KiB, score = 10
Accepted, time = 141 ms, mem = 772 KiB, score = 100
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct Ta{
int x,y,w;
};
Ta a[15005];
int num[15005],n,m;
bool comp(const Ta l,const Ta r)
{
if(l.x<=r.x&&l.y<=r.y)
return true;
else
if(l.x<r.x) return true;
return false;
}
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);
a[1].w=0;
for(int i=2;i<=n;i++)
{
int j=i-1;
while(j>0)
{
if(a[j].x<=a[i].x&&a[j].y<=a[i].y)
a[i].w++;
j--;
}
}
for(int i=1;i<=n;i++)
num[a[i].w]++;
for(int i=0;i<n;i++)
printf("%d\n",num[i]);
return 0;
}

再次被数据范围坑了......
#include <cstdio>
#include <cstdlib>
#include <algorithm>

using namespace std;

struct point {
int x, y;
} _p[15005];
struct Node {
int l, mid, r;
int val;
} q[75000];
struct in {
int x, y, t;
} p[15005];
int n;
int ans[15005];

bool cmp(point a, point b) {
if (a.x < b.x)
return true;
if (a.x > b.x)
return false;
if (a.y < b.y)
return true;
else
return false;
}
void initialization(int node, int l, int r) {
q[node].l = l;
q[node].mid = (l + r) / 2;
q[node].r = r;
if (l == r)
return ;
initialization(node * 2, l, q[node].mid);
initialization(node * 2 + 1, q[node].mid + 1, r);
}
void add(int node, int lr, int val) {
if (q[node].r == lr && q[node].l == lr) {

q[node].val += val;
return ;
}
if (lr <= q[node].mid) {
add(node * 2, lr, val);
q[node].val += val;
}
else {
add(node * 2 + 1, lr, val);
q[node].val += val;
}
}
int sum(int node, int l, int r) {
if (q[node].l == l && q[node].r == r) {
return q[node].val;
}
if (r <= q[node].mid)
return sum(node * 2, l, r);
if (l <= q[node].mid && q[node].mid < r)
return (sum(node * 2, l, q[node].mid) + sum(node * 2 + 1, q[node].mid + 1, r));
if (q[node].mid <= l)
return (sum(node * 2 + 1, l, r));
}
int main(int argc, const char *argv[]) {
scanf("%d", &n);
int maxy = 1;
for (int i = 1; i <= n; ++i) {
scanf("%d %d", &_p[i].x, &_p[i].y);
if (_p[i].y > maxy)
maxy = _p[i].y;
}
sort(_p + 1, _p + n + 1, cmp);
initialization(1, 1, maxy);
int tot = 0;
for (int i = 1; i <= n; ++i) {
if (_p[i].x != _p[i - 1].x || _p[i].y != _p[i - 1].y) {
p[++tot].x = _p[i].x;
p[tot].y = _p[i].y;
p[tot].t = 1;
}
else
++p[tot].t;
}
for (int i = 1; i <= tot; ++i) {
add(1, p[i].y, p[i].t);
ans[sum(1, 1, p[i].y) - 1] += p[i].t;
}
for (int i = 0; i < n; ++i)
printf("%d\n", ans[i]);
return 0;
}

可以先Ω（nlogn）排序后离散化然后用O（maxx*maxy）维护二维前缀和。也可以用树状数组维护

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=15000+10;

int ans[MAXN];

struct NODE{
int x,y ;

}d[MAXN];

int main()
{
int n,bri;
scanf("%d",&n);
for(int i=1; i<=n; i++)
scanf("%d%d",&d[i].x,&d[i].y);
for(int i=1; i<=n; i++){
bri = 0;
for(int j=1; j<=n; j++)
if(i != j && d[i].x >= d[j].x && d[i].y >= d[j].y)
bri++;
ans[bri]++;
}
for(int i=0; i<n; i++)
printf("%d\n",ans[i]);
return 0;
}
暴力。。。

暴搜的举手...

program exam;
var i,j,m,n,k,l,o:longint;
x,y,a,c,h:array[0..100000] of longint;
begin
readln(n);
for i:=1 to n do
readln(x[i],y[i]);
for i:=1 to n do
begin
k:=0;
for j:=1 to n do
if (x[i]>=x[j]) and (y[i]>=y[j]) then inc(k);
inc(o);
h[o]:=k-1;
end;
for i:=1 to o do
for j:=0 to n-1 do
if h[i]=j then inc(c[j]);
for i:=0 to n-1 do
writeln(c[i]);
end.

记录信息
评测状态 Accepted
题目 P1066 弱弱的战壕
递交时间 2015-06-30 11:24:20
代码语言 C++
评测机 VijosEx
消耗时间 231 ms
消耗内存 592 KiB
评测时间 2015-06-30 11:24:28

评测结果
编译成功

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

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

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

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

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

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

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

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

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

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

Accepted, time = 231 ms, mem = 592 KiB, score = 100

代码
#include <iostream>
#include <stdio.h>

using namespace std;

int i , j;
int n , m;
int k , l;
int a[20000][3];
int f[20000];

int main ()
{
scanf( "%d" , &n );
for( i = 1 ; i <= n ; i++ )
scanf( "%d %d" , &a[i][1] , &a[i][2] );
for( i = 1 ; i <= n ; i++ )
{
k = 0;
for( j = 1 ; j <= n ; j++ )
if( i != j && a[i][1] >= a[j][1] && a[i][2] >= a[j][2] )
k++;
f[k]++;
}
for( i = 0 ; i < n ; i++ )
printf( "%d\n" , f[i] );
return 0;
}

ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC
ACACACACACACACACACACACACACACACAC

排序只管了x。。没管y
结果崩了 错了好长时间

这都能ac，我被吓了

为何用的树状数组要29ms....
###
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 15000+10;
const int MAXS = 32000+10;

int n, ans[MAXN], c[MAXS], cj;

struct Point{
int x, y, p;

Point(){
x = y = p = 0;
}

inline void init(int egP){
scanf("%d %d", &x, &y);
p = egP, cj = max(cj, y);
}

friend bool operator < (const Point& A, const Point& B){
return A.x<B.x || (A.x==B.x && A.y<B.y);
}
}p[MAXN];

struct BIT{
int n;

BIT(){
memset(c, 0, sizeof(c));
}

inline void add(int x, int p){
while (p<=n)
c[p] += x, p += p&(-p);
}

inline int sum(int p){
int ret = 0;
while (p)
ret += c[p], p -= p&(-p);
return ret;
}
}tree;

int main(){
memset(ans, 0, sizeof(ans));
scanf("%d", &n), cj = 0;
for (int i=0; i<n; i++)
p[i].init(i);

sort(p, p+n);

tree.n = cj;
for (int i=0; i<n; i++)
ans[tree.sum(p[i].y)] ++,
tree.add(1, p[i].y);

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

评测结果
编译成功

Free Pascal Compiler version 2.6.2 [2013/02/12] for i386
Copyright (c) 1993-2012 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling foo.pas
foo.pas(37,13) Warning: Variable "a" does not seem to be initialized
Linking foo.exe
41 lines compiled, 0.1 sec , 28448 bytes code, 1628 bytes data
1 warning(s) issued
测试数据 #0: Accepted, time = 0 ms, mem = 908 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 916 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 912 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 912 KiB, score = 10
测试数据 #4: Accepted, time = 62 ms, mem = 912 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 908 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 908 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 908 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 912 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 912 KiB, score = 10
Accepted, time = 107 ms, mem = 916 KiB, score = 100
代码
Var a:Array[0..15000] of Longint;
map:Array[0..15005,1..2] of Longint;
i,j,t,n:Longint;
Procedure qsort(l,r:Longint);
Var i,j,mid1,mid2:Longint;
Begin
i:=l;
j:=r;
mid1:=map[(l+r) Div 2,1];
mid2:=map[(l+r) Div 2,2];
Repeat
While (map[i,1]>mid1) Or ((map[i,1]=mid1) And (map[i,2]>mid2)) Do Inc(i);
While (map[j,1]<mid1) Or ((map[j,1]=mid1) And (map[j,2]<mid2)) Do Dec(j);
If (i<=j) Then
Begin
map[0]:=map[i];
map[i]:=map[j];
map[j]:=map[0];
Inc(i);
Dec(j);
End;
Until i>j;
If (j>l) Then qsort(l,j);
If (i<r) Then qsort(i,r);
End;
Begin
Readln(n);
For i:=1 To n Do
Readln(map[i,1],map[i,2]);
qsort(1,n);
For i:=1 To n Do
Begin
t:=0;
For j:=i+1 To n do
If (map[i,1]>=map[j,1]) And (map[i,2]>=map[j,2]) Then
Inc(t);
Inc(a[t]);
End;
For i:=0 To n-1 Do
Writeln(a[i]);
End.

水题，先离散化了之后BIT维护即可。。。脑残的BIT的界打错了，结果花了半个小时才写出来555
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 960 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 964 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 960 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 964 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 960 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 960 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 960 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 964 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 960 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 960 KiB, score = 10
Accepted, time = 0 ms, mem = 964 KiB, score = 100
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std ;

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

int a[ MAXN ] , n , ans[ MAXN ] , N = 0 ;

void Add( int x , int y ) {
for ( int i = x ; i <= N ; i += lowbit( i ) ) a[ i ] += y ;
}

int Sum( int x ) {
int rec = 0 ; for ( ; x ; x -= lowbit( x ) ) rec += a[ x ] ;
return rec ;
}

struct pos {
int x , y ;
bool operator < ( const pos &a ) const {
return x < a.x || ( x == a.x && y < a.y ) ;
}
bool operator == ( const pos &a ) const {
return x == a.x && y == a.y ;
}
} b[ MAXN ] ;

int main( ) {
// freopen( "input.txt" , "r" , stdin ) ; freopen( "output.txt" , "w" , stdout ) ;
scanf( "%d" , &n ) ; for ( int i = 0 ; i < n ; i ++ ) scanf( "%d%d" , &b[ i ].x , &b[ i ].y ) , N = max( N , b[ i ].y ) ;
sort( b , b + n ) ;
int i = 0 ;
while ( i < n ) {
int cnt = 1 ; for ( ; b[ i ] == b[ i + 1 ] && i + 1 < n ; i ++ ) cnt ++ ;
ans[ Sum( b[ i ].y ) + cnt - 1 ] += cnt ; Add( b[ i ].y , cnt ) ;
++ i ;
}
for ( int i = 0 ; i < n ; i ++ ) printf( "%d\n" , ans[ i ] ) ;
return 0 ;
}

评测结果

编译成功

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

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

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

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

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

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

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

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

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

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

Accepted, time = 30 ms, mem = 976 KiB, score = 100

program p1066;
var inf,outf:text;
maxy,n:longint;
x,y,num,d:array[0..15000]of longint;
////////////////////////////////////////////////////////////////////////////////
procedure init;
var i:longint;
begin
read(n);
for i:=1 to n do
begin
read(x[i],y[i]);
end;
end;
////////////////////////////////////////////////////////////////////////////////
procedure swap(pp,qq:longint);
var tim:longint;
begin
tim:=x[pp];x[pp]:=x[qq];x[qq]:=tim;
tim:=y[pp];y[pp]:=y[qq];y[qq]:=tim;
end;

////////////////////////////////////////////////////////////////////////////////
procedure fixduiy(l,r:longint);
var time,tim,p1,p2:longint;
begin
p1:=l; p2:=2*p1; time:=y[p1]; tim:=x[p1];
while ((p2<=r)and(y[p2]>time))or((p2<r)and(y[p2+1]>time)) do
begin
if (p2<r)and(y[p2]<y[p2+1]) then inc(p2);
if y[p2]>time then
begin
y[p1]:=y[p2];
x[p1]:=x[p2];
end;
p1:=p2; p2:=p1*2;
end;
y[p1]:=time;
x[p1]:=tim;
end;
////////////////////////////////////////////////////////////////////////////////
procedure dsorty;
var i:longint;
begin
for i:=n div 2 downto 1 do fixduiy(i,n);
for i:=1 to n-1 do
begin
swap(1,n-i+1);
fixduiy(1,n-i);
end;
end;
////////////////////////////////////////////////////////////////////////////////
procedure lisany;
var i,j,k:longint;
begin
j:=0;k:=0;
for i:=1 to n do
begin
if y[i]>k then
begin
inc(j);
k:=y[i];
end;
y[i]:=j;
end;
maxy:=j;
end;
////////////////////////////////////////////////////////////////////////////////
procedure fixduix(l,r:longint);
var time,tim,p1,p2:longint;
begin
p1:=l; p2:=2*p1; time:=y[p1]; tim:=x[p1];
while ((p2<=r)and(x[p2]>tim))or((p2<r)and(x[p2+1]>tim)) do
begin
if (p2<r)and(x[p2]<x[p2+1]) then inc(p2);
if x[p2]>tim then
begin
y[p1]:=y[p2];
x[p1]:=x[p2];
end;
p1:=p2; p2:=p1*2;
end;
y[p1]:=time;
x[p1]:=tim;
end;
////////////////////////////////////////////////////////////////////////////////
procedure dsortx;
var i:longint;
begin
for i:=1 to n do x[i]:=x[i]*32000+y[i];
for i:=n div 2 downto 1 do fixduix(i,n);
for i:=1 to n-1 do
begin
swap(1,n-i+1);
fixduix(1,n-i);
end;
end;
////////////////////////////////////////////////////////////////////////////////
procedure main;
var i,j:longint;
begin
fillchar(num,sizeof(num),0);
fillchar(d,sizeof(d),0);
for i:=1 to n do
begin
inc(num[d[y[i]]]);
for j:=y[i] to maxy do inc(d[j]);
end;
for i:=0 to n-1 do
writeln(num[i]);
end;
////////////////////////////////////////////////////////////////////////////////
begin
init;
dsorty;
lisany;
dsortx;
main;
end.

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int c[100000],star[100000],n,x,y;
int lowbit(int k){return k&(k^(k-1));}
struct arr{int x,y;}a[100000];
void change(int k,int delta){
while(k<=32000){
c[k]+=delta;
k+=lowbit(k);
}
}
bool cmp(const arr &a,const arr &b){
if (a.y!=b.y) return a.y<b.y;
else return a.x<b.x;
}
int getsum(int k){
int t=0;
while(k>0){
t+=c[k];
k-=lowbit(k);
}return t;
}
void init(){
int d;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
a[i].x++;
}sort(a+1,a+n+1,cmp);
//for(int i=1;i<=n;i++) printf("%d %d\n",a[i].x,a[i].y);
for(int i=1;i<=n;i++){
d=getsum(a[i].x);
change(a[i].x,1);
star[d]++;
}
}
void print(){
for(int i=0;i<n;i++) printf("%d\n",star[i]);
}
int main(){
init();
print();
return 0;
}

虽然我写n^2暴力可以过，但还是不知道正规算法是什么

var
n,i:longint;
ans,a,b,c:array[0..32001] of longint;
function lowbit(k:longint):longint;
begin
exit((-k)and(k));
end;

procedure update(i:longint);
begin
while i<=32001 do
begin
inc(c[i]);
i:=i+lowbit(i);
end;
end;

function sum(i:longint):longint;
begin
sum:=0;
while i>0 do
begin
sum:=sum+c[i];
i:=i-lowbit(i);
end;
end;
procedure qs(low,high:longint);
var i,j,mid,mid1,t:longint;
begin
i:=low; j:=high; mid:=a[(i+j) div 2]; mid1:=b[(i+j) div 2];
repeat
while (a[i]<mid) or ((a[i]=mid) and (b[i]<mid1)) do inc(i);
while (a[j]>mid) or ((a[j]=mid) and (b[j]>mid1)) do dec(j);
if i<=j then
begin
t:=a[i]; a[i]:=a[j]; a[j]:=t;
t:=b[i]; b[i]:=b[j]; b[j]:=t;
inc(i); dec(j);
end;
until i>j;
if i<high then qs(i,high);
if j>low then qs(low,J);
end;

begin
readln(n);
for i:=1 to n do
readln(a[i],b[i]);
qs(1,n);
for i:=1 to n do
begin
inc(ans[sum(b[i])]);
update(b[i]);
end;

for i:=0 to n-1 do
writeln(ans[i]);
end.

###Block code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
struct node{
int r,l,v;
}tr[65000];
struct A{
int x,y;
}f[15002];
bool cmp(A a,A b){
return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
}
void build_tree(int step,int lf,int rt){
tr[step].v=0;
tr[step].l=lf;
tr[step].r=rt;
if(lf==rt) return ;
int mid=(lf+rt)/2;
build_tree(step*2,lf,mid);
build_tree(step*2+1,mid+1,rt);
}
void insert(int delta,int st,int ed,int step){
int mid=(tr[step].l+tr[step].r)>>1;
if(tr[step].l==st&&tr[step].r==ed){
tr[step].v+=delta;
return ;
}else if(tr[step].r==tr[step].l){
return ;
}else if(ed<=mid){
insert(delta,st,ed,step*2);
}else if(st>mid){
insert(delta,st,ed,step*2+1);
}else{
insert(delta,st,mid,step*2);
insert(delta,mid+1,ed,step*2+1);
}
return ;
}
int query(int x,int step){
if(tr[step].l==tr[step].r){
return tr[step].v;
}
int mid=(tr[step].l+tr[step].r)>>1;
return tr[step].v+((x<=mid)?query(x,step*2):query(x,step*2+1));
}
int main(){
int n,ans[15003];
while(scanf("%d",&n)==1){
memset(ans,0,sizeof(ans));
build_tree(1,0,32002);
for(int i=0;i<n;i++)
scanf("%d%d",&f[i].x,&f[i].y);
sort(f,f+n,cmp);
for(int i=0;i<n;i++){
ans[query(f[i].y,1)]++;
insert(1,f[i].y,32002,1);
}
for(int i=0;i<n;i++)
printf("%d\n",ans[i]);
}
return 0;
}

#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <stack>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define abs(x) ((x)>0?(x):-(x))
#define __max(a,b) ((a)>(b)?(a):(b))
#define __min(a,b) ((a)<(b)?(a):(b))
#define rep(i,repstt,repend) for(int i=repstt;i<repend;i++)
#define erep(i,repstt,repend) for(int i=repstt;i<=repend;i++)
#define inf 0x7f//2147483647
#define iinf 0x7fffffff
#define PI acos(-1.0)
#define NOBUG puts("No_Bug_Hear");
#define STOP system("pause");
#define FOUT freopen("out.txt","w",stdout);
#define FIN freopen("in.txt","r",stdin);
#define OUTCLOSE fclose(stdout);
#define INCLOSE fclose(stdin);
#define INIT(a,b) memset(a,b,sizeof(a))
typedef long long ll;
using namespace std;

struct bat{
int x,y;
}f[15003];
bool cmp(bat xx,bat yy){
return (xx.x==yy.x)?(xx.y<yy.y):(xx.x<yy.x);
}
int n,ans[15003],c[32003];
int lowbit(int x){
return x&(-x);
}
int trsum(int x){
int ret=0;
while(x){
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
void update(int x,int dx){
while(x<32003){
c[x]+=dx;
x+=lowbit(x);
}
return ;
}
int main(){
//FIN
//FOUT
while(cin>>n){
INIT(ans,0);
erep(i,1,n)
scanf("%d%d",&f[i].x,&f[i].y);
sort(f+1,f+1+n,cmp);
erep(i,1,n){
ans[trsum(f[i].y)]++;
update(f[i].y,1);
}
erep(i,0,n-1)
printf("%d\n",ans[i]);
}
//INCLOSE
//OUTCLOSE
return 0;
}

我为什么错了
#include<iostream>
using namespace std;
int main() {
int n,i,j,x[5001],z[5001],y[5001],u[5000];
cin>>n;
for(i=1;i<=n;i++) cin>>x[i]>>y[i];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(x[i]<x[j]&&y[i]<y[j]) z[j]++;
for(j=1;j<=n;j++)
u[z[j]]++;
for(i=0;i!=n;i++) cout<<u[i]<<endl;
return 0;
}