Submission #612545

#	Time	Username	Problem	Language	Result	Execution time	Memory
612545		fvogel499	Seats (IOI18_seats)	C++17	0 / 100	304 ms	132068 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

#define size(x) (int)((x).size())

using namespace std;

const int p2 = 1<<20;

struct SumSegtree {
    SumSegtree() {
        t = new int [p2*2];
        lz = new int [p2*2];
        cnt = new int [p2*2];
        for (int i = 0; i < p2*2; i++) {
            t[i] = 0;
            lz[i] = 0;
            cnt[i] = 1;
        }
        for (int i = p2-1; i >= 1; i--) {
            cnt[i] = cnt[i*2] + cnt[i*2+1];
        }
    }
    void push(int x, int span) {
        if (x < p2) {
            lz[x*2] += lz[x];
            lz[x*2+1] += lz[x];
        }
        t[x] += lz[x];
        // assert(t[x] >= 2);
        lz[x] = 0;
    }
    void pull(int x) {
        t[x] = min(t[x*2], t[x*2+1]);
        cnt[x] = 0;
        if (t[x] == t[x*2]) {
            cnt[x] += cnt[x*2];
        }
        if (t[x] == t[x*2+1]) {
            cnt[x] += cnt[x*2+1];
        }
    }
    void upd(int rb, int re, int rv, int qn = 1, int qb = 0, int qe = p2-1) {
        if (rb > qe || qb > re) push(qn, qe-qb+1);
        else if (rb <= qb && qe <= re) {
            lz[qn] += rv;
            push(qn, qe-qb+1);
        }
        else {
            push(qn, qe-qb+1);
            int qm = (qb+qe)/2;
            upd(rb, re, rv, qn*2, qb, qm);
            upd(rb, re, rv, qn*2+1, qm+1, qe);
            pull(qn);
        }
    }
    int get(int rb, int re, int qn = 1, int qb = 0, int qe = p2-1) {
        push(qn, qe-qb+1);
        if (rb > qe || qb > re) return 0;
        else if (rb <= qb && qe <= re) {
            // return t[qn];
            return (t[qn] == 2 ? cnt[qn] : 0);
        }
        else {
            int qm = (qb+qe)/2;
            int r = get(rb, re, qn*2, qb, qm)+get(rb, re, qn*2+1, qm+1, qe);
            pull(qn);
            return r;
        }
    }
    int* t, * lz, * cnt;
};

SumSegtree st;
int n;
vector<int> b, posOf;

void give_initial_chart(int H, int W, std::vector<int> row, std::vector<int> col) {
    st = SumSegtree();
    assert(H == 1);
    n = W;
    assert(size(row) == n && size(col) == n);
    posOf = vector<int>(n);
    for (int i = 0; i < n; i++) {
        assert(row[i] == 0);
        posOf[col[i]] = i;
    }
    b = col;
    for (int i = -1; i < n; i++) {
        int c = n;
        if (0 <= i && i < n) c = b[i];
        int d = n;
        if (0 <= i+1 && i+1 < n) d = b[i+1];
        if (c > d) swap(c, d);
        assert(c < d);
        st.upd(c, d-1, 1);
        // vector<int> curState(n, 0);
        // for (int j = 0; j < n; j++) curState[j] = st.get(j, j);
        // cout << "Case #" << i << ": ";
        // for (int j = 0; j < n; j++) {
        //     cout << curState[j] << ' ';
        // }
        // cout << endl;
        // cout << endl;
    }
}

void doit(int v, int x, int ch) {
    int secV = n;
    if (0 <= x && x < n) secV = b[x];
    if (v > secV) swap(v, secV);
    if (v < secV) st.upd(v, secV-1, ch);
}

int swap_seats(int x, int y) {
    assert(0 <= x && x < n);
    assert(0 <= y && y < n);
    if (posOf[x]+1 == posOf[y] || posOf[x]-1 == posOf[y]) {
        if (!(posOf[x]+1 == posOf[y])) {
            swap(x, y);
        }
        doit(x, posOf[x]-1, -1);
        doit(y, posOf[y]+1, -1);
        doit(x, posOf[y]+1, 1);
        doit(y, posOf[x]-1, 1);
    }
    else {doit(x, posOf[x]-1, -1);
        doit(x, posOf[x]+1, -1);
        doit(y, posOf[y]-1, -1);
        doit(y, posOf[y]+1, -1);
        doit(y, posOf[x]-1, 1);
        doit(y, posOf[x]+1, 1);
        doit(x, posOf[y]-1, 1);
        doit(x, posOf[y]+1, 1);
    }
    int res = st.get(0, n-1);
    swap(b[posOf[x]], b[posOf[y]]);
    swap(posOf[x], posOf[y]);
    return res;
}

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