CSES - Datatähti 2024 loppu

CSES - Datatähti 2024 loppu - Results

Submission details
Task:	Retkeily
Sender:	vgtcross
Submission time:	2024-01-20 14:01:43 +0200
Language:	C++ (C++20)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	10
#2	ACCEPTED	15
#3	ACCEPTED	25
#4	ACCEPTED	50

Test results
test	verdict	time	group
#1	ACCEPTED	0.00 s	1, 2, 3, 4	details
#2	ACCEPTED	0.00 s	1, 2, 3, 4	details
#3	ACCEPTED	0.00 s	1, 2, 3, 4	details
#4	ACCEPTED	0.00 s	1, 2, 3, 4	details
#5	ACCEPTED	0.00 s	1, 2, 3, 4	details
#6	ACCEPTED	0.00 s	1, 2, 4	details
#7	ACCEPTED	0.00 s	1, 2, 4	details
#8	ACCEPTED	0.01 s	1, 2, 3, 4	details
#9	ACCEPTED	0.00 s	1, 2, 4	details
#10	ACCEPTED	0.01 s	1, 2, 3, 4	details
#11	ACCEPTED	0.00 s	1, 2, 4	details
#12	ACCEPTED	0.00 s	1, 2, 4	details
#13	ACCEPTED	0.01 s	1, 2, 4	details
#14	ACCEPTED	0.01 s	1, 2, 4	details
#15	ACCEPTED	0.01 s	1, 2, 4	details
#16	ACCEPTED	0.01 s	2, 4	details
#17	ACCEPTED	0.02 s	2, 4	details
#18	ACCEPTED	0.02 s	2, 4	details
#19	ACCEPTED	0.09 s	2, 3, 4	details
#20	ACCEPTED	0.10 s	2, 4	details
#21	ACCEPTED	0.18 s	2, 3, 4	details
#22	ACCEPTED	0.00 s	1, 3, 4	details
#23	ACCEPTED	0.01 s	1, 3, 4	details
#24	ACCEPTED	0.04 s	3, 4	details
#25	ACCEPTED	0.54 s	3, 4	details
#26	ACCEPTED	0.54 s	3, 4	details
#27	ACCEPTED	0.54 s	3, 4	details
#28	ACCEPTED	0.54 s	3, 4	details
#29	ACCEPTED	0.00 s	1, 4	details
#30	ACCEPTED	0.00 s	1, 4	details
#31	ACCEPTED	0.01 s	1, 4	details
#32	ACCEPTED	0.01 s	1, 4	details
#33	ACCEPTED	0.01 s	1, 4	details
#34	ACCEPTED	0.01 s	1, 4	details
#35	ACCEPTED	0.00 s	1, 4	details
#36	ACCEPTED	0.01 s	1, 4	details
#37	ACCEPTED	0.05 s	4	details
#38	ACCEPTED	0.67 s	4	details
#39	ACCEPTED	0.68 s	4	details
#40	ACCEPTED	0.67 s	4	details
#41	ACCEPTED	0.30 s	4	details

Code

#include <bits/stdc++.h>

#define all(x) begin(x),end(x)
#define fi first
#define se second

using namespace std;
using ll = long long;
using pic = pair<int, char>;
using pii = pair<int, int>;

struct segtree {
    int l, r, m;
    segtree *lc = nullptr, *rc = nullptr;
    int v = -1e9;

    segtree(int L, int R) : l(L), r(R) {
        m = (l + r) / 2;
        if (l == r) return;
        lc = new segtree(l, m);
        rc = new segtree(m+1, r);
    }

    void point_upd(int i, int u) {
        if (l == i && i == r) {
            v = max(v, u);
            return;
        }
        if (i <= m) lc->point_upd(i, u);
        else rc->point_upd(i, u);
        v = max(lc->v, rc->v);
    }

    int range_max(int L, int R) {
        if (L > R) return -1e9;
        if (l == L && r == R) return v;
        return max(lc->range_max(L, min(R, m)), rc->range_max(max(m+1, L), R));
    }

    void clear() {
        for (auto u : {lc, rc}) if (u != nullptr) {
            u->clear();
            delete u;
        }
    }
};

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

    vector<array<int, 5>> pts(n+m);
    vector<int> yv(n+m);
    for (int i = 0; i < n; ++i) {
        cin >> pts[i][0] >> pts[i][1];
        yv[i] = pts[i][1];
        pts[i][2] = i;
        pts[i][3] = 0;
    }
    for (int i = n; i < n+m; ++i) {
        cin >> pts[i][0] >> pts[i][1];
        yv[i] = pts[i][1];
        pts[i][2] = i-n;
        pts[i][3] = 1;
    }
    sort(all(pts), [](array<int, 5> &a, array<int, 5> &b) {
        return a[1] < b[1];
    });
    sort(all(yv));
    pts[0][4] = 0;
    for (int i = 1; i < n+m; ++i) pts[i][4] = pts[i-1][4] + (pts[i][1] != pts[i-1][1]);
    int w = pts[n+m-1][4];
    sort(all(pts));
    segtree left(0, w), right(0, w);
    vector<int> dis(m, 1e9);
    for (auto &p : pts) {
        if (p[3] == 0) {
            left.point_upd(p[4], p[0] + p[1]);
            right.point_upd(p[4], p[0] - p[1]);
        } else {
            dis[p[2]] = min(dis[p[2]], p[0] + p[1] - left.range_max(0, p[4]));
            dis[p[2]] = min(dis[p[2]], p[0] - p[1] - right.range_max(p[4], w));
        }
    }
    left.clear();
    right.clear();
    left = segtree(0, w);
    right = segtree(0, w);
    reverse(all(pts));
    for (auto &p : pts) {
        if (p[3] == 0) {
            left.point_upd(p[4], - p[0] + p[1]);
            right.point_upd(p[4], - p[0] - p[1]);
        } else {
            dis[p[2]] = min(dis[p[2]], - p[0] + p[1] - left.range_max(0, p[4]));
            dis[p[2]] = min(dis[p[2]], - p[0] - p[1] - right.range_max(p[4], w));
        }
    }
    left.clear();
    right.clear();

    cout << *max_element(all(dis)) << '\n';
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);

    solve();

    return 0;
}

Test details

Test 1

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`1 1 6 6 8 9` view save

correct output
`5` view save

user output
`5` view save

Test 2

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`5 5 5 10 8 10 1 2 4 10 ...` view save

correct output
`4` view save

user output
`4` view save

Test 3

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`10 10 5 2 1 10 6 10 5 5 ...` view save

correct output
`5` view save

user output
`5` view save

Test 4

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`10 5 6 1 8 9 3 2 6 6 ...` view save

correct output
`3` view save

user output
`3` view save

Test 5

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`5 10 10 10 6 2 10 9 8 7 ...` view save

correct output
`7` view save

user output
`7` view save

Test 6

Group: 1, 2, 4

Verdict: ACCEPTED

input
`1 1 55 68 28 42` view save

correct output
`53` view save

user output
`53` view save

Test 7

Group: 1, 2, 4

Verdict: ACCEPTED

input
`100 100 52 56 58 96 3 99 18 1 ...` view save

correct output
`20` view save

user output
`20` view save

Test 8

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`1000 100 60 40 68 47 30 32 74 52 ...` view save

correct output
`5` view save

user output
`5` view save

Test 9

Group: 1, 2, 4

Verdict: ACCEPTED

input
`100 1000 44 26 18 81 18 6 83 90 ...` view save

correct output
`20` view save

user output
`20` view save

Test 10

Group: 1, 2, 3, 4

Verdict: ACCEPTED

input
`1000 1000 15 13 23 79 81 43 30 40 ...` view save

correct output
`7` view save

user output
`7` view save

Test 11

Group: 1, 2, 4

Verdict: ACCEPTED

input
`1 1 948 495 227 149` view save

correct output
`1067` view save

user output
`1067` view save

Test 12

Group: 1, 2, 4

Verdict: ACCEPTED

input
`100 100 114 530 748 841 612 709 810 232 ...` view save

correct output
`203` view save

user output
`203` view save

Test 13

Group: 1, 2, 4

Verdict: ACCEPTED

input
`1000 100 225 82 265 691 978 367 993 396 ...` view save

correct output
`50` view save

user output
`50` view save

Test 14

Group: 1, 2, 4

Verdict: ACCEPTED

input
`100 1000 848 668 189 716 451 80 626 973 ...` view save

correct output
`192` view save

user output
`192` view save

Test 15

Group: 1, 2, 4

Verdict: ACCEPTED

input
`1000 1000 931 656 382 809 666 609 1000 923 ...` view save

correct output
`66` view save

user output
`66` view save

Test 16

Group: 2, 4

Verdict: ACCEPTED

input
`10000 1000 961 158 561 313 991 125 821 964 ...` view save

correct output
`18` view save

user output
`18` view save

Test 17

Group: 2, 4

Verdict: ACCEPTED

input
`1000 10000 428 1000 485 958 46 915 582 127 ...` view save

correct output
`67` view save

user output
`67` view save

Test 18

Group: 2, 4

Verdict: ACCEPTED

input
`10000 10000 503 849 367 829 448 926 362 512 ...` view save

correct output
`22` view save

user output
`22` view save

Test 19

Group: 2, 3, 4

Verdict: ACCEPTED

input
`100000 10000 111 705 808 24 69 858 961 122 ...` view save

correct output
`7` view save

user output
`7` view save

Test 20

Group: 2, 4

Verdict: ACCEPTED

input
`10000 100000 844 874 339 315 819 918 627 936 ...` view save

correct output
`27` view save

user output
`27` view save

Test 21

Group: 2, 3, 4

Verdict: ACCEPTED

input
`100000 100000 100 468 303 899 784 458 505 54 ...` view save

correct output
`8` view save

user output
`8` view save

Test 22

Group: 1, 3, 4

Verdict: ACCEPTED

input
`10 10 451219 220496 369161 161920 241139 700531 811276 993633 ...` view save

correct output
`10` view save

user output
`10` view save

Test 23

Group: 1, 3, 4

Verdict: ACCEPTED

input
`1000 1000 337358 113599 674585 852084 717817 983395 895431 391144 ...` view save

correct output
`10` view save

user output
`10` view save

Test 24

Group: 3, 4

Verdict: ACCEPTED

input
`10000 10000 636432 664736 341727 37864 469264 360610 545785 879043 ...` view save

correct output
`10` view save

user output
`10` view save

Test 25

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 750315 55215 550921 465416 435380 742666 288479 495099 ...` view save

correct output
`7` view save

user output
`7` view save

Test 26

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 416825 677767 347155 162523 602643 936386 181956 517732 ...` view save

correct output
`8` view save

user output
`8` view save

Test 27

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 155202 457283 421100 55104 604625 136495 841749 569346 ...` view save

correct output
`9` view save

user output
`9` view save

Test 28

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 290146 808578 489810 268578 956361 635214 939844 534435 ...` view save

correct output
`10` view save

user output
`10` view save

Test 29

Group: 1, 4

Verdict: ACCEPTED

input
`10 10 668880 791821 226050 188133 859493 736633 290460 838926 ...` view save

correct output
`342068` view save

user output
`342068` view save

Test 30

Group: 1, 4

Verdict: ACCEPTED

input
`100 100 729367 697755 338457 742774 535371 701216 93743 555995 ...` view save

correct output
`285526` view save

user output
`285526` view save

Test 31

Group: 1, 4

Verdict: ACCEPTED

input
`100 1000 50870 539657 476809 462765 311713 355546 901838 829393 ...` view save

correct output
`255789` view save

user output
`255789` view save

Test 32

Group: 1, 4

Verdict: ACCEPTED

input
`1000 100 182415 659794 581623 510256 594984 525993 367726 938015 ...` view save

correct output
`50501` view save

user output
`50501` view save

Test 33

Group: 1, 4

Verdict: ACCEPTED

input
`1000 1000 668976 422918 350791 933024 893307 88057 278098 13847 ...` view save

correct output
`57897` view save

user output
`57897` view save

Test 34

Group: 1, 4

Verdict: ACCEPTED

input
`1000 1000 701742 116334 278337 368995 187245 133297 273083 369187 ...` view save

correct output
`60537` view save

user output
`60537` view save

Test 35

Group: 1, 4

Verdict: ACCEPTED

input
`10 10 693836 74759 61731 520849 666762 45364 559335 979511 ...` view save

correct output
`417182` view save

user output
`417182` view save

Test 36

Group: 1, 4

Verdict: ACCEPTED

input
`1000 1000 207572 43521 513003 683552 58800 253576 16541 558695 ...` view save

correct output
`69609` view save

user output
`69609` view save

Test 37

Group: 4

Verdict: ACCEPTED

input
`10000 10000 89066 605574 504488 66068 959128 348414 68004 849599 ...` view save

correct output
`22936` view save

user output
`22936` view save

Test 38

Group: 4

Verdict: ACCEPTED

input
`100000 100000 20824 214259 463783 904059 603615 769692 789080 399093 ...` view save

correct output
`8070` view save

user output
`8070` view save

Test 39

Group: 4

Verdict: ACCEPTED

input
`100000 100000 811424 464350 336948 946495 204883 914446 171888 431769 ...` view save

correct output
`8240` view save

user output
`8240` view save

Test 40

Group: 4

Verdict: ACCEPTED

input
`100000 100000 850810 902354 292608 63461 223139 188900 197760 995048 ...` view save

correct output
`7769` view save

user output
`7769` view save

Test 41

Group: 4

Verdict: ACCEPTED

input
`100000 100000 1 1 1 2 1 3 1 4 ...` view save

correct output
`1899999` view save

user output
`1899999` view save

Datatähti 2024 loppu

Retkeily

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Tasks

Submissions (vgtcross)