Submission #926766

#	Time	Username	Problem	Language	Result	Execution time	Memory
926766		efishel	Seats (IOI18_seats)	C++17	0 / 100	206 ms	262144 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()) {}

    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 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);
    }

    void tour (ll l, ll r, ll id) {
        push(l, r, id);
        if (l == r) {
            cerr << l << ": " << tree[id].minN << '\n';
            return;
        }
        tour(l, mid, id+1);
        tour(mid+1, r, id+off);
    }

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

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

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;
    st.update(ve[0], n-1, 1, 0, n-1, 0);
    for (ll i = 1; i < n; i++) {
        ll l = min(ve[i-1], ve[i]);
        ll r = max(ve[i-1], ve[i])-1;
        st.update(l, r, 1, 0, n-1, 0);
    }
    st.update(ve[n-1], n-1, 1, 0, n-1, 0);
}

ll 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());
}

// int main () {
//     cin.tie(nullptr) -> sync_with_stdio(false);
//     int n;
//     cin >> n;
//     int ve[n];
//     for (ll i = 0; i < n; i++) cin >> ve[i];
//     int AA[4] = { 0, 0, 0, 0 };
//     give_initial_chart(1, n, AA, ve);
//     cout << st.query() << '\n';
//     st.tour(0, n-1, 0);
//     ll Q;
//     cin >> Q;
//     while (Q--) {
//         ll a, b;
//         cin >> a >> b;
//         cout << swap_seats(a, b) << '\n';
//         st.tour(0, n-1, 0);
//         cout.flush();
//         cerr.flush();
//     }
//     return 0;
// }

/*/

9
6 1 4 5 2 3 0 7 8
0->6->0
1->1
4->2->4
5->3->5
7->7
8->8

5 6 4 1 3 7 2 0 8
5 6 4 7 3 1 2 0 8
7 6 4 5 3 1 2 0 8

/*/

Compilation message (stderr)

seats.cpp: In function 'll change(ll, ll)':
seats.cpp:107:1: warning: no return statement in function returning non-void [-Wreturn-type]
  107 | }
      | ^

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