QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#120615#1154. WombatsQwerty1232#0 525ms14796kbC++173.8kb2023-07-07 01:16:082024-05-26 02:55:57

Judging History

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

  • [2024-05-26 02:55:57]
  • 评测
  • 测评结果:0
  • 用时:525ms
  • 内存:14796kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 01:16:08]
  • 提交

answer

#include "wombats.h"

#include <bits/stdc++.h>

constexpr int inf = 1e9 + 1;
int n, m;

struct Cum {
    std::vector<int> L;
    std::vector<std::vector<int>> data;

    std::vector<std::vector<int>> v, h;
    int len;

    Cum() {
        len = 0;
    }
    Cum(std::vector<int> v, std::vector<int> h) {
        len = 1;
        L = v;
        this->v.push_back(v);
        this->h.push_back(h);
        return;

        assert(v.size() == m);
        assert(h.size() == m - 1);
        std::vector<int> ph(m);
        std::partial_sum(h.begin(), h.end(), ph.begin() + 1);
        data.assign(m, std::vector<int>(m));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                data[i][j] = abs(ph[i] - ph[j]);
            }
        }
    }
};

Cum fuck(Cum a) {
    if (a.len == -1) {
        return a;
    }
    int l = a.len;
    Cum res;
    res.len = -1;
    res.data.resize(m);
    res.L = a.L;
    for (int i = 0; i < m; i++) {
        std::vector<int> dp(m, inf);
        dp[i] = 0;
        auto shit = [&](auto& h) {
            for (int j = 1; j < m; j++) {
                dp[j] = std::min(dp[j], dp[j - 1] + h[j - 1]);
            }
            for (int j = m - 2; j >= 0; j--) {
                dp[j] = std::min(dp[j], dp[j + 1] + h[j]);
            }
        };
        shit(a.h[0]);
        for (int j = 1; j < l; j++) {
            for (int t = 0; t < m; t++) {
                dp[t] += a.v[j][t];
            }
            shit(a.h[j]);
        }
        res.data[i] = dp;
    }
    return res;
}

Cum merge(Cum a, Cum b) {
    if (!a.len || !b.len) {
        return a.len ? a : b;
    }
    if (a.len == -1 || b.len == -1) {
        if (a.len != -1) {
            a = fuck(a);
        }
        if (b.len != -1) {
            b = fuck(b);
        }
    } else {
        a.L = b.L;
        a.len += b.len;
        a.v.insert(a.v.end(), b.v.begin(), b.v.end());
        a.h.insert(a.h.end(), b.h.begin(), b.h.end());
        if (a.len > 1) {
            a = fuck(a);
        }
        return a;
    }
    Cum res;
    res.len = -1;
    res.L = a.L;
    res.data.assign(m, std::vector<int>(m, inf));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            for (int t = 0; t < m; t++) {
                res.data[i][t] = std::min(res.data[i][t], a.data[i][j] + b.L[j] + b.data[j][t]);
            }
        }
    }
    return res;
}

std::vector<std::vector<int>> h, v;

int size;
std::vector<Cum> data;

void build() {
    for (size = 1; size < n; size *= 2)
        ;
    data.resize(2 * size);
    for (int i = 0; i < n; i++) {
        data[size + i] = Cum(v[i], h[i]);
    }
    for (int i = size - 1; i > 0; i--) {
        data[i] = merge(data[2 * i], data[2 * i + 1]);
    }
}

void update(int i) {
    data[i + size] = Cum(v[i], h[i]);
    i += size;
    for (i >>= 1; i > 0; i >>= 1) {
        data[i] = merge(data[2 * i], data[2 * i + 1]);
    }
}

void init(int r, int c, int H[5000][200], int V[5000][200]) {
    n = r;
    m = c;
    h.assign(n, std::vector<int>(m - 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m - 1; j++) {
            h[i][j] = H[i][j];
        }
    }
    v.assign(n, std::vector<int>(m));
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m; j++) {
            v[i + 1][j] = V[i][j];
        }
    }
    build();
}

void changeH(int p, int q, int w) {
    h[p][q] = w;
    update(p);
}

void changeV(int p, int q, int w) {
    v[p + 1][q] = w;
    update(p + 1);
}

int escape(int v1, int v2) {
    if (data[1].len != -1) {
        data[1] = fuck(data[1]);
    }

    int res = data[1].data[v1][v2];
    return res;
    // return 42;
}

詳細信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 9
Accepted
time: 3ms
memory: 11796kb

input:

5000 1
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...

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 500 lines

Test #2:

score: 0
Wrong Answer
time: 7ms
memory: 11904kb

input:

4999 1
447
741
689
474
539
506
732
156
94
221
858
311
318
930
146
187
13
881
960
441
480
653
504
999
274
251
772
626
944
822
314
881
695
235
952
241
204
347
821
392
641
146
316
410
305
658
977
748
363
387
550
611
991
287
105
927
679
460
660
952
310
680
669
697
768
30
25
979
743
20
624
174
877
928
46...

output:

2517633
2517633
2517783
2517783
2517783
2517783
2518327
2519367
2519367
2518623
2518623
2518635
2518635
2518635
2518671
2518333
2518521
2517343
2517343
2516891
2516891
2518399
2518399
2518121
2518121
2518121
2517711
2518419
2518051
2518051
2518051
2518051
2518413
2518969
2518583
2518583
2518583
2519...

result:

wrong answer 1st lines differ - expected: '2499534', found: '2517633'

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 1ms
memory: 5940kb

input:

20 20
1 1 1 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0
0 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 1 1 1
0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 0 1 0
0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1
0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 0 0
1 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0
1 1 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0
0 0 0 1 1 0 0 1 0 0 1 1 1 0 ...

output:

1
1
3
2
2
0
2
3
2
1
2
2
3
2
2
2
1
1
3
2
3
1
1
1
0
4
0
1
3
1
1
1
1
2
3
1
1
4
0
1
2
1
2
1
1
2
2
0
2
2
1
2
3
2
2
1
2
1
1
3
3
0
0
2
1
2
2
5
1
2
0
0
4
4
2
1
2
2
1
2
2
1
2
0
0
1
1
2
2
3
1
2
1
1
4
2
1
0
2
1
3
1
1
0
1
3
2
1
1
1
0
1
2
2
2
2
1
2
1
1
1
3
1
1
2
0
2
1
2
2
1
2
3
2
1
1
1
3
3
1
3
0
0
3
1
3
4
1
1
2
...

result:

wrong answer 1st lines differ - expected: '2', found: '1'

Subtask #3:

score: 0
Wrong Answer

Test #18:

score: 0
Wrong Answer
time: 525ms
memory: 10564kb

input:

99 100
278 927 579 441 245 179 75 110 797 424 854 825 213 194 8 666 556 81 205 126 225 882 913 85 319 94 784 83 486 391 262 251 623 746 706 453 842 242 414 876 885 88 175 334 971 539 90 860 11 32 402 776 314 301 966 800 744 20 777 681 535 55 191 1 773 503 55 223 285 3 136 505 644 175 686 454 2 818 3...

output:

24854
26323
31410
28597
34651
25173
30998
29528
29479
30436
26264
27994
28144
26380
28096
29519
28035
28912
33832
26534
34475
40963
26029
31290
29570
36335
25464
26288
27469
30714
34614
30720
31047
27456
31245
42217
27185
29345
27641
30145
27501
36467
27125
30330
29165
27198
31924
33389
30011
27324
...

result:

wrong answer 1st lines differ - expected: '34137', found: '24854'

Subtask #4:

score: 0
Wrong Answer

Test #25:

score: 0
Wrong Answer
time: 11ms
memory: 14796kb

input:

4999 2
57
194
293
623
704
290
534
103
734
55
774
398
571
972
268
57
567
207
425
914
855
650
38
540
496
242
353
263
889
192
216
416
414
54
80
451
456
956
809
169
909
394
244
936
77
180
653
263
338
732
752
739
250
759
738
450
431
243
50
897
790
606
389
146
148
878
611
707
802
623
187
98
653
244
127
75...

output:

1994772
1994755
1994715
1994812
1994772
1994755
1993502
1993405
1993445
1993462
1993395
1993492
1993395
1993492
1993702
1993605
1993605
1993702
1993605
1993702
1993645
1993662
1993605
1993702
1993605
1993702
1993605
1993702
1993662
1993645
1993702
1993605
1993605
1993702
1993630
1993533
1993590
1993...

result:

wrong answer 1st lines differ - expected: '2116460', found: '1994772'

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%