Submission #779958

#	Time	Username	Problem	Language	Result	Execution time	Memory
779958		GusterGoose27	Seats (IOI18_seats)	C++17	0 / 100	179 ms	32200 KiB

seats

// #pragma GCC optimize("Ofast")

#include "seats.h"

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6+5;
int points[MAXN];
bool active[MAXN];
int n;
typedef pair<int, int> pii;

pii comb(pii &a, pii &b) {
    if (a.first != b.first) return min(a, b);
    return pii(a.first, a.second+b.second);
}

class stree {
public:
    int lp, rp;
    stree *l = nullptr;
    stree *r = nullptr;
    pii mn = pii(0, 1);
    int lz = 0;
    stree(int lv, int rv) {
        lp = lv;
        rp = rv;
        if (lp < rp) {
            int m = (lp+rp)/2;
            l = new stree(lp, m);
            r = new stree(m+1, rp);
            mn = comb(l->mn, r->mn);
        }
    }
    void set_lz(int v) {
        lz += v;
        mn.first += v;
    }
    void prop() {
        if (lz == 0) return;
        assert(l);
        l->set_lz(lz);
        r->set_lz(lz);
        lz = 0;
    }
    void upd(int lv, int rv, int v) {
        if (lp > rv || rp < lv) return;
        if (lp >= lv && rp <= rv) {
            return set_lz(v);
        }
        prop();
        l->upd(lv, rv, v);
        r->upd(lv, rv, v);
        mn = comb(l->mn, r->mn);
    }
};

stree *tree;

void make(int i, bool unmake) {
    if (active[i] != unmake) return;
    active[i] ^= 1;
    int mult = (unmake) ? -1 : 1;
    bool lcomp = (i == 0) ? 1 : points[i-1] > points[i];
    bool rcomp = (i == n-1) ? 1 : points[i+1] > points[i];
    if (lcomp && rcomp) tree->upd(0, points[i]-1, -mult);
    if (!lcomp && !rcomp) tree->upd(0, points[i]-1, mult);
}

void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    n = W;
    assert(H == 1);
    for (int i = 0; i < n; i++) {
        points[i] = C[i];
        assert(R[i] == 0);
    }
    tree = new stree(0, n-1);
    for (int i = 0; i < n; i++) make(i, 0);
}

int swap_seats(int a, int b) {
    for (int i = max(0, a-1); i <= min(n-1, a+1); i++) make(i, 1);
    for (int i = max(0, b-1); i <= min(n-1, b+1); i++) make(i, 1);
    swap(points[a], points[b]);
    for (int i = max(0, a-1); i <= min(n-1, a+1); i++) make(i, 0);
    for (int i = max(0, b-1); i <= min(n-1, b+1); i++) make(i, 0);
    assert(tree->mn.first == 0);
    assert(tree->mn.second >= 2);
    return tree->mn.second;
}

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