QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#319037#5604. Triangle ContainmentAssitu21WA 38ms7292kbC++111.1kb2024-02-01 16:30:292024-02-01 16:30:29

Judging History

你现在查看的是最新测评结果

  • [2024-02-01 16:30:29]
  • 评测
  • 测评结果:WA
  • 用时:38ms
  • 内存:7292kb
  • [2024-02-01 16:30:29]
  • 提交

answer

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define ld long double
using namespace std;

const int N=1e5+10;
struct zy{int x,y,v,id;ld p;}a[N];
ll f[N],g[N];
int b[N];
int n,X,i,j,x;
ll s;

inline int read(){
	int x=0,z=1; char c=getchar(); if (c=='-') z=-1;
	while(c<'0'||c>'9'){c=getchar(); if (c=='-') z=-1;}
	while('0'<=c&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*z;
}
inline int cmp(zy x,zy y){return x.p<y.p;}
int lb(int x){return x&-x;}
inline ll ask(int x){
	ll s=0;
	for(int i=x;i;i-=lb(i)) s+=g[i];
	return s;
}
inline void ad(int x,int v){
	for(int i=x;i<=n;i+=lb(i)) g[i]+=v;
}
int main(){
	n=read(); X=read();
	for(i=1;i<=n;++i){
		a[i].x=read(); a[i].y=read(); a[i].v=read(); a[i].id=i;
		a[i].p=atan2(a[i].y,a[i].x);
	}
	
	sort(a+1,a+n+1,cmp);
	for(i=n;i>=1;--i)
		b[a[i].id]=n-i+1;
	
	for(i=1;i<=n;++i)
		a[i].p=atan2(a[i].y,a[i].x-X);
	
	s=0;
	sort(a+1,a+n+1,cmp);
	for(i=n;i>=1;--i){
		x=a[i].id;
		f[x]=s-ask(b[x]);
		ad(b[x],a[i].v);
		s+=a[i].v;
	}
	
	for(i=1;i<=n;++i)
		printf("%lld\n",f[i]);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 4380kb

input:

5 8
-8 1 1
-1 10 2
0 3 4
7 1 8
8 2 16

output:

0
12
0
0
8

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 4264kb

input:

6 6
0 1 1
2 3 10
2 5 100
3 1 1000
3 5 10000
4 5 100000

output:

0
1000
1010
0
1010
1000

result:

ok 6 lines

Test #3:

score: -100
Wrong Answer
time: 38ms
memory: 7292kb

input:

99999 1000000000
500002962 1 1
500025469 1 1
500044229 1 1
500026049 1 1
499983663 1 1
499965983 1 1
499988191 1 1
499987116 1 1
500029240 1 1
499975570 1 1
499973295 1 1
499986404 1 1
500023312 1 1
499964976 1 1
499952153 1 1
500046927 1 1
499951857 1 1
499984523 1 1
500038724 1 1
499991318 1 1
500...

output:

0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
5
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
22
0
0
0
0
0
0
0
0
0
0
1
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
32
0
0
0
0
0
3
0
0
0
0
0
2
3
0
0
2
10
0
0
0
0
0
0
0
0
0
0
23
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 3rd lines differ - expected: '0', found: '2'