QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#731434 | #5604. Triangle Containment | beamishboys# | WA | 82ms | 9428kb | C++23 | 1.4kb | 2024-11-10 04:01:34 | 2024-11-10 04:01:34 |
Judging History
answer
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;
int n, x0;
vector<array<int, 3>> spots;
vector<pair<double, int>> ldegs, rdegs;
struct BIT {
int n;
vector<long long> bit;
BIT(int n) : n(n) {
bit.assign(n, 0);
}
void update_bit(int i, long long v) {
int diff = v - bit[i];
for(int j=i; j<n; j+=(j&-j)) bit[j] += diff;
}
long long query_bit(int i) {
long long res = 0;
for(int j=i; j>0; j-=(j&-j)) res += bit[j];
return res;
}
};
int main() {
cin >> n >> x0;
spots.resize(n);
for(auto &[x,y,v] : spots) cin >> x >> y >> v;
ldegs.clear(), rdegs.clear();
for(int i=0; i<n; ++i) {
auto [x,y,v] = spots[i];
double ldeg = atan2(double(y), double(x));
double rdeg = atan2(double(y), double(x0-x)); // interior angle
ldegs.push_back({ldeg, i});
rdegs.push_back({rdeg, i});
}
// we will compress the right to be used in a bit
sort(rdegs.begin(), rdegs.end());
for(int i=0; i<n; ++i) {
auto &[v, j] = rdegs[i];
v = i+1;
spots[j][1] = v;
}
BIT bit(rdegs.size()+10);
vector<long long> res(n, -1);
long long curv = 0;
sort(ldegs.begin(), ldegs.end());
for(auto [ld, i] : ldegs) {
res[i] = bit.query_bit(spots[i][1]);
bit.update_bit(spots[i][1], spots[i][2]);
}
for(auto v : res) cout << v << '\n';
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3932kb
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: 4112kb
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: 0
Accepted
time: 66ms
memory: 9428kb
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 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 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 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 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 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 0 0 0 0 0 0 0 0 ...
result:
ok 99999 lines
Test #4:
score: 0
Accepted
time: 82ms
memory: 9408kb
input:
100000 1000000000 -50000 1000000000 454290650 -49999 1000000000 208284433 -49998 1000000000 854275069 -49997 1000000000 627720731 -49996 1000000000 79147837 -49995 1000000000 614585061 -49994 1000000000 438660998 -49993 1000000000 300657551 -49992 1000000000 546865509 -49991 1000000000 353401129 -49...
output:
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 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 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 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 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 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 100000 lines
Test #5:
score: -100
Wrong Answer
time: 77ms
memory: 9312kb
input:
100000 1000000000 -1000000000 1 423302241 -999999999 1 941931570 -999999998 1 801255926 -999999997 1 434775469 -999999996 1 784636342 -999999995 1 41794758 -999999994 1 768189347 -999999993 1 746924545 -999999992 1 259101843 -999999991 1 798620683 -999999990 1 447243634 -999999989 1 848852324 -99999...
output:
0 423302241 941931570 1743187496 434775469 1219411811 476570227 1244759574 746924545 1006026388 1545545228 1992788862 1595776869 1741301021 1964300085 2366293419 714439107 1264446583 1613461411 1685494458 1614464926 2287502754 2500260551 3280639698 1247954584 1730231337 1485698742 2386390413 1671420...
result:
wrong answer 2nd lines differ - expected: '0', found: '423302241'