QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#395215#1375. TripTikmegz112233AC ✓8858ms335388kbC++235.5kb2024-04-21 10:59:012024-04-21 10:59:01

Judging History

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

  • [2024-04-21 10:59:01]
  • 评测
  • 测评结果:AC
  • 用时:8858ms
  • 内存:335388kb
  • [2024-04-21 10:59:01]
  • 提交

answer

#include <bits/stdc++.h>

#define sz(x)  (int)x.size()
#define bigint __int128
#define el '\n'
#define ll long long
#define int  long long
//#define int long long
#define ld long double
using namespace std;
const int N = 1e5 + 4, M = 1e5 + 10, mod = 998244353;
int szz = 1;

struct seg_tree {
    vector<vector<pair<int, int>>> tree;
    // weight , idx
    vector<pair<int, int>> neutral = {};
    int k;

    seg_tree(int n, vector<vector<pair<int, int>>> &v, int k) {
        szz = 1;
        while (szz < n)szz <<= 1;
        tree.assign(2 * szz, neutral);
        this->k = k;
        build(v);
    }

    vector<pair<int, int>> merge(vector<pair<int, int>> val1, vector<pair<int, int>> val2) {
        // vector 2*n 3,3
        for (auto x: val2)val1.push_back(x);
        sort(val1.rbegin(), val1.rend());
        while (sz(val1) > k)val1.pop_back();
        return val1;
    }

    void build(vector<vector<pair<int, int>>> &v, int node = 0, int lx = 0, int rx = szz - 1) {
        if (lx == rx) {
            if (lx < sz(v)) {
                tree[node] = v[lx];
            }
            return;
        }
        int mid = lx + rx >> 1;
        build(v, (node << 1) + 1, lx, mid);
        build(v, (node << 1) + 2, mid + 1, rx);
        tree[node] = merge(tree[(node << 1) + 1], tree[(node << 1) + 2]);
    }

    void set(int idx, vector<pair<int, int>> val, int node = 0, int lx = 0, int rx = szz - 1) {
        if (lx == rx) {
            tree[node] = val;
            return;
        }
        int mid = (lx + rx) >> 1;
        if (mid >= idx) {
            set(idx, val, (node << 1) + 1, lx, mid);
        } else {
            set(idx, val, (node << 1) + 2, mid + 1, rx);
        }
        tree[node] = merge(tree[(node << 1) + 1], tree[(node << 1) + 2]);
    }

    vector<pair<int, int>> query(int l, int r, int node = 0, int lx = 0, int rx = szz - 1) {
        if (lx > r or rx < l)return neutral;
        if (lx >= l and rx <= r) {
            return tree[node];
        }
        int mid = lx + rx >> 1;
        vector<pair<int, int>> q1 = query(l, r, (node << 1) + 1, lx, mid);
        vector<pair<int, int>> q2 = query(l, r, (node << 1) + 2, mid + 1, rx);
        return merge(q1, q2);
    }

};

void acc() {
    int n, k;
    cin >> n >> k;
    // 0
    vector<pair<long long , long long >> points(n);
    // x-axis  , idx
    //  -5 -1 0 1 2 3
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        points[i] = {x, i};
    }
    points.push_back({0, -1});
    sort(points.begin(), points.end());
    n++;
    vector<vector<pair<int, int>>> v(n);
    for (int i = 0; i < n; i++) {
        v[i].push_back({points[i].second, i});
    }
    seg_tree sg(n, v, k);
    int lg = 28;
    vector<int> adj[n + 1][lg];
    vector<int> pw(lg + 1, 1);
    pw[0] = 0;
    for (int i = 2; i < lg; i++)pw[i] = pw[i - 1] * 2;
    for (int bt = 0; bt < lg; bt++) {
//        cout << "with bt = " << bt << el;
//        cout << "---------" << el;
        for (int i = 0; i < n; i++) {
            int l = points[i].first - pw[bt], r = points[i].first + pw[bt];
            pair<long long ,long long > p = {l,-1};
            int  idxl = std::lower_bound(points.begin(), points.end(), p ) - points.begin();
            p = {r,-1};
            auto idxr = std::lower_bound(points.begin(), points.end(), p) - points.begin();
            if (idxr == n or points[idxr].first > r)idxr--;
//            cout << points[i].first << " " << idxl << " " << idxr << el;
            vector<pair<int, int>> ret = sg.query(idxl, idxr);
            // weight , idx
            for (auto [val, idx]: ret) {
                adj[i][bt].push_back(idx);
//                cout << idx << " ";
            }
//            cout << "------" << el;
        }
    }
//    for (int i = 0; i < n; i++) {
//        cout << points[i].first << el;
//        for (int j = 0; j < 4; j++) {
//            cout << "with scoop == " << pw[j] << el;
//            for (auto child: adj[i][j]) {
//                cout << child << " ";
//            }
//            cout << el;
//        }
//    }

    int idx_zero = -1;
    for (int i = 0; i < sz(points); i++) {
        if (points[i].first == 0)idx_zero = i;
    }
    priority_queue<array<int, 3>> pq;
    // num_of operation , lst ,  bt
    pq.push({0, idx_zero, 1});
    vector<int> lst(n, 1e9);
    vector<vector<int>> dist(n + 1, vector<int>(lg, 1e9));
    dist[0][1] = 0;
    while (sz(pq)) {
        array<int, 3> arr = pq.top();
        pq.pop();
        int op = -arr[0], node = arr[1], bt = arr[2];
        for (int i = 0; i < lg; i++) {
            int nw_cost = abs(bt - i) + op;
            for (auto child: adj[node][i]) {
                if (dist[child][i] > nw_cost + (child != node)) {
                    dist[child][i] = nw_cost + (child != node);
                    pq.push({-dist[child][i], child, i});
                }
                if (child == node)lst[child] = min(lst[child], nw_cost);
            }
        }
    }
    vector<int> ans(n - 1, 11223344);
    for (int i = 0; i < sz(points); i++) {
        if (points[i].first == 0)continue;
        ans[points[i].second] = lst[i];
    }
    for (int i = 0; i < sz(ans); i++) {
        if (ans[i] >= 1e9)cout << "-1" << el;
        else cout << ans[i] << el;
    }
//    cout << el;
}

signed main() {
    int t = 1;
    cout.tie(0);
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    //  while (t--)acc();
    acc();
}

详细

Test #1:

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

input:

4 2
-2
-1
-3
2

output:

3
1
3
2

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 5585ms
memory: 258300kb

input:

100000 4
-81032899
-96819000
35569221
67767248
74154777
75473369
3463319
18339682
-77145048
-26587182
-22902096
-55717109
-47237134
-44620229
-45753774
33183854
-15569807
72648777
-33842373
44545672
-48017305
71506102
33448860
-20688896
6205313
21527590
24985350
-14688810
29596074
-47051603
-9258675...

output:

56
49
48
47
47
50
38
42
-1
-1
51
55
51
52
51
46
41
48
46
44
47
47
49
44
37
-1
44
44
45
51
49
49
45
49
44
43
51
54
46
43
-1
44
49
57
46
45
43
47
46
53
48
44
47
-1
49
55
53
47
52
51
49
47
53
56
43
50
43
29
43
50
52
52
47
45
47
50
52
47
49
47
50
49
48
47
49
45
62
37
47
48
51
39
47
46
48
50
47
53
44
52
...

result:

ok 100000 lines

Test #3:

score: 0
Accepted
time: 5601ms
memory: 257460kb

input:

100000 4
70680198
97317334
39546330
-54313602
-76555335
61941724
-8221943
-40467311
-38387353
-79352984
-85695884
-116744
-8014898
-90838613
21642942
-13906694
61034002
41083341
22631959
70997275
75121931
90712180
-50976024
-89714113
62620386
30945015
37854774
2964535
80028136
-28328113
-32257258
78...

output:

-1
59
-1
48
49
43
44
49
46
52
48
-1
45
49
40
45
47
43
46
54
-1
49
46
50
46
44
45
39
45
45
46
52
-1
37
52
49
33
42
42
-1
40
34
50
-1
47
56
50
54
-1
46
-1
44
50
37
-1
50
60
48
51
49
-1
53
47
44
41
-1
47
46
-1
50
47
47
48
51
46
47
44
51
50
48
-1
-1
40
48
-1
43
42
58
51
43
54
43
48
50
41
-1
45
48
48
55
...

result:

ok 100000 lines

Test #4:

score: 0
Accepted
time: 5594ms
memory: 258380kb

input:

100000 4
-22911754
64514931
-46579963
-52307990
-28419918
-35238
66903391
-87096465
15648262
-88916963
96268224
-39583622
-33334243
76123224
30449894
-60512561
92205726
96701672
12953603
70508490
88259167
-12584810
35245713
2029713
19820003
91618921
-66864990
-96291681
73438998
6296068
-26195246
780...

output:

-1
50
45
48
45
22
46
52
46
59
52
52
47
50
52
49
50
48
-1
49
47
55
49
40
50
49
54
-1
48
41
43
41
46
55
-1
50
49
46
48
48
46
47
49
48
50
42
45
55
44
55
54
47
56
-1
52
55
-1
52
-1
54
48
-1
54
41
45
47
50
-1
50
56
48
57
44
48
50
50
48
-1
-1
55
52
53
57
51
45
57
51
45
49
54
52
42
48
57
49
49
51
57
47
51
...

result:

ok 100000 lines

Test #5:

score: 0
Accepted
time: 8858ms
memory: 335388kb

input:

100000 4
-288
-318
-339
-525
-666
-688
714
-1068
1248
-1318
1453
1485
-1503
1767
1844
1893
-1903
-1942
-1959
1995
2114
-2150
-2209
2256
-2302
2317
-2414
-2423
2693
-2702
2736
-2948
2974
2986
3013
-3019
3197
-3300
3493
3495
3612
-3633
-3657
3702
3727
-3753
3758
4031
-4063
4131
-4172
-4284
4298
4409
4...

output:

11
11
10
11
11
11
11
12
13
13
14
14
13
15
15
15
15
15
15
14
14
15
15
14
14
14
14
14
16
15
16
15
15
16
15
15
16
15
18
17
17
15
15
16
15
15
15
16
17
16
16
16
16
15
15
16
15
16
16
16
16
16
19
17
17
16
16
17
18
17
17
17
16
18
18
16
18
17
18
18
16
17
16
17
16
16
16
16
16
18
19
17
17
17
17
18
17
17
18
17
...

result:

ok 100000 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 3908kb

input:

2 1
-13
-20

output:

7
6

result:

ok 2 lines

Test #7:

score: 0
Accepted
time: 5026ms
memory: 252488kb

input:

100000 4
76
8621794
308
92
6
34
1
483450
375193
6822
11
86577381
975813
5025
9
63600034
459
2
738030
3518
24576
42
7850
56238
40826768
1775
40118
32
2802
44344
429383
162507
1017
628933
361842
49
419
12
1593123
876
156
26178
54984
6102
8073233
109434
16
13978897
134384
5
1560478
35
145007
100827
815...

output:

15
53
20
17
6
12
1
41
49
29
8
50
39
28
6
56
21
2
45
26
37
12
32
35
-1
27
-1
11
27
38
51
37
26
40
48
14
21
7
-1
23
19
35
35
32
-1
-1
9
44
52
4
41
11
49
41
64
39
18
36
43
18
25
46
25
36
11
31
11
45
70
46
47
50
12
26
32
35
8
40
-1
23
46
30
24
41
-1
42
-1
57
34
34
57
21
30
41
10
49
23
51
3
51
41
-1
38
1...

result:

ok 100000 lines

Test #8:

score: 0
Accepted
time: 4823ms
memory: 247440kb

input:

100000 4
245352
1
523
6520
1080897
1894
11174315
206582
27800445
43672882
1960
2037
12339783
197460
3208646
224604
109172
60481043
71
232890
3519534
23453
4356
103
439
20
97
6265775
167265
177
57
26965344
2228831
35719
154
1592499
308701
2
344
19657419
2598760
49175
13
401
26
736
4275
85118178
80666...

output:

42
1
20
42
-1
25
48
40
63
72
25
25
54
49
46
38
33
67
15
42
44
43
28
15
23
10
16
45
34
17
13
64
41
40
18
54
45
2
20
59
46
34
9
21
12
22
29
71
-1
35
12
55
-1
24
44
43
49
3
31
65
15
66
16
7
20
36
37
41
24
43
38
31
-1
36
42
23
35
55
66
50
38
60
12
43
17
40
66
62
44
28
7
20
21
50
69
46
39
43
46
30
72
42
...

result:

ok 100000 lines

Test #9:

score: 0
Accepted
time: 4966ms
memory: 252576kb

input:

100000 4
889
21738495
59706
3859026
114
45
173111
6292802
2
117
13
11
13201
81386
51048924
79
42
6
26276509
36320
5621949
10
434
37
19683193
822970
6269807
50057532
9
15
24
18614267
22902213
1318
21
17403705
6828
14123
8958
2501
233101
1553
31308685
11413
73
2266252
1267501
86091802
7755
136705
20
1...

output:

22
45
33
39
16
12
49
-1
2
15
9
8
31
37
63
15
12
5
42
35
41
6
22
12
42
45
44
52
6
8
11
49
57
22
10
47
33
34
30
37
35
26
49
29
17
43
44
58
30
37
9
46
41
18
33
29
48
43
45
5
9
19
40
56
-1
17
47
62
49
1
48
43
32
30
33
42
38
15
38
14
47
39
4
37
40
43
61
38
46
45
-1
35
-1
30
40
52
30
46
39
-1
33
17
13
37
...

result:

ok 100000 lines