QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#319037 | #5604. Triangle Containment | Assitu21 | WA | 38ms | 7292kb | C++11 | 1.1kb | 2024-02-01 16:30:29 | 2024-02-01 16:30:29 |
Judging History
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'