QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#625079#9427. Collect the CoinsffaoTL 990ms62284kbC++232.6kb2024-10-09 17:22:052024-10-09 17:22:06

Judging History

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

  • [2024-11-06 15:56:27]
  • hack成功,自动添加数据
  • (/hack/1139)
  • [2024-10-09 17:22:06]
  • 评测
  • 测评结果:TL
  • 用时:990ms
  • 内存:62284kb
  • [2024-10-09 17:22:05]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int maxn = 1e6 + 100;

ll n;
pair<ll, ll> vec[maxn];
set<pair<ll, ll>> all;
unordered_set<ll> all_pos;
ll V;

bool valid(ll i, ll j) {
    auto [t1, p1] = vec[i];
    auto [t2, p2] = vec[j];
    return abs(p1 - p2) <= abs(t1 - t2) * V;
}

void insert(ll pos) {
    auto [t, p] = vec[pos];
    // insert (p - tV, -p-tV)
    // ...
    auto x = p - t * V;
    auto y = -p - t * V;

    bool flag = true;
    auto rit = all.lower_bound({x, y});
    if (rit == all.end())
        flag = true;
    else {
        auto [tx, ty] = *rit;
        if (ty < y)
            flag = true;
        else
            flag = false;
    }
    if (flag) {
        auto it = rit;
        while (it != all.begin()) {
            auto pit = prev(it, 1);
            auto [tx, ty] = *pit;
            if (ty <= y)
                all.erase(pit);
            else
                break;
        }
        all.insert({x, y});
    }
}

bool check() {
    static bool dp[maxn];
    std::fill(dp, dp + n + 1, 0);
    all.clear();

    for (int i = 2; i < n; i++) {
        if (!valid(i - 1, i)) break;
        dp[i + 1] = true;
    }
    // check st = 2, i = 3?
    dp[2] = true;
    for (ll i = 3; i <= n; i++) {
        if (!valid(i - 2, i - 1)) {
            all.clear();
        }
        // cout << "addr2" << endl;
        if (dp[i - 1]) insert(i - 2);
        // j-1
        auto [qt, qp] = vec[i];
        auto qx = qp - qt * V;
        auto qy = -qp - qt * V;
        auto it = all.lower_bound({qx, qy});
        if (it != all.end()) {
            auto [tx, ty] = *it;
            if (ty >= qy) dp[i] = true;
        }
    }
    for (int temp = n; temp >= 1; temp--) {
        if (temp < n and !valid(temp, temp + 1)) break;
        if (dp[temp]) return true;
    }
    return false;
};

void solve() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> vec[i].first >> vec[i].second;
    }
    all_pos.clear();
    for (ll i = 1; i <= n; i++) {
        all_pos.insert(vec[i].second);
    }
    if (all_pos.size() <= 2) {
        cout << 0 << '\n';
        return;
    }

    ll L = 1, R = 1e9 + 100;
    while (L < R) {
        ll mid = (L + R) / 2;
        V = mid;
        if (check())
            R = mid;
        else
            L = mid + 1;
    }
    if (L > 1e9) L = -1;
    cout << L << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll t;
    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: 3632kb

input:

3
5
1 1
3 7
3 4
4 3
5 10
1
10 100
3
10 100
10 1000
10 10000

output:

2
0
-1

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 36ms
memory: 6216kb

input:

1135
2
6 5
8 8
8
2 9
2 10
4 4
5 3
6 2
6 8
8 2
8 7
1
9 1
6
4 6
6 1
6 2
9 10
10 1
10 7
5
1 6
2 5
6 7
8 6
10 3
8
1 10
5 4
5 7
6 1
6 6
8 4
9 1
9 4
8
1 1
1 3
2 9
3 3
5 9
6 10
9 7
10 7
3
5 8
6 6
10 6
7
2 9
4 7
5 10
6 3
6 7
8 9
10 1
6
1 4
2 8
5 9
7 10
9 1
10 5
9
2 7
4 5
5 9
6 10
7 4
9 4
9 9
10 3
10 7
1
3 1...

output:

0
3
0
3
1
3
6
0
3
2
2
0
2
5
0
1
5
1
2
0
0
0
1
4
2
0
2
1
3
0
3
2
3
2
5
3
1
1
0
1
1
1
0
2
0
1
0
1
0
2
1
0
2
3
4
4
1
1
1
0
1
3
0
1
4
4
3
0
0
2
2
6
4
2
1
0
0
1
0
2
1
2
0
1
1
3
0
0
1
2
0
3
0
2
2
2
1
0
0
0
5
1
2
0
6
1
1
1
2
2
2
0
3
1
4
3
6
0
8
1
1
3
0
2
2
4
1
1
0
0
0
7
2
2
1
0
0
3
1
2
1
1
2
5
3
0
3
3
3
5
...

result:

ok 1135 lines

Test #3:

score: 0
Accepted
time: 814ms
memory: 45024kb

input:

1
1000000
2 57841
2 357142
3 496329
3 545446
4 503408
4 590762
5 78281
6 196926
6 349414
7 200245
8 953412
11 616898
12 592065
13 945945
15 20908
15 852722
16 221184
16 401521
17 884478
18 186072
18 931445
19 833560
20 314177
21 138453
21 731965
22 172104
23 595921
25 372617
27 545759
28 977029
30 4...

output:

994024

result:

ok single line: '994024'

Test #4:

score: 0
Accepted
time: 489ms
memory: 61080kb

input:

1
1000000
6 1991827
13 8125243
19 22493
24 4282711
28 356362
39 765152
41 6737899
44 8549464
57 4530192
64 7201376
67 6695629
70 3830504
70 6658581
71 4591382
71 8349070
75 2107828
76 4073563
81 2712838
92 1391185
95 4663781
102 5986957
113 8423636
118 7826607
122 1171556
122 3118750
160 938066
162 ...

output:

9609125

result:

ok single line: '9609125'

Test #5:

score: 0
Accepted
time: 524ms
memory: 62164kb

input:

1
1000000
108 565196036
597 561009880
1007 831705109
2597 55966094
2869 765993518
3025 202191673
3283 237167825
3410 829643653
4879 960747182
7284 679152790
8765 64201585
8899 97619554
9320 713144607
9519 991746776
9913 346063307
11161 970513525
11256 975123550
12073 778562963
14286 206857559
15803 ...

output:

268764694

result:

ok single line: '268764694'

Test #6:

score: 0
Accepted
time: 51ms
memory: 4432kb

input:

1135
9
1 7
3 7
4 10
5 2
6 8
7 10
8 3
9 10
10 4
9
1 4
3 2
4 1
5 3
5 7
7 2
8 4
10 7
10 10
5
3 10
4 4
7 3
8 8
9 7
8
4 1
4 4
5 5
6 4
8 3
8 4
9 2
9 4
3
1 4
5 3
10 9
7
2 6
3 4
4 2
6 3
6 9
8 3
8 7
7
1 5
3 6
4 8
4 9
5 10
8 4
8 10
1
8 6
9
1 6
2 6
3 9
5 9
6 7
6 9
8 1
9 4
10 4
5
3 9
4 3
4 6
6 4
8 5
7
1 1
2 1
3...

output:

3
2
1
1
1
2
2
0
3
3
4
0
4
1
3
2
0
0
0
3
2
6
3
0
1
0
4
0
3
0
2
0
3
0
0
1
4
0
1
2
4
0
2
1
1
1
2
8
1
1
1
1
1
5
0
1
0
3
0
3
2
2
3
2
5
0
0
2
6
4
3
2
2
1
2
0
0
4
5
0
6
5
0
4
3
5
4
1
3
0
0
2
0
8
2
1
1
2
1
3
1
1
4
0
5
0
4
0
1
6
0
7
1
1
0
3
2
1
5
1
3
1
1
8
3
0
2
1
1
0
0
1
1
1
0
6
1
1
1
1
0
0
1
3
1
4
0
2
0
1
...

result:

ok 1135 lines

Test #7:

score: 0
Accepted
time: 596ms
memory: 44880kb

input:

1
1000000
1 421151
2 313604
3 982622
4 993745
5 997253
6 859839
7 835793
8 324554
9 553026
10 218950
11 672201
12 373214
13 147841
14 445973
15 807912
16 753995
17 564224
18 662086
19 862430
20 378806
21 591406
22 415543
23 490080
24 184083
25 287323
26 578004
27 302543
28 302371
29 689597
30 538475...

output:

492642

result:

ok single line: '492642'

Test #8:

score: 0
Accepted
time: 635ms
memory: 60736kb

input:

1
1000000
4 5761079
27 9913703
31 3480982
33 8607438
37 3321663
64 3998110
72 4273261
78 7438482
84 8988669
96 920933
101 9309679
106 2230436
118 8605436
123 104422
129 7742745
131 4597839
139 9509656
142 3293909
159 9386630
176 9018043
188 3538661
207 9103530
233 2796496
239 7390510
246 2350961
249...

output:

4801594

result:

ok single line: '4801594'

Test #9:

score: 0
Accepted
time: 659ms
memory: 62284kb

input:

1
1000000
1659 745509192
1793 453656007
2417 245865714
3481 181708105
4181 423236911
5279 477367945
7195 966897525
9086 169940320
12642 77818181
14303 26150912
15915 448404964
16486 168882999
16531 105802492
16723 521426994
16754 508715351
19350 563835961
20119 410674400
20775 157959337
20870 320155...

output:

257246803

result:

ok single line: '257246803'

Test #10:

score: 0
Accepted
time: 491ms
memory: 45120kb

input:

1
1000000
1 199948
2 400091
2 463093
3 30523
4 771947
6 320897
7 104702
8 993244
9 926737
10 794612
11 210817
12 351420
13 495204
14 86010
16 589773
17 940494
18 467002
19 785066
20 724000
21 843646
22 47780
23 44610
24 494920
25 717543
27 869625
27 888906
28 972386
29 138651
30 73442
31 229124
32 4...

output:

983172

result:

ok single line: '983172'

Test #11:

score: 0
Accepted
time: 660ms
memory: 60880kb

input:

1
1000000
8 4343641
20 9188668
27 7784999
36 567704
71 225957
104 1690417
111 6719613
130 3931557
131 4091107
138 6733754
140 694514
143 5699446
164 8271151
190 5161164
204 6604398
219 7818039
225 103011
225 1033586
229 5290991
258 6252181
268 7412984
269 1107497
270 5043326
282 5968288
303 893538
3...

output:

9374697

result:

ok single line: '9374697'

Test #12:

score: 0
Accepted
time: 703ms
memory: 62132kb

input:

1
1000000
339 331918409
1828 806301739
4285 288684076
5821 210020913
6987 489751813
8084 346009704
9692 770088627
10407 404154547
10866 421926603
11062 935900735
11722 724947155
13636 832546152
16251 197187715
16251 291560397
17148 385272967
18475 77755669
19621 568102456
21145 20338367
21638 135488...

output:

907611400

result:

ok single line: '907611400'

Test #13:

score: 0
Accepted
time: 70ms
memory: 4184kb

input:

1135
10
1 3
1 7
2 3
2 5
4 7
4 8
6 1
6 4
7 5
7 8
8
1 4
2 2
2 3
3 5
3 10
6 8
9 1
9 4
1
10 7
1
2 5
6
1 6
1 9
5 2
5 9
8 1
8 4
6
5 8
5 9
6 5
6 10
8 3
8 9
9
1 5
1 6
4 9
5 6
5 7
7 2
7 10
10 2
10 3
3
6 9
10 5
10 8
3
4 6
4 7
7 10
1
8 6
7
1 2
2 3
2 10
3 4
3 6
5 4
5 9
3
2 1
2 9
7 7
8
6 2
6 8
7 6
7 7
8 2
8 3
10...

output:

4
7
0
0
2
3
3
1
1
0
4
1
4
1
0
1
0
7
1
2
1
3
3
1
4
4
0
0
2
0
2
5
0
3
1
3
2
4
0
0
4
2
0
6
5
2
1
3
0
1
2
0
2
2
2
2
0
1
4
5
0
6
5
5
0
0
2
0
2
3
1
5
5
4
3
6
0
2
3
7
1
0
0
0
1
1
4
2
5
4
0
0
3
3
0
0
1
0
3
1
2
5
3
2
3
5
0
1
3
7
4
3
3
0
2
0
0
1
1
3
3
1
0
0
3
1
0
0
6
3
6
7
1
0
0
4
4
0
0
1
4
2
3
2
1
6
0
0
2
0
...

result:

ok 1135 lines

Test #14:

score: 0
Accepted
time: 911ms
memory: 45116kb

input:

1
1000000
2 77901
2 299883
4 428639
4 813168
5 100173
5 782917
7 40384
7 449788
11 236799
11 975047
12 459959
12 627756
14 268070
14 838229
15 42307
15 750817
18 429714
18 542540
20 396104
20 555946
24 382023
24 670885
25 123347
25 160290
26 338330
26 462536
29 78983
29 370000
32 431681
32 899225
33...

output:

993613

result:

ok single line: '993613'

Test #15:

score: 0
Accepted
time: 990ms
memory: 60932kb

input:

1
1000000
4 3326080
4 9907237
39 453090
39 7480697
52 2672608
52 7499680
78 1255223
78 1706176
117 135598
117 161705
131 2847430
131 9067040
201 2370848
201 4954617
256 832631
256 4772412
265 2646914
265 9939501
291 995828
291 7583564
311 4996097
311 8685066
334 1025837
334 8498081
338 2244726
338 2...

output:

9776177

result:

ok single line: '9776177'

Test #16:

score: -100
Time Limit Exceeded

input:

1
1000000
1387 627417959
1387 938885698
2331 35605535
2331 388781199
2813 377765380
2813 717077893
11097 80601983
11097 601468694
18924 26066416
18924 371804579
21959 646680704
21959 676102593
27236 566499457
27236 811388411
30230 462184409
30230 972254978
30814 68498987
30814 655963890
33826 734512...

output:

804824864

result: