Submission #1199128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199128		fv3	Seats (IOI18_seats)	C++20	33 / 100	549 ms	49020 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "/home/fv3/prog/debug/debug.h"
#else
#define debug(...) 42
#endif

struct segtree {
    int nt = 1;
    vector<int> mn, cnt, add;

    void init(int N, vector<int> &a, vector<int> &p) {
        while (nt < N) {
            nt <<= 1;
        }

        mn = vector<int>(2*nt, 1 << 30);
        cnt = vector<int>(2*nt, 1);
        add = vector<int>(2*nt);

        mn[nt] = 2;
        for (int i = 1; i < N; i++) {
            mn[nt+i] = mn[nt+i-1];

            if (a[p[i]-1] < i) {
                mn[nt+i]--;
            } else {
                mn[nt+i]++;
            }
            if (a[p[i]+1] < i) {
                mn[nt+i]--;
            } else {
                mn[nt+i]++;
            }
        }

        for (int i = nt-1; i >= 1; i--) {
            merge(i, i*2, i*2|1);
        }
    }

    void prop(int k) {
        mn[k] += add[k];
        if (k < nt) {
            add[k*2] += add[k];
            add[k*2|1] += add[k];
        }
        add[k] = 0;
    }

    void update(int l, int r, int k, int tl, int tr, int val) {
        prop(k);
        if (tl > r || tr < l) return;
        if (tl >= l && tr <= r) {
            add[k] += val;
            prop(k);
            return;
        }
        int c = (tl + tr) / 2;
        update(l, r, k*2, tl, c, val);
        update(l, r, k*2|1, c+1, tr, val);

        merge(k, k*2, k*2|1);
    }

    void merge(int i, int c1, int c2) {
        if (mn[c1] == mn[c2]) {
            cnt[i] = cnt[c1] + cnt[c2];
        } else if (mn[c1] < mn[c2]) {
            cnt[i] = cnt[c1];
        } else {
            cnt[i] = cnt[c2];
        }
        mn[i] = min(mn[c1], mn[c2]);
    }
};

vector<vector<int>> m;
vector<int> a, pos;
int N;

segtree st;

void give_initial_chart(int H_, int W_, vector<int> R_, vector<int> C_)  {
    N = W_; // H = 1
    a = vector<int>(N+2, N);
    for (int i = 0; i < N; i++) {
        a[C_[i]+1] = i;
    }
    
    pos = C_;
    for (auto &e : pos) {
        e++;
    }
    st.init(N, a, pos);
}

int swap_seats(int u, int v)  {
    // TODO: Handle case where u and v are adjacent
    st.update(min(a[pos[u]-1], u), max(a[pos[u]-1], u)-1, 1, 0, st.nt-1, -1);
    st.update(min(a[pos[u]+1], u), max(a[pos[u]+1], u)-1, 1, 0, st.nt-1, -1);

    st.update(min(a[pos[v]-1], v), max(a[pos[v]-1], v)-1, 1, 0, st.nt-1, -1);
    st.update(min(a[pos[v]+1], v), max(a[pos[v]+1], v)-1, 1, 0, st.nt-1, -1);

    swap(a[pos[u]], a[pos[v]]);
    swap(pos[u], pos[v]);

    st.update(min(a[pos[u]-1], u), max(a[pos[u]-1], u)-1, 1, 0, st.nt-1, 1);
    st.update(min(a[pos[u]+1], u), max(a[pos[u]+1], u)-1, 1, 0, st.nt-1, 1);

    st.update(min(a[pos[v]-1], v), max(a[pos[v]-1], v)-1, 1, 0, st.nt-1, 1);
    st.update(min(a[pos[v]+1], v), max(a[pos[v]+1], v)-1, 1, 0, st.nt-1, 1);

    return st.cnt[1];
}

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