oj.uz

Submission #958223

# Submission time Handle Problem Language Result Execution time Memory
958223 2024-04-05T07:42:41 Z Pring Seats (IOI18_seats) C++17
100 / 100
 2075 ms 259156 KB 
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;

namespace {
    pli operator+(pli a, pli b) {
        if (a.fs < b.fs) return a;
        if (a.fs > b.fs) return b;
        return mp(a.fs, a.sc + b.sc);
    }
    const int MXN = 3000039, INF = 2e9;
    int n, h, w;
    pii pos[MXN];
    int time[MXN];

    struct SMG {
        #define mid ((l + r) >> 1)
        pli val[MXN * 4];
        ll tag[MXN * 4];
        void add_tag(int id, int l, int r, ll _t) {
            val[id].fs += _t;
            tag[id] += _t;
        }
        void push(int id, int l, int r) {
            if (tag[id] == 0) return;
            add_tag(id * 2 + 1, l, mid, tag[id]);
            add_tag(id * 2 + 2, mid, r, tag[id]);
            tag[id] = 0;
        }
        void pull(int id, int l, int r) {
            val[id] = val[id * 2 + 1] + val[id * 2 + 2];
        }
        void build(int id, int l, int r) {
            tag[id] = 0;
            if (l + 1 == r) {
                val[id] = mp(0LL, 1);
                return;
            }
            build(id * 2 + 1, l, mid);
            build(id * 2 + 2, mid, r);
            pull(id, l, r);
        }
        void modify(int id, int l, int r, int _l, int _r, int _v) {
            if (_r <= l || r <= _l) return;
            if (_l <= l && r <= _r) {
                add_tag(id, l, r, _v);
                return;
            }
            push(id, l, r);
            modify(id * 2 + 1, l, mid, _l, _r, _v);
            modify(id * 2 + 2, mid, r, _l, _r, _v);
            pull(id, l, r);
        }
        #undef mid
    } smg;

    int f(int x, int y) {
        return x * (w + 2) + y;
    }

    int f(pii p) {
        return p.fs * (w + 2) + p.sc;
    }

    void MODIFY(int x, int y, int mul) {
        int a = time[f(x, y)];
        int b = time[f(x, y + 1)];
        int c = time[f(x + 1, y)];
        int d = time[f(x + 1, y + 1)];
        if (d < c) swap(d, c);
        if (c < b) swap(c, b);
        if (b < a) swap(b, a);
        if (d < c) swap(d, c);
        if (c < b) swap(c, b);
        if (d < c) swap(d, c);
        // debug(x, y, a, b, c, d);
        if (a < b) smg.modify(0, 0, n, a, b, mul);
        if (c < d) smg.modify(0, 0, n, c, d, INF * mul);
        // auto [sml, cnt] = smg.val[0];
        // debug(sml, cnt);
    }

    void INIT() {
        FOR(i, 0, n) time[f(pos[i])] = i;
        fill(time, time + w + 2, n);
        fill(time + (w + 2) * (h + 1), time + (w + 2) * (h + 2), n);
        FOR(i, 1, h + 1) {
            time[f(i, 0)] = n;
            time[f(i, w + 1)] = n;
        }
        smg.build(0, 0, n);
        // auto [sml, cnt] = smg.val[0];
        // debug(sml, cnt);
        FOR(i, 0, h + 1) FOR(j, 0, w + 1) MODIFY(i, j, 1);
    }

    void UPD(pii p, int x) {
        MODIFY(p.fs - 1, p.sc - 1, -1);
        MODIFY(p.fs - 1, p.sc, -1);
        MODIFY(p.fs, p.sc - 1, -1);
        MODIFY(p.fs, p.sc, -1);
        time[f(p)] = x;
        MODIFY(p.fs - 1, p.sc - 1, 1);
        MODIFY(p.fs - 1, p.sc, 1);
        MODIFY(p.fs, p.sc - 1, 1);
        MODIFY(p.fs, p.sc, 1);
    }

    int CALC(int x, int y) {
        // debug(x, y);
        UPD(pos[x], y);
        UPD(pos[y], x);
        swap(pos[x], pos[y]);
        auto [sml, cnt] = smg.val[0];
        // debug(sml, cnt);
        return (sml == 4 ? cnt : 0);
    }
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    ::h = H;
    ::w = W;
    ::n = h * w;
    FOR(i, 0, h * w) pos[i] = mp(R[i] + 1, C[i] + 1);
    INIT();
}

int swap_seats(int a, int b) {
    return CALC(a, b);
}

// #ifdef MIKU
// void miku() {
// }

// int32_t main() {
//     cin.tie(0) -> sync_with_stdio(false);
//     cin.exceptions(cin.failbit);
//     miku();
//     return 0;
// }
// #endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 193452 KB Output is correct
2 Correct 36 ms 193628 KB Output is correct
3 Correct 44 ms 193620 KB Output is correct
4 Correct 36 ms 193620 KB Output is correct
5 Correct 34 ms 193616 KB Output is correct
6 Correct 41 ms 193608 KB Output is correct
7 Correct 43 ms 193616 KB Output is correct
8 Correct 39 ms 193424 KB Output is correct
9 Correct 40 ms 193456 KB Output is correct
10 Correct 45 ms 193620 KB Output is correct
11 Correct 40 ms 193616 KB Output is correct
12 Correct 35 ms 193616 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 193452 KB Output is correct
2 Correct 36 ms 193628 KB Output is correct
3 Correct 44 ms 193620 KB Output is correct
4 Correct 36 ms 193620 KB Output is correct
5 Correct 34 ms 193616 KB Output is correct
6 Correct 41 ms 193608 KB Output is correct
7 Correct 43 ms 193616 KB Output is correct
8 Correct 39 ms 193424 KB Output is correct
9 Correct 40 ms 193456 KB Output is correct
10 Correct 45 ms 193620 KB Output is correct
11 Correct 40 ms 193616 KB Output is correct
12 Correct 35 ms 193616 KB Output is correct
13 Correct 69 ms 195700 KB Output is correct
14 Correct 75 ms 195924 KB Output is correct
15 Correct 60 ms 195736 KB Output is correct
16 Correct 43 ms 195924 KB Output is correct
17 Correct 65 ms 196120 KB Output is correct
18 Correct 61 ms 195908 KB Output is correct
19 Correct 65 ms 195920 KB Output is correct
20 Correct 52 ms 195924 KB Output is correct
21 Correct 44 ms 195924 KB Output is correct
22 Correct 46 ms 195804 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1340 ms 250192 KB Output is correct
2 Correct 709 ms 250172 KB Output is correct
3 Correct 678 ms 250168 KB Output is correct
4 Correct 533 ms 250600 KB Output is correct
5 Correct 568 ms 252312 KB Output is correct
6 Correct 511 ms 250284 KB Output is correct
7 Correct 595 ms 250236 KB Output is correct
8 Correct 671 ms 250064 KB Output is correct
9 Correct 648 ms 252636 KB Output is correct
10 Correct 628 ms 252764 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 195800 KB Output is correct
2 Correct 135 ms 200360 KB Output is correct
3 Correct 561 ms 252696 KB Output is correct
4 Correct 1331 ms 252828 KB Output is correct
5 Correct 494 ms 256040 KB Output is correct
6 Correct 1175 ms 256932 KB Output is correct
7 Correct 542 ms 255728 KB Output is correct
8 Correct 694 ms 253676 KB Output is correct
9 Correct 602 ms 253916 KB Output is correct
10 Correct 598 ms 253904 KB Output is correct
11 Correct 523 ms 258004 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 195108 KB Output is correct
2 Correct 76 ms 195108 KB Output is correct
3 Correct 115 ms 195160 KB Output is correct
4 Correct 152 ms 195152 KB Output is correct
5 Correct 236 ms 197332 KB Output is correct
6 Correct 783 ms 259152 KB Output is correct
7 Correct 960 ms 258976 KB Output is correct
8 Correct 754 ms 259028 KB Output is correct
9 Correct 1730 ms 259156 KB Output is correct
10 Correct 734 ms 258908 KB Output is correct
11 Correct 743 ms 258896 KB Output is correct
12 Correct 675 ms 258908 KB Output is correct

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 193452 KB Output is correct
2 Correct 36 ms 193628 KB Output is correct
3 Correct 44 ms 193620 KB Output is correct
4 Correct 36 ms 193620 KB Output is correct
5 Correct 34 ms 193616 KB Output is correct
6 Correct 41 ms 193608 KB Output is correct
7 Correct 43 ms 193616 KB Output is correct
8 Correct 39 ms 193424 KB Output is correct
9 Correct 40 ms 193456 KB Output is correct
10 Correct 45 ms 193620 KB Output is correct
11 Correct 40 ms 193616 KB Output is correct
12 Correct 35 ms 193616 KB Output is correct
13 Correct 69 ms 195700 KB Output is correct
14 Correct 75 ms 195924 KB Output is correct
15 Correct 60 ms 195736 KB Output is correct
16 Correct 43 ms 195924 KB Output is correct
17 Correct 65 ms 196120 KB Output is correct
18 Correct 61 ms 195908 KB Output is correct
19 Correct 65 ms 195920 KB Output is correct
20 Correct 52 ms 195924 KB Output is correct
21 Correct 44 ms 195924 KB Output is correct
22 Correct 46 ms 195804 KB Output is correct
23 Correct 1340 ms 250192 KB Output is correct
24 Correct 709 ms 250172 KB Output is correct
25 Correct 678 ms 250168 KB Output is correct
26 Correct 533 ms 250600 KB Output is correct
27 Correct 568 ms 252312 KB Output is correct
28 Correct 511 ms 250284 KB Output is correct
29 Correct 595 ms 250236 KB Output is correct
30 Correct 671 ms 250064 KB Output is correct
31 Correct 648 ms 252636 KB Output is correct
32 Correct 628 ms 252764 KB Output is correct
33 Correct 66 ms 195800 KB Output is correct
34 Correct 135 ms 200360 KB Output is correct
35 Correct 561 ms 252696 KB Output is correct
36 Correct 1331 ms 252828 KB Output is correct
37 Correct 494 ms 256040 KB Output is correct
38 Correct 1175 ms 256932 KB Output is correct
39 Correct 542 ms 255728 KB Output is correct
40 Correct 694 ms 253676 KB Output is correct
41 Correct 602 ms 253916 KB Output is correct
42 Correct 598 ms 253904 KB Output is correct
43 Correct 523 ms 258004 KB Output is correct
44 Correct 52 ms 195108 KB Output is correct
45 Correct 76 ms 195108 KB Output is correct
46 Correct 115 ms 195160 KB Output is correct
47 Correct 152 ms 195152 KB Output is correct
48 Correct 236 ms 197332 KB Output is correct
49 Correct 783 ms 259152 KB Output is correct
50 Correct 960 ms 258976 KB Output is correct
51 Correct 754 ms 259028 KB Output is correct
52 Correct 1730 ms 259156 KB Output is correct
53 Correct 734 ms 258908 KB Output is correct
54 Correct 743 ms 258896 KB Output is correct
55 Correct 675 ms 258908 KB Output is correct
56 Correct 95 ms 195148 KB Output is correct
57 Correct 211 ms 195128 KB Output is correct
58 Correct 359 ms 197668 KB Output is correct
59 Correct 1135 ms 254812 KB Output is correct
60 Correct 2075 ms 254868 KB Output is correct
61 Correct 1039 ms 254868 KB Output is correct
62 Correct 800 ms 258972 KB Output is correct
63 Correct 2020 ms 257032 KB Output is correct
64 Correct 1232 ms 254800 KB Output is correct
65 Correct 1122 ms 254960 KB Output is correct
66 Correct 1171 ms 255064 KB Output is correct
67 Correct 1176 ms 254692 KB Output is correct
68 Correct 851 ms 256852 KB Output is correct
69 Correct 1764 ms 258976 KB Output is correct