oj.uz

Submission #964612

# Submission time Handle Problem Language Result Execution time Memory
964612 2024-04-17T08:06:12 Z fve5 Seats (IOI18_seats) C++17
5 / 100
 4000 ms 93124 KB 
#include <bits/stdc++.h>
#include "seats.h"
using namespace std;

typedef long long i64;

struct Info {
    i64 mi;
    int cnt;
};

Info merge(const Info &a, const Info &b) {
    if (a.mi < b.mi)
        return a;
    if (b.mi < a.mi)
        return b;
    return {a.mi, a.cnt + b.cnt};
}

class SegTree {
    vector<Info> arr;
    vector<i64> lazy;
    int s;

    void push(int n, int nb, int ne) {
        if (!lazy[n]) return;

        arr[n].mi += lazy[n];
        if (nb + 1 != ne) {
            lazy[2 * n] += lazy[n];
            lazy[2 * n + 1] += lazy[n];
        }

        lazy[n] = 0;
    }

    void update(int l, int r, i64 d, int n, int nb, int ne) {
        push(n, nb, ne);
        if (ne <= l || nb >= r) return;
        if (l <= nb && ne <= r) {
            lazy[n] = d;
            push(n, nb, ne);
            return;
        }

        update(l, r, d, 2 * n, nb, (nb + ne) / 2);
        update(l, r, d, 2 * n + 1, (nb + ne) / 2, ne);

        arr[n] = merge(arr[2 * n], arr[2 * n + 1]);
    }

    Info query(int l, int r, int n, int nb, int ne) {
        push(n, nb, ne);
        if (ne <= l || nb >= r) return {(i64)1e18, 1};
        if (l <= nb && ne <= r) return arr[n];

        return merge(
            query(l, r, 2 * n, nb, (nb + ne) / 2),
            query(l, r, 2 * n + 1, (nb + ne) / 2, ne));
    }

public:

    void update(int l, int r, i64 d) { update(l, r, d, 1, 0, s); }
    int query(int l, int r) { return query(l, r, 1, 0, s).cnt; }

    SegTree() { }
    SegTree(int N) {
        s = 1 << (int)ceil(log2(N));
        arr.resize(2 * s, {0, 1});
        lazy.resize(2 * s);

        for (int i = s - 1; i > 0; i--)
            arr[i] = merge(arr[2 * i], arr[2 * i + 1]);
    }
};

#define GOOD_SQUARE_VALUE 1
#define BAD_SQUARE_VALUE ((int)1e7)

int H, W;
vector<vector<int>> grid;
vector<pair<int, int>> pos;

SegTree segtree;

bool get_status(int i, int j, int t) {
    if (i < 0 || j < 0 || i >= H || j >= W)
        return false;
    return grid[i][j] <= t;
}

int get_square_value(int x, int y, int dx, int dy, int t) {
    int cnt = get_status(x, y, t) + get_status(x + dx, y, t)
            + get_status(x, y + dy, t) + get_status(x + dx, y + dy, t);

    switch (cnt) {
    case 1: return GOOD_SQUARE_VALUE;
    case 3: return BAD_SQUARE_VALUE;
    default: return 0;
    }
}

void do_update(int idx, bool rev = false) {
    auto [x, y] = pos[idx];

    int factor = rev ? -1 : +1;
    i64 upd = 0;

    // Remove old squares
    for (auto dx: {-1, +1})
        for (auto dy: {-1, +1})
            upd -= get_square_value(x, y, dx, dy, idx - 1) * factor;

    // Add new squares
    for (auto dx: {-1, +1})
        for (auto dy: {-1, +1})
            upd += get_square_value(x, y, dx, dy, idx) * factor;

    // Push to segment
    segtree.update(idx, H * W, upd);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    ::H = H, ::W = W;
    grid.assign(H, vector<int>(W));
    pos.resize(H * W);

    for (int i = 0; i < H * W; i++) {
        pos[i] = {R[i], C[i]};
        grid[R[i]][C[i]] = i;
    }

    segtree = SegTree(H * W);

    for (int i = 0; i < H * W; i++) {
        do_update(i);
    }
}

int swap_seats(int a, int b) {
    /*for (auto c: {a, b})
        for (int x = max(0, pos[c].first - 1); x <= min(H - 1, pos[c].first + 1); x++)
            for (int y = max(0, pos[c].second - 1); y <= min(W - 1, pos[c].second + 1); y++)
                do_update(grid[x][y], true);*/

    for (int i = 0; i < H * W; i++)
        do_update(i, true);

    swap(pos[a], pos[b]);
    grid[pos[a].first][pos[a].second] = a;
    grid[pos[b].first][pos[b].second] = b;

    /*for (auto c: {a, b})
        for (int x = max(0, pos[c].first - 1); x <= min(H - 1, pos[c].first + 1); x++)
            for (int y = max(0, pos[c].second - 1); y <= min(W - 1, pos[c].second + 1); y++)
                do_update(grid[x][y]);*/

    for (int i = 0; i < H * W; i++)
        do_update(i);

    return segtree.query(0, H * W);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 740 KB Output is correct
2 Correct 55 ms 592 KB Output is correct
3 Correct 191 ms 548 KB Output is correct
4 Correct 157 ms 568 KB Output is correct
5 Correct 169 ms 592 KB Output is correct
6 Correct 173 ms 540 KB Output is correct
7 Correct 190 ms 536 KB Output is correct
8 Correct 137 ms 808 KB Output is correct
9 Correct 123 ms 544 KB Output is correct
10 Correct 210 ms 592 KB Output is correct
11 Correct 185 ms 808 KB Output is correct
12 Correct 176 ms 784 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 740 KB Output is correct
2 Correct 55 ms 592 KB Output is correct
3 Correct 191 ms 548 KB Output is correct
4 Correct 157 ms 568 KB Output is correct
5 Correct 169 ms 592 KB Output is correct
6 Correct 173 ms 540 KB Output is correct
7 Correct 190 ms 536 KB Output is correct
8 Correct 137 ms 808 KB Output is correct
9 Correct 123 ms 544 KB Output is correct
10 Correct 210 ms 592 KB Output is correct
11 Correct 185 ms 808 KB Output is correct
12 Correct 176 ms 784 KB Output is correct
13 Execution timed out 4043 ms 1628 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4050 ms 93124 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4032 ms 1632 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1904 KB Output is correct
2 Correct 123 ms 1960 KB Output is correct
3 Correct 1729 ms 2136 KB Output is correct
4 Execution timed out 4019 ms 1616 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 740 KB Output is correct
2 Correct 55 ms 592 KB Output is correct
3 Correct 191 ms 548 KB Output is correct
4 Correct 157 ms 568 KB Output is correct
5 Correct 169 ms 592 KB Output is correct
6 Correct 173 ms 540 KB Output is correct
7 Correct 190 ms 536 KB Output is correct
8 Correct 137 ms 808 KB Output is correct
9 Correct 123 ms 544 KB Output is correct
10 Correct 210 ms 592 KB Output is correct
11 Correct 185 ms 808 KB Output is correct
12 Correct 176 ms 784 KB Output is correct
13 Execution timed out 4043 ms 1628 KB Time limit exceeded
14 Halted 0 ms 0 KB -