「fjWC2015」Screen
「题目描述」
码农有一块超新星屏幕,它有N个像素点,每个像素点有亮度和灰度两个参数,记为I和H, 范围都是0~32000.
一天,码农突发奇想,想知道哪个点比较容易亮瞎眼睛。为此,他定义了一个瞎眼指数: 瞎眼指数就是灰度和亮度均不大于该像素点的像素个数。
现在,码农希望知道,瞎眼指数为0~N-1的像素点分别有多少个
「输入格式」
第一行一个数字N,代表有N个像素点。接下来N行,每行两个数字,代表该像素点的亮度和灰度。
N个像素的亮度和灰度。像素按照灰度从小到大的顺序给出,(0 <= I, H <= 32000, N < 20000)
「输出格式」
输出:瞎眼指数从0到H-1之间各等级的像素个数。
「样例输入」
5
1 1
5 1
7 1
3 3
5 5
「样例输出」
1
2
1
1
0
题解
这种题都能错的全FJ估计除了我没几个了。。
排序树状数组。。。我真是傻逼啊TAT
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include<set> #include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define rad 100000000 #define inf 1000000000 #define ll long long #define eps 1e-10 #define pi acos(-1) using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; int t[40005],ans[40005]; struct data{ int x,y; }a[40005]; void add(int x,int val) { for(int i=x;i<=40000;i+=i&-i) t[i]+=val; } int query(int x) { int ans=0; for(int i=x;i;i-=i&-i) ans+=t[i]; return ans; } bool operator<(data a,data b) { if(a.x==b.x)return a.y<b.y; return a.x<b.x; } int main() { //freopen("screen.in","r",stdin); //freopen("screen.out","w",stdout); n=read(); for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read()+1; sort(a+1,a+n+1); for(int i=1;i<=n;i++) { int tmp=query(a[i].y); add(a[i].y,1); ans[tmp]++; } for(int i=0;i<n;i++)printf("%d\n",ans[i]); return 0; } |
Subscribe