Submission #1198397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198397		Zicrus	Seats (IOI18_seats)	C++17	0 / 100	132 ms	16176 KiB

seats

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

typedef long long ll;

struct segment_tree {
    ll n, nt;
    vector<ll> tree, cnt, laz;

    void recalc(ll i) {
        if (i >= nt) return;
        if (tree[2*i] < tree[2*i+1]) {
            tree[i] = tree[2*i];
            cnt[i] = cnt[2*i];
        }
        else if (tree[2*i] > tree[2*i+1]) {
            tree[i] = tree[2*i+1];
            cnt[i] = cnt[2*i+1];
        }
        else {
            tree[i] = tree[2*i];
            cnt[i] = cnt[2*i] + cnt[2*i+1];
        }
    }

    void prop(ll i) {
        tree[i] += laz[i];
        if (i < nt) {
            laz[2*i] += laz[i];
            laz[2*i+1] += laz[i];
        }
        laz[i] = 0;
    }
    
    segment_tree() { }
    segment_tree(ll n, vector<ll> &a) : n(n) {
        nt = 1;
        while (nt < n) nt *= 2;
        tree = laz = vector<ll>(2*nt);
        cnt = vector<ll>(2*nt, 1);
        for (ll i = 0; i < n; i++) tree[nt+i] = a[i];
        for (ll i = nt-1; i > 0; i--) recalc(i);
    }

    ll global_cnt() {
        return tree[1] > 2 ? 0 : cnt[1];
    }

    void range_add(ll k, ll tl, ll tr, ll l, ll r, ll val) {
        prop(k);
        if (r < tl || l > tr) return;
        if (l <= tl && r >= tr) {
            laz[k] += val;
            prop(k);
            return;
        }
        ll mid = (tl + tr) / 2;
        range_add(2*k, tl, mid, l, r, val);
        range_add(2*k+1, mid+1, tr, l, r, val);
        recalc(k);
    }
    void range_add(ll l, ll r, ll val) { return range_add(1, 0, nt-1, l, r, val); }

    void print(ll k) {
        prop(k);
        if (k >= nt) {
            cerr << tree[k] << ' ';
        }
        else {
            print(2*k);
            print(2*k+1);
        }
        if (k == 1) cerr << endl;
    }
};

ll h, w;
vector<ll> pos, val;
segment_tree tree;

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    h = H; w = W;
    pos = vector<ll>(w);
    val = vector<ll>(w+2, 1ll << 62ll);
    for (ll i = 0; i < w; i++) {
        pos[i] = C[i];
        val[pos[i]+1] = i;
    }

    vector<ll> a(w, 2);
    vector<bool> state(w+2);
    state[pos[0]+1] = true;
    for (ll i = 1; i < w; i++) {
        ll p = pos[i]+1;
        a[i] = a[i-1];
        ll &cur = a[i];
        cur -= (state[p-1] != state[p]) + (state[p] != state[p+1]);
        state[p] = true;
        cur += (state[p-1] != state[p]) + (state[p] != state[p+1]);
    }
    tree = segment_tree(w, a);
}

pair<ll, ll> range(ll x, ll y) {
    return {min(val[x], val[y]), max(val[x], val[y])-1};
}

int swap_seats(int A, int B) {
    ll a = A, b = B;
    ll pa = pos[a]+1, pb = pos[b]+1;

    {
        auto al = range(pa-1, pa);
        auto ar = range(pa, pa+1);
        auto bl = range(pb-1, pb);
        auto br = range(pb, pb+1);
        tree.range_add(al.first, al.second, -1);
        tree.range_add(ar.first, ar.second, -1);
        if (bl != ar) tree.range_add(bl.first, bl.second, -1);
        if (br != al) tree.range_add(br.first, br.second, -1);
    }
    swap(pos[a], pos[b]);
    swap(val[pa], val[pb]);
    {
        auto al = range(pa-1, pa);
        auto ar = range(pa, pa+1);
        auto bl = range(pb-1, pb);
        auto br = range(pb, pb+1);
        tree.range_add(al.first, al.second, 1);
        tree.range_add(ar.first, ar.second, 1);
        if (bl != ar) tree.range_add(bl.first, bl.second, 1);
        if (br != al) tree.range_add(br.first, br.second, 1);
    }

    return tree.global_cnt();
}

#ifdef TEST
#include "grader.cpp"
#endif

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