Submission #1306639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306639		orzorzorz	Seats (IOI18_seats)	C++20	33 / 100	951 ms	48924 KiB

seats

#include "seats.h"
#include <vector>
#include <algorithm>

using namespace std;

int N_total;
vector<int> pos; // Stores the position of seat i
vector<int> val; // The value (time) at grid position i
int tree_min[4000005];
int tree_cnt[4000005];
int lazy[4000005];

// --- Segment Tree Functions ---
void push_up(int v) {
    tree_min[v] = min(tree_min[2 * v], tree_min[2 * v + 1]);
    tree_cnt[v] = 0;
    if (tree_min[v] == tree_min[2 * v]) tree_cnt[v] += tree_cnt[2 * v];
    if (tree_min[v] == tree_min[2 * v + 1]) tree_cnt[v] += tree_cnt[2 * v + 1];
}

void apply(int v, int add) {
    tree_min[v] += add;
    lazy[v] += add;
}

void push_down(int v) {
    if (lazy[v] != 0) {
        apply(2 * v, lazy[v]);
        apply(2 * v + 1, lazy[v]);
        lazy[v] = 0;
    }
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        tree_min[v] = 0;
        tree_cnt[v] = 1;
    } else {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        push_up(v);
    }
}

void update(int v, int tl, int tr, int l, int r, int add) {
    if (l > r) return;
    if (l == tl && r == tr) {
        apply(v, add);
    } else {
        push_down(v);
        int tm = (tl + tr) / 2;
        update(2 * v, tl, tm, l, min(r, tm), add);
        update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, add);
        push_up(v);
    }
}

// --- Logic for 1D Transitions ---
// A transition exists between pos i and i+1 for all k in [min_time, max_time - 1]
void update_transition(int i, int factor) {
    int t1 = val[i];
    int t2 = val[i + 1];
    if (t1 > t2) swap(t1, t2);
    // Transition exists when one is black and one is white: time is in [t1, t2-1]
    update(1, 0, N_total - 1, t1, t2 - 1, factor);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    // Assuming H=1 for Subtask 5. If W=1, the logic is identical.
    N_total = H * W;
    pos.resize(N_total);
    val.assign(N_total + 2, N_total); // Padding with "infinity" time
    
    for (int i = 0; i < N_total; i++) {
        // Since it's 1D, we care about the position in the row/column
        int p = (H == 1) ? C[i] : R[i];
        pos[i] = p + 1; // 1-based to allow for padding at index 0
        val[p + 1] = i;
    }

    build(1, 0, N_total - 1);

    // Initial transitions (including boundaries)
    for (int i = 0; i <= N_total; i++) {
        update_transition(i, 1);
    }
}

int swap_seats(int a, int b) {
    int p1 = pos[a];
    int p2 = pos[b];

    // Identify affected adjacent pairs
    vector<int> affected = {p1 - 1, p1, p2 - 1, p2};
    sort(affected.begin(), affected.end());
    affected.erase(unique(affected.begin(), affected.end()), affected.end());

    // 1. Remove old transition counts
    for (int p : affected) update_transition(p, -1);

    // 2. Swap
    swap(val[p1], val[p2]);
    swap(pos[a], pos[b]);

    // 3. Add new transition counts
    for (int p : affected) update_transition(p, 1);

    // The condition for a 1D rectangle is exactly 2 transitions
    if (tree_min[1] == 2) return tree_cnt[1];
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 20
• Subtask 4: 0 / 6
• Subtask 5: 33 / 33
• Subtask 6: 0 / 30