oj.uz

Submission #782574

# Submission time Handle Problem Language Result Execution time Memory
782574 2023-07-14T05:44:36 Z resting Seats (IOI18_seats) C++17
100 / 100
 3986 ms 251260 KB 
#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

#define set owo

//segment tree base
struct segtree {
    int l, r;
    segtree* lc, * rc;
    segtree* getmem();
    int mn = 0, mncnt;
    int lz = 0;
    segtree() : segtree(-1, -1) {};
    segtree(int l, int r) : l(l), r(r), mncnt(r - l + 1) {
        if (l == r) return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree(l, m);
        rc = getmem(); *rc = segtree(m + 1, r);
    }
    void apply(int x) {
        lz += x; mn += x;
    }
    void push() {
        if (l == r) return;
        lc->apply(lz); rc->apply(lz);
        lz = 0;
    }
    void pull() {
        mn = min(lc->mn, rc->mn); mncnt = 0;
        if (lc->mn == mn) mncnt += lc->mncnt;
        if (rc->mn == mn) mncnt += rc->mncnt;
    }
    void upd(int ql, int qr, int qv) {
        if (l > qr || r < ql) return;
        if (ql <= l && r <= qr) {
            apply(qv);
            return;
        }
        push();
        lc->upd(ql, qr, qv);
        rc->upd(ql, qr, qv);
        pull();
    }

    //debugging only
    int q(int v, int ad = 0) {
        ad += lz;
        if (l == r) return ad;
        if (v <= lc->r) return lc->q(v, ad);
        return rc->q(v, ad);
    }
}uwu, mem[4000005];
int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }
vector<int> r, c;
int h, w, n, dx[] = { -1, 0, 1, 0, -1, 0 }, dy[] = { 0, -1, 0, 1, 0, 0 };
vector<vector<int>> g;

bool inbound(int r, int c) {
    return r >= 0 && c >= 0 && r < h && c < w;
}

void upd(int r, int c, int t) {
    for (int i = 0; i < 4; i++) {
        int a = inbound(r + dx[i], c + dy[i]) ? g[r + dx[i]][c + dy[i]] : n;
        int b = inbound(r + dx[i + 1], c + dy[i + 1]) ? g[r + dx[i + 1]][c + dy[i + 1]] : n;
        if (a > g[r][c] && b > g[r][c]) {
            uwu.upd(g[r][c], n - 1, t);
            uwu.upd(min(a, b), n - 1, -t);
        }
        if (a < g[r][c] && b < g[r][c]) {
            uwu.upd(max(a, b), n - 1, t);
            uwu.upd(g[r][c], n - 1, -t);
        }
    }
}

void set(int r, int c, int v) {
    for (int i = 1; i < 6; i++) {
        if (!inbound(r + dx[i], c + dy[i])) continue;
        upd(r + dx[i], c + dy[i], -1);
    }
    g[r][c] = v;
    for (int i = 1; i < 6; i++) {
        if (!inbound(r + dx[i], c + dy[i])) continue;
        upd(r + dx[i], c + dy[i], 1);
    }
}


void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H * W; h = H; w = W; r = R; c = C;
    uwu = segtree(0, n - 1);
    g = vector<vector<int>>(H, vector<int>(W, 0));
    for (int i = 0; i < n; i++) {
        g[r[i]][c[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        upd(r[i], c[i], 1);
    }
}

int swap_seats(int a, int b) {
    set(r[a], c[a], b);
    set(r[b], c[b], a);
    swap(r[a], r[b]);
    swap(c[a], c[b]);
    return uwu.mncnt;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 156912 KB Output is correct
2 Correct 79 ms 156928 KB Output is correct
3 Correct 88 ms 157004 KB Output is correct
4 Correct 78 ms 156948 KB Output is correct
5 Correct 79 ms 156928 KB Output is correct
6 Correct 82 ms 156968 KB Output is correct
7 Correct 86 ms 157004 KB Output is correct
8 Correct 92 ms 156940 KB Output is correct
9 Correct 85 ms 157008 KB Output is correct
10 Correct 86 ms 156984 KB Output is correct
11 Correct 82 ms 157004 KB Output is correct
12 Correct 72 ms 157008 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 156912 KB Output is correct
2 Correct 79 ms 156928 KB Output is correct
3 Correct 88 ms 157004 KB Output is correct
4 Correct 78 ms 156948 KB Output is correct
5 Correct 79 ms 156928 KB Output is correct
6 Correct 82 ms 156968 KB Output is correct
7 Correct 86 ms 157004 KB Output is correct
8 Correct 92 ms 156940 KB Output is correct
9 Correct 85 ms 157008 KB Output is correct
10 Correct 86 ms 156984 KB Output is correct
11 Correct 82 ms 157004 KB Output is correct
12 Correct 72 ms 157008 KB Output is correct
13 Correct 132 ms 157276 KB Output is correct
14 Correct 136 ms 157260 KB Output is correct
15 Correct 97 ms 157324 KB Output is correct
16 Correct 91 ms 157808 KB Output is correct
17 Correct 117 ms 157300 KB Output is correct
18 Correct 139 ms 157284 KB Output is correct
19 Correct 117 ms 157336 KB Output is correct
20 Correct 104 ms 157516 KB Output is correct
21 Correct 92 ms 157304 KB Output is correct
22 Correct 97 ms 157804 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2432 ms 184336 KB Output is correct
2 Correct 1025 ms 184332 KB Output is correct
3 Correct 930 ms 200328 KB Output is correct
4 Correct 963 ms 200328 KB Output is correct
5 Correct 995 ms 200320 KB Output is correct
6 Correct 972 ms 200332 KB Output is correct
7 Correct 978 ms 200268 KB Output is correct
8 Correct 952 ms 200324 KB Output is correct
9 Correct 950 ms 200324 KB Output is correct
10 Correct 974 ms 200320 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 157160 KB Output is correct
2 Correct 232 ms 159428 KB Output is correct
3 Correct 966 ms 184784 KB Output is correct
4 Correct 2450 ms 200324 KB Output is correct
5 Correct 863 ms 204224 KB Output is correct
6 Correct 1793 ms 251260 KB Output is correct
7 Correct 956 ms 201500 KB Output is correct
8 Correct 1010 ms 200328 KB Output is correct
9 Correct 970 ms 200672 KB Output is correct
10 Correct 979 ms 203424 KB Output is correct
11 Correct 948 ms 223764 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 157852 KB Output is correct
2 Correct 161 ms 157844 KB Output is correct
3 Correct 236 ms 157952 KB Output is correct
4 Correct 314 ms 158064 KB Output is correct
5 Correct 405 ms 158328 KB Output is correct
6 Correct 1362 ms 188932 KB Output is correct
7 Correct 1459 ms 189260 KB Output is correct
8 Correct 1344 ms 188804 KB Output is correct
9 Correct 2137 ms 188656 KB Output is correct
10 Correct 1307 ms 205140 KB Output is correct
11 Correct 1334 ms 205140 KB Output is correct
12 Correct 1273 ms 205088 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 156912 KB Output is correct
2 Correct 79 ms 156928 KB Output is correct
3 Correct 88 ms 157004 KB Output is correct
4 Correct 78 ms 156948 KB Output is correct
5 Correct 79 ms 156928 KB Output is correct
6 Correct 82 ms 156968 KB Output is correct
7 Correct 86 ms 157004 KB Output is correct
8 Correct 92 ms 156940 KB Output is correct
9 Correct 85 ms 157008 KB Output is correct
10 Correct 86 ms 156984 KB Output is correct
11 Correct 82 ms 157004 KB Output is correct
12 Correct 72 ms 157008 KB Output is correct
13 Correct 132 ms 157276 KB Output is correct
14 Correct 136 ms 157260 KB Output is correct
15 Correct 97 ms 157324 KB Output is correct
16 Correct 91 ms 157808 KB Output is correct
17 Correct 117 ms 157300 KB Output is correct
18 Correct 139 ms 157284 KB Output is correct
19 Correct 117 ms 157336 KB Output is correct
20 Correct 104 ms 157516 KB Output is correct
21 Correct 92 ms 157304 KB Output is correct
22 Correct 97 ms 157804 KB Output is correct
23 Correct 2432 ms 184336 KB Output is correct
24 Correct 1025 ms 184332 KB Output is correct
25 Correct 930 ms 200328 KB Output is correct
26 Correct 963 ms 200328 KB Output is correct
27 Correct 995 ms 200320 KB Output is correct
28 Correct 972 ms 200332 KB Output is correct
29 Correct 978 ms 200268 KB Output is correct
30 Correct 952 ms 200324 KB Output is correct
31 Correct 950 ms 200324 KB Output is correct
32 Correct 974 ms 200320 KB Output is correct
33 Correct 128 ms 157160 KB Output is correct
34 Correct 232 ms 159428 KB Output is correct
35 Correct 966 ms 184784 KB Output is correct
36 Correct 2450 ms 200324 KB Output is correct
37 Correct 863 ms 204224 KB Output is correct
38 Correct 1793 ms 251260 KB Output is correct
39 Correct 956 ms 201500 KB Output is correct
40 Correct 1010 ms 200328 KB Output is correct
41 Correct 970 ms 200672 KB Output is correct
42 Correct 979 ms 203424 KB Output is correct
43 Correct 948 ms 223764 KB Output is correct
44 Correct 94 ms 157852 KB Output is correct
45 Correct 161 ms 157844 KB Output is correct
46 Correct 236 ms 157952 KB Output is correct
47 Correct 314 ms 158064 KB Output is correct
48 Correct 405 ms 158328 KB Output is correct
49 Correct 1362 ms 188932 KB Output is correct
50 Correct 1459 ms 189260 KB Output is correct
51 Correct 1344 ms 188804 KB Output is correct
52 Correct 2137 ms 188656 KB Output is correct
53 Correct 1307 ms 205140 KB Output is correct
54 Correct 1334 ms 205140 KB Output is correct
55 Correct 1273 ms 205088 KB Output is correct
56 Correct 209 ms 158472 KB Output is correct
57 Correct 402 ms 158484 KB Output is correct
58 Correct 675 ms 158856 KB Output is correct
59 Correct 1975 ms 201348 KB Output is correct
60 Correct 3986 ms 201276 KB Output is correct
61 Correct 1771 ms 201396 KB Output is correct
62 Correct 1524 ms 203136 KB Output is correct
63 Correct 3414 ms 202424 KB Output is correct
64 Correct 2005 ms 201612 KB Output is correct
65 Correct 1781 ms 201260 KB Output is correct
66 Correct 1963 ms 201524 KB Output is correct
67 Correct 2045 ms 204356 KB Output is correct
68 Correct 1706 ms 215572 KB Output is correct
69 Correct 3431 ms 224684 KB Output is correct