QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#750251#5604. Triangle Containment521289WA 161ms7128kbC++141.5kb2024-11-15 13:39:552024-11-15 13:39:56

Judging History

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

  • [2024-11-15 13:39:56]
  • 评测
  • 测评结果:WA
  • 用时:161ms
  • 内存:7128kb
  • [2024-11-15 13:39:55]
  • 提交

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'