QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#284061#3163. Bomaswarner1129AC ✓534ms68520kbC++203.8kb2023-12-15 22:09:582023-12-15 22:09:59

Judging History

This is the latest submission verdict.

  • [2023-12-15 22:09:59]
  • Judged
  • Verdict: AC
  • Time: 534ms
  • Memory: 68520kb
  • [2023-12-15 22:09:58]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
template <class... T> void dbg(T... x) { char e{}; ((cerr << e << x, e = ' '), ...); }
template <class T> void org(T l, T r) { while (l != r) cerr << ' ' << *l++; cerr << '\n'; }
#define debug(x...) dbg(#x, '=', x, '\n')
#define olist(x...) dbg(#x, '='), org(x)
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define debug(...) ((void)0)
#define olist(...) ((void)0)
#endif
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second

using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using Pt = pair<int, int>;

template <class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
constexpr int mod = 998244353;
constexpr double eps = 0;

template<class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); }
template<class... T> int add(T... x) { int t{}; return (((t += x) %= mod), ...), t; }
template<class... T> int mul(T... x) { i64 t{1}; return (((t *= x) %= mod), ...), t; }

int sig(double x) { return (x > eps) - (x < -eps); }

struct Cir {
    i64 x, y, r, id, type;
    double get(double t) const {
        return y + type * sqrt(r * r - (x - t) * (x - t));
    }
};

void solve() {
    int n, q;
    cin >> n >> q;

    const int m = n + q;
    vector<array<int, 3>> C(m);
    vector<pair<int, int>> event;
    for (int i = 0; i < m; i++) {
        int x, y, r;
        cin >> x >> y >> r;
        C[i] = {x, y, r};
        event.emplace_back(x - r, i + m);
        event.emplace_back(x + r, i);
    }

    sort(all(event));

    int curx = -3e7;
    auto cmp = [&](const Cir &a, const Cir &b) -> bool {
        double s = a.get(curx), t = b.get(curx);
        if (sig(s - t) == 0) return a.type == b.type ? a.id < b.id : a.type < b.type;
        return s < t;
    };
    
    vector<int> pa(m, -1);
    vector G(m, vector<int>{});
    set<Cir, decltype(cmp)> S(cmp);
    for (auto [x, id] : event) {
        curx = x;
        
        Cir up{C[id % m][0], C[id % m][1], C[id % m][2], id % m, 1};
        Cir low{C[id % m][0], C[id % m][1], C[id % m][2], id % m, -1};

        if (id >= m) { // add
            id -= m;
            auto it = S.lower_bound(up);
            if (it != S.end() and it->type == 1) {
                int f = it->id;
                G[f].push_back(id);
                pa[id] = f;
            } else if (it != S.end() and it->type == -1) {
                int f = pa[it->id];
                if (f != -1) {
                    G[f].push_back(id);
                    pa[id] = f;
                }
            }
            S.insert(up);
            S.insert(low);
        } else { // del
            S.erase(up);
            S.erase(low);
        }

    }

    for (int i = 0; i < m; i++) {
        debug(i);
        olist(all(G[i]));
    }

    vector<bool> vis(m);
    vector dp(m, array<int, 2>{});
    auto dfs = [&](auto self, int u) -> void {
        if (vis[u]) return;
        vis[u] = 1;
        for (int v : G[u]) {
            self(self, v);
            if (u < n) {
                dp[u][0] += max(dp[v][0], dp[v][1]);
                dp[u][1] += dp[v][0];
            } else {
                dp[u][0] += dp[v][0];
                dp[u][1] += max(dp[v][0], dp[v][1]);
            }
        }
        if (u < n) dp[u][1] += 1;
    };
    for (int i = 0; i < m; i++)
        if (!vis[i]) dfs(dfs, i);

    for (int i = n; i < n + q; i++) {
        cout << max(dp[i][0] + 1, dp[i][1]) << '\n';
    }
} 

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3504kb

input:

3 5
0 0 100
0 50 20
0 -50 20
0 0 80
0 0 2
500 0 2
0 50 25
0 0 150

output:

2
1
1
1
3

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 534ms
memory: 68520kb

input:

100000 100000
0 0 177461
0 0 1212
0 0 106548
0 0 93559
0 0 155649
0 0 8291
0 0 183489
0 0 29821
0 0 191678
0 0 71901
0 0 33471
0 0 132700
0 0 145730
0 0 76077
0 0 60942
0 0 128623
0 0 40935
0 0 31129
0 0 90101
0 0 35338
0 0 48909
0 0 176056
0 0 88015
0 0 162994
0 0 89426
0 0 157047
0 0 149106
0 0 66...

output:

13037
19135
13258
12786
36495
41010
10043
10595
1790
42734
19510
7466
12734
399
22483
65
44682
5971
24586
5683
6185
45000
38645
36401
2060
6820
19429
20203
15172
1535
961
22850
39203
735
32462
7427
48457
30027
43505
20521
45017
21763
31570
38556
36905
4518
34405
11379
1423
46918
18962
28138
39470
40...

result:

ok 100000 lines

Test #3:

score: 0
Accepted
time: 234ms
memory: 25336kb

input:

100000 1000
0 -585740 7
0 -53180 9
0 571380 1
0 228460 1
0 315240 5
0 -288560 3
0 -187500 2
0 -695880 2
0 -624540 2
0 -443260 3
0 -192120 9
0 978300 2
0 -564880 3
0 285580 2
0 -696220 2
0 954360 4
0 -19820 9
0 -123320 1
0 931400 6
0 149160 9
0 56380 9
0 39460 7
0 -360660 5
0 23600 7
0 222900 6
0 756...

output:

29
61
31
33
41
33
51
19
59
9
33
47
41
15
35
59
45
27
21
37
33
53
27
3
1
9
3
21
49
39
1
27
43
7
41
5
1
13
3
7
47
35
47
9
41
33
11
15
37
35
17
5
23
23
49
25
17
15
49
15
53
33
47
1
41
7
17
33
53
7
17
43
17
61
27
31
31
47
53
15
5
39
7
23
35
45
59
15
49
13
47
29
15
37
1
25
23
61
7
59
15
35
47
57
51
45
19...

result:

ok 1000 lines

Test #4:

score: 0
Accepted
time: 322ms
memory: 39780kb

input:

100000 50000
7068750 7131250 2
-7131250 7068750 3
7131250 -7068750 1
-7068750 -7131250 1
7068755 7131245 2
-7131245 7068755 3
7131245 -7068755 1
-7068755 -7131245 3
7068760 7131240 1
-7131240 7068760 1
7131240 -7068760 1
-7068760 -7131240 1
7068765 7131235 3
-7131235 7068765 3
7131235 -7068765 3
-70...

output:

19177
12510
14311
19825
16433
7356
3708
4170
19481
13152
14357
15239
5840
5941
9243
11317
14464
19210
7867
5479
11014
21098
1960
14425
994
7411
14615
2900
7098
19671
4817
2958
11286
20903
3323
3847
22084
20399
14357
13564
10673
18188
15420
11072
20096
12840
16900
13163
8387
9690
9810
3926
76
11731
1...

result:

ok 50000 lines

Test #5:

score: 0
Accepted
time: 71ms
memory: 15648kb

input:

100000 100000
0 0 1
3 0 1
6 0 1
9 0 1
12 0 1
15 0 1
18 0 1
21 0 1
24 0 1
27 0 1
30 0 1
33 0 1
36 0 1
39 0 1
42 0 1
45 0 1
48 0 1
51 0 1
54 0 1
57 0 1
60 0 1
63 0 1
66 0 1
69 0 1
72 0 1
75 0 1
78 0 1
81 0 1
84 0 1
87 0 1
90 0 1
93 0 1
96 0 1
99 0 1
102 0 1
105 0 1
108 0 1
111 0 1
114 0 1
117 0 1
120 ...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 214ms
memory: 18144kb

input:

100000 100000
1300000 -150000 1418
1300000 1740000 844
1300000 1920000 3257
1300000 -1920000 193
1300000 -100000 484
1300000 -440000 2288
1300000 1180000 527
1300000 -1190000 2119
1300000 -1590000 42
1300000 1400000 2458
1300000 1160000 1991
1300000 1070000 2112
1300000 -1350000 1723
1300000 -390000...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #7:

score: 0
Accepted
time: 1ms
memory: 3444kb

input:

4 6
0 13 11
0 34 8
0 12 2
0 30 2
0 52 2
0 18 2
0 29 29
0 6 2
0 46 2
0 36 2

output:

1
1
3
1
1
1

result:

ok 6 lines

Test #8:

score: 0
Accepted
time: 1ms
memory: 3540kb

input:

39 61
0 299 299
0 382 56
0 258 8
0 453 11
0 8 2
0 341 11
0 104 2
0 29 17
0 399 5
0 495 11
0 446 2
0 50 2
0 22 8
0 202 2
0 529 5
0 468 2
0 544 2
0 550 2
0 408 2
0 559 5
0 491 5
0 284 2
0 168 2
0 59 5
0 571 5
0 110 2
0 254 2
0 224 2
0 300 2
0 580 2
0 334 2
0 306 2
0 140 2
0 71 5
0 80 2
0 116 2
0 34 2
...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
12
7
7
3
2
2
2
1
2
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

result:

ok 61 lines

Test #9:

score: 0
Accepted
time: 2ms
memory: 3680kb

input:

481 519
0 2999 2999
0 2230 2228
0 552 548
0 1434 332
0 143 137
0 1172 68
0 73 65
0 3300 98
0 5191 65
0 4791 167
0 2795 101
0 3675 41
0 421 137
0 5380 50
0 193 53
0 3260 56
0 2912 14
0 5437 5
0 390 104
0 5467 23
0 577 17
0 1277 35
0 2719 23
0 3930 62
0 513 17
0 2951 23
0 4077 83
0 5650 38
0 1787 17
0...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
30
44
24
37
32
10
12
6
6
9
10
9
2
2
6
7
6
7
7
2
5
3
5
2
9
3
1
2
2
3
7
5
3
2
1
4
1
5
7
2
5
1
1
2
2
3
3
1
2
3
2
6
2
2
1
2
1
1
1
3
1
2
3
1
2
1
2
2
2
2
1
1
1
1
1
1
1
3
1
2
1
3
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
2
1
2
5
1
1
1
1
1
1
1
...

result:

ok 519 lines

Test #10:

score: 0
Accepted
time: 17ms
memory: 5464kb

input:

4970 5030
0 15103 7883
0 25957 2969
0 11478 4256
0 37837 1109
0 42766 1784
0 23280 290
0 17262 1526
0 19332 542
0 16178 440
0 29136 206
0 25206 524
0 51478 260
0 47898 1010
0 30075 731
0 1050 230
0 2142 860
0 47375 485
0 16937 317
0 54730 122
0 45582 1028
0 23858 284
0 3156 152
0 17636 380
0 13856 8...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
3749
434
241
245
132
91
104
52
148
129
280
76
108
82
96
60
46
22
77
50
46
62
41
19
49
25
44
14
9
10
10
30
25
17
37
31
35
7
10
22
25
12
35
33
19
23
16
59
12
18
7
20
16
18
4
16
22
16...

result:

ok 5030 lines

Test #11:

score: 0
Accepted
time: 222ms
memory: 26132kb

input:

49988 50012
0 299999 299999
0 109750 109748
0 437818 24602
0 40308 40304
0 93183 12569
0 316809 19721
0 20795 20789
0 348633 12101
0 46010 4424
0 526771 20801
0 241596 5498
0 2302 2294
0 255099 8003
0 338576 2042
0 422904 9686
0 167442 3350
0 266847 3743
0 317681 7685
0 521922 8708
0 372276 4694
0 5...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
4839
4426
2871
1531
1226
993
1646
1423
614
812
292
660
457
723
232
474
682
1262
683
521
536
396
558
203
407
501
447
209
368
142
237
145
237
265
489
204
163
252
122
169
77
51
69
96
143
286
54
100
178
69
189
150
122
100
276
76
144
365
47
160
183
136
93
1...

result:

ok 50012 lines

Test #12:

score: 0
Accepted
time: 93ms
memory: 15512kb

input:

100000 100000
-9999359 -9999999 1
-9998719 -9999999 1
-9998079 -9999999 1
-9997439 -9999999 1
-9996799 -9999999 1
-9996159 -9999999 1
-9995519 -9999999 1
-9994879 -9999999 1
-9994239 -9999999 1
-9993599 -9999999 1
-9992959 -9999999 1
-9992319 -9999999 1
-9991679 -9999999 1
-9991039 -9999999 1
-99903...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines