QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#750251 | #5604. Triangle Containment | 521289 | WA | 161ms | 7128kb | C++14 | 1.5kb | 2024-11-15 13:39:55 | 2024-11-15 13:39:56 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
inline void debug(){
#ifndef mrclr
freopen("C:/Users/52419/Desktop/icpc/debug.in", "r", stdin);
#endif
}
typedef long long LL;
const int N = 1e5 + 10;
int n, x, k[N]; LL tot, ans[N];
#define lowbit(x) (x & -x)
LL bit[N];
inline void upd(const int x, const LL v){
for(int i = x; i <= n; i += lowbit(i)) bit[i] += v;
}
inline LL que(const int x){
LL res = 0; for(int i = x; i; i -= lowbit(i)) res += bit[i];
return res;
}
int main(){ //debug();
cin >> n >> x;
auto angle = [&] (array<int, 4> a, array<int, 4> b) {
auto [x1, y1, val1, i1] = a;
auto [x2, y2, val2, i2] = b;
return atan2(y2 - y1,x2 - x1);
};
vector<array<int, 4>> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
arr[i][3] = i;
}
sort(begin(arr), end(arr), [&](array<int, 4> a, array<int, 4> b) {
return angle(a, {0, 0, 0, 0}) > angle(b, {0, 0, 0, 0});
});
for(int i = 0; i < n; i++)
k[arr[i][3]] = i + 1;
sort(begin(arr), end(arr), [&](array<int, 4> a, array<int, 4> b) {
return angle(a, {x, 0, 0, 0}) > angle(b, {x, 0, 0, 0});
});
for(int i = 0; i < n; i++){
ans[arr[i][3]] = tot - que(k[arr[i][3]]);
upd(k[arr[i][3]], arr[i][2]), tot += arr[i][2];
}
for(int i = 0; i < n; i++){
cout<< ans[i] <<endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4144kb
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: 4128kb
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: 161ms
memory: 7128kb
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:
81 56 42 50 11 59 1 5 52 9 48 9 3 37 13 73 15 75 30 20 11 9 7 1 26 29 0 18 7 72 58 34 43 0 39 0 1 8 8 35 62 41 40 11 2 0 65 32 4 52 28 8 80 20 5 72 47 46 22 25 12 66 1 25 0 42 1 68 72 63 24 54 0 8 51 9 81 4 19 12 9 22 21 60 88 83 59 4 10 22 44 20 17 32 2 74 25 12 49 30 16 23 5 20 48 3 84 13 37 3 52 ...
result:
wrong answer 1st lines differ - expected: '0', found: '81'