Submission #926777

#	Time	Username	Problem	Language	Result	Execution time	Memory
926777		efishel	Seats (IOI18_seats)	C++17	33 / 100	1729 ms	94804 KiB

seats

// #include "seats.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

#define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
    struct Node {
        ll minN;
        ll cou;
        bool hasL;
        ll lazy;

        Node (): minN(0), cou(1), hasL(false), lazy(0) {} // idem. lazy init

        Node operator+ (const Node& o) {
            Node ans;
            ans.minN = min(minN, o.minN);
            if (minN == o.minN) ans.cou = cou + o.cou;
            else if (minN < o.minN) ans.cou = cou;
            else ans.cou = o.cou;
            return ans;
        }
    };

    vector <Node> tree;

    SegTree (ll n): tree(2*n, Node()) {
        build(0, n-1, 0);
    }

    void push (ll l, ll r, ll id) {
        if (!tree[id].hasL) return;
        tree[id].minN += tree[id].lazy;
        if (l < r) {
            tree[id+1].lazy += tree[id].lazy;
            tree[id+1].hasL = true;
            tree[id+off].lazy += tree[id].lazy;
            tree[id+off].hasL = true;
        }
        tree[id].hasL = false;
        tree[id].lazy = 0; // 0 is idem.
    }

    void pull (ll l, ll r, ll id) {
        tree[id] = tree[id+1] + tree[id+off];
    }

    void build (ll l, ll r, ll id) {
        if (l >= r) return;
        build(l, mid, id+1);
        build(mid+1, r, id+off);
        pull(l, r, id);
    }

    void update (ll ql, ll qr, ll val, ll l, ll r, ll id) {
        push(l, r, id);
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            tree[id].lazy += val;
            tree[id].hasL = true;
            push(l, r, id);
            return;
        }
        update(ql, qr, val, l, mid, id+1);
        update(ql, qr, val, mid+1, r, id+off);
        pull(l, r, id);
    }

    ll query () {
        assert(tree[0].minN == 2);
        return tree[0].cou;
    }
};

SegTree st(0);
ll n;
vll ve2;
vll ve;

void change (ll i, ll val) {
    // border between ve[i-1] and ve[i]
    ll l = min(i>0 ? ve[i-1] : n, i<n ? ve[i] : n);
    ll r = max(i>0 ? ve[i-1] : n, i<n ? ve[i] : n)-1;
    st.update(l, r, val, 0, n-1, 0);
}

int swap_seats (int a, int b) {
    ll atA = ve2[a];
    ll atB = ve2[b];
    change(atA, -1);
    change(atA+1, -1);
    change(atB, -1);
    change(atB+1, -1);
    swap(ve2[a], ve2[b]);
    swap(ve[atA], ve[atB]);
    change(atA, 1);
    change(atA+1, 1);
    change(atB, 1);
    change(atB+1, 1);
    return int(st.query());
}

void give_initial_chart (int _, int n, vector <int> __, vector <int> ve2) {
    ::n = n;
    ::ve.resize(n);
    ::ve2.resize(n);
    for (ll i = 0; i < n; i++) {
        ve[ve2[i]] = i;
        ::ve2[i] = ve2[i];
    }
    st.tree = SegTree(n).tree;
    for (ll i = 0; i <= n; i++) {
        change(i, 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