oj.uz

Submission #611022

# Submission time Handle Problem Language Result Execution time Memory
611022 2022-07-29T00:53:33 Z skittles1412 Seats (IOI18_seats) C++17
100 / 100
 1596 ms 139548 KB 
#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

const int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};

struct Node {
    int mn, cnt;

    void apply_lazy(int x) {
        mn += x;
    }

    Node operator+(const Node& n) const {
        if (mn < n.mn) {
            return *this;
        } else if (n.mn < mn) {
            return n;
        }
        return {mn, cnt + n.cnt};
    }
};

struct DS {
    int n;
    vector<Node> v;
    vector<int> lazy;

    DS() {}
    DS(int n): n(n), v(4 * n, {0, 1}), lazy(4 * n) {
        build(1, 0, n - 1);
    }

    void build(int o, int l, int r) {
        if (l == r) {
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        v[o] = v[lc] + v[rc];
    }

    void update(int o, int l, int r, int ql, int qr, int x) {
        if (ql <= l && r <= qr) {
            lazy[o] += x;
            v[o].apply_lazy(x);
            return;
        }
        int mid = (l + r) / 2, lc = o * 2, rc = lc + 1;
        if (ql <= mid) {
            update(lc, l, mid, ql, qr, x);
        }
        if (mid < qr) {
            update(rc, mid + 1, r, ql, qr, x);
        }
        v[o] = v[lc] + v[rc];
        v[o].apply_lazy(lazy[o]);
    }

    void update(int l, int r, int x) {
        if (l > r) {
            return;
        }
        update(1, 0, n - 1, l, r, x);
    }

    int query() const {
        return v[1].cnt;
    }
} ds;

int n, m;
vector<vector<int>> arr;
vector<pair<int, int>> pos;

bool ibs(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

void update1(int x, int y, int v) {
    int ans = n * m;
    auto go = [&](int x, int y) -> void {
        if (ibs(x, y)) {
            ans = min(ans, arr[x][y]);
        }
    };
    go(x - 1, y);
    go(x, y - 1);
    ds.update(arr[x][y], ans - 1, v);
}

void update2(int x, int y, int v) {
    int adj[4];
    for (int i = 0; i < 4; i++) {
        int cx = x + dx[i], cy = y + dy[i];
        if (ibs(cx, cy)) {
            adj[i] = arr[cx][cy];
        } else {
            adj[i] = 1e9;
        }
    }
    sort(begin(adj), end(adj));
    ds.update(adj[1], arr[x][y] - 1, v);
}

void update(int x, int y, int v) {
    update1(x, y, v);
    update2(x, y, v);
}

void set_pos(int u) {
    auto& [x, y] = pos[u];
    arr[x][y] = u;
}

void give_initial_chart(int _n, int _m, vector<int> r, vector<int> c) {
    n = _n;
    m = _m;
    ds = DS(n * m);
    pos.resize(n * m);
    arr.resize(n, vector<int>(m));
    for (int i = 0; i < n * m; i++) {
        pos[i] = {r[i], c[i]};
        set_pos(i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            update(i, j, 1);
        }
    }
}

int swap_seats(int u, int v) {
    set<pair<int, int>> changed;
    for (auto& [x, y] : {pos[u], pos[v]}) {
        changed.emplace(x, y);
        for (int i = 0; i < 4; i++) {
            int cx = x + dx[i], cy = y + dy[i];
            if (ibs(cx, cy)) {
                changed.emplace(cx, cy);
            }
        }
    }
    for (auto& [x, y] : changed) {
        update(x, y, -1);
    }
    swap(pos[u], pos[v]);
    set_pos(u);
    set_pos(v);
    for (auto& [x, y] : changed) {
        update(x, y, 1);
    }
    return ds.query();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 15 ms 340 KB Output is correct
3 Correct 22 ms 424 KB Output is correct
4 Correct 14 ms 400 KB Output is correct
5 Correct 8 ms 480 KB Output is correct
6 Correct 20 ms 460 KB Output is correct
7 Correct 20 ms 436 KB Output is correct
8 Correct 20 ms 436 KB Output is correct
9 Correct 17 ms 424 KB Output is correct
10 Correct 20 ms 432 KB Output is correct
11 Correct 18 ms 456 KB Output is correct
12 Correct 14 ms 396 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 15 ms 340 KB Output is correct
3 Correct 22 ms 424 KB Output is correct
4 Correct 14 ms 400 KB Output is correct
5 Correct 8 ms 480 KB Output is correct
6 Correct 20 ms 460 KB Output is correct
7 Correct 20 ms 436 KB Output is correct
8 Correct 20 ms 436 KB Output is correct
9 Correct 17 ms 424 KB Output is correct
10 Correct 20 ms 432 KB Output is correct
11 Correct 18 ms 456 KB Output is correct
12 Correct 14 ms 396 KB Output is correct
13 Correct 39 ms 1236 KB Output is correct
14 Correct 46 ms 1256 KB Output is correct
15 Correct 28 ms 1296 KB Output is correct
16 Correct 14 ms 1788 KB Output is correct
17 Correct 36 ms 1272 KB Output is correct
18 Correct 30 ms 1236 KB Output is correct
19 Correct 29 ms 1296 KB Output is correct
20 Correct 30 ms 1516 KB Output is correct
21 Correct 21 ms 1316 KB Output is correct
22 Correct 29 ms 1764 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 958 ms 74756 KB Output is correct
2 Correct 505 ms 74888 KB Output is correct
3 Correct 633 ms 74876 KB Output is correct
4 Correct 440 ms 81696 KB Output is correct
5 Correct 525 ms 81756 KB Output is correct
6 Correct 653 ms 81788 KB Output is correct
7 Correct 647 ms 81840 KB Output is correct
8 Correct 580 ms 81992 KB Output is correct
9 Correct 607 ms 81836 KB Output is correct
10 Correct 513 ms 81760 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 1020 KB Output is correct
2 Correct 86 ms 7296 KB Output is correct
3 Correct 503 ms 75204 KB Output is correct
4 Correct 951 ms 75132 KB Output is correct
5 Correct 456 ms 86312 KB Output is correct
6 Correct 995 ms 139548 KB Output is correct
7 Correct 460 ms 90024 KB Output is correct
8 Correct 679 ms 88768 KB Output is correct
9 Correct 619 ms 88992 KB Output is correct
10 Correct 511 ms 91900 KB Output is correct
11 Correct 465 ms 112256 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1352 KB Output is correct
2 Correct 70 ms 1340 KB Output is correct
3 Correct 114 ms 1600 KB Output is correct
4 Correct 137 ms 1580 KB Output is correct
5 Correct 218 ms 2300 KB Output is correct
6 Correct 727 ms 79456 KB Output is correct
7 Correct 834 ms 87720 KB Output is correct
8 Correct 765 ms 87548 KB Output is correct
9 Correct 1177 ms 87556 KB Output is correct
10 Correct 638 ms 87528 KB Output is correct
11 Correct 657 ms 95540 KB Output is correct
12 Correct 402 ms 95532 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 340 KB Output is correct
2 Correct 15 ms 340 KB Output is correct
3 Correct 22 ms 424 KB Output is correct
4 Correct 14 ms 400 KB Output is correct
5 Correct 8 ms 480 KB Output is correct
6 Correct 20 ms 460 KB Output is correct
7 Correct 20 ms 436 KB Output is correct
8 Correct 20 ms 436 KB Output is correct
9 Correct 17 ms 424 KB Output is correct
10 Correct 20 ms 432 KB Output is correct
11 Correct 18 ms 456 KB Output is correct
12 Correct 14 ms 396 KB Output is correct
13 Correct 39 ms 1236 KB Output is correct
14 Correct 46 ms 1256 KB Output is correct
15 Correct 28 ms 1296 KB Output is correct
16 Correct 14 ms 1788 KB Output is correct
17 Correct 36 ms 1272 KB Output is correct
18 Correct 30 ms 1236 KB Output is correct
19 Correct 29 ms 1296 KB Output is correct
20 Correct 30 ms 1516 KB Output is correct
21 Correct 21 ms 1316 KB Output is correct
22 Correct 29 ms 1764 KB Output is correct
23 Correct 958 ms 74756 KB Output is correct
24 Correct 505 ms 74888 KB Output is correct
25 Correct 633 ms 74876 KB Output is correct
26 Correct 440 ms 81696 KB Output is correct
27 Correct 525 ms 81756 KB Output is correct
28 Correct 653 ms 81788 KB Output is correct
29 Correct 647 ms 81840 KB Output is correct
30 Correct 580 ms 81992 KB Output is correct
31 Correct 607 ms 81836 KB Output is correct
32 Correct 513 ms 81760 KB Output is correct
33 Correct 38 ms 1020 KB Output is correct
34 Correct 86 ms 7296 KB Output is correct
35 Correct 503 ms 75204 KB Output is correct
36 Correct 951 ms 75132 KB Output is correct
37 Correct 456 ms 86312 KB Output is correct
38 Correct 995 ms 139548 KB Output is correct
39 Correct 460 ms 90024 KB Output is correct
40 Correct 679 ms 88768 KB Output is correct
41 Correct 619 ms 88992 KB Output is correct
42 Correct 511 ms 91900 KB Output is correct
43 Correct 465 ms 112256 KB Output is correct
44 Correct 35 ms 1352 KB Output is correct
45 Correct 70 ms 1340 KB Output is correct
46 Correct 114 ms 1600 KB Output is correct
47 Correct 137 ms 1580 KB Output is correct
48 Correct 218 ms 2300 KB Output is correct
49 Correct 727 ms 79456 KB Output is correct
50 Correct 834 ms 87720 KB Output is correct
51 Correct 765 ms 87548 KB Output is correct
52 Correct 1177 ms 87556 KB Output is correct
53 Correct 638 ms 87528 KB Output is correct
54 Correct 657 ms 95540 KB Output is correct
55 Correct 402 ms 95532 KB Output is correct
56 Correct 107 ms 1968 KB Output is correct
57 Correct 211 ms 2000 KB Output is correct
58 Correct 300 ms 2760 KB Output is correct
59 Correct 1129 ms 91664 KB Output is correct
60 Correct 1596 ms 90396 KB Output is correct
61 Correct 763 ms 91664 KB Output is correct
62 Correct 729 ms 93180 KB Output is correct
63 Correct 1517 ms 92852 KB Output is correct
64 Correct 1027 ms 91936 KB Output is correct
65 Correct 927 ms 91660 KB Output is correct
66 Correct 1112 ms 92016 KB Output is correct
67 Correct 917 ms 94748 KB Output is correct
68 Correct 740 ms 105912 KB Output is correct
69 Correct 1509 ms 115108 KB Output is correct