Submission #612502

#	Time	Username	Problem	Language	Result	Execution time	Memory
612502		fvogel499	Seats (IOI18_seats)	C++17	0 / 100	268 ms	98148 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];
        for (int i = 0; i < p2*2; i++) {
            t[i] = 0;
            lz[i] = 0;
        }
    }
    void push(int x, int span) {
        if (x < p2) {
            lz[x*2] ^= lz[x];
            lz[x*2+1] ^= lz[x];
        }
        if (lz[x]) {
            t[x] = span-t[x];
            lz[x] = 0;
        }
    }
    void pull(int x) {
        t[x] = t[x*2] + t[x*2+1];
    }
    void upd(int rb, int re, 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] ^= 1;
            push(qn, qe-qb+1);
        }
        else {
            push(qn, qe-qb+1);
            int qm = (qb+qe)/2;
            upd(rb, re, qn*2, qb, qm);
            upd(rb, re, 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];
        }
        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;
        }
    }
    void set(int x, int val) {
        int cur = get(x, x);
        if (cur != val) {
            upd(x, x);
        }
    }
    int* t, * lz;
};

struct MaxSegtree {
    MaxSegtree() {
        t = new int [p2*2];
        for (int i = 0; i < p2*2; i++) {
            t[i] = -1;
        }
    }
    void upd(int x, int v) {
        x += p2;
        t[x] = v;
        for (x /= 2; x; x /= 2) {
            t[x] = max(t[x*2], t[x*2+1]);
        }
    }
    int get(int b, int e) {
        int r = -1;
        b += p2;
        e += p2;
        while (b <= e) {
            if (b%2 == 1) {
                r = max(r, t[b]);
                b++;
            }
            if (e%2 == 0) {
                r = max(r, t[e]);
                e--;
            }
            b /= 2;
            e /= 2;
        }
        return r;
    }
    int* t;
};

SumSegtree sumST = SumSegtree();
MaxSegtree maxST = MaxSegtree();
int n;
vector<int> posOf;

void give_initial_chart(int H, int W, std::vector<int> row, std::vector<int> col) {
    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;
    }
    int range [2] = {posOf[0], posOf[0]};
    for (int i = 0; i < n; i++) {
        range[0] = min(range[0], posOf[i]);
        range[1] = max(range[1], posOf[i]);
        sumST.set(i, (range[1]-range[0] == i));
    }
    int log = sumST.get(0, p2-1);
    for (int i = 0; i < n; i++) {
        maxST.upd(posOf[i], i);
    }
}

int swap_seats(int a, int b) {
    assert(a >= 0 && a < n && b >= 0 && b < n);
    if (a > b) swap(a, b);
    assert(a < b);
    if (a <= b-1) {
        sumST.upd(a, b-1);
    }
    int lft = min(posOf[a], posOf[b]);
    int rgt = max(posOf[a], posOf[b]);
    if (lft+1 <= rgt-1) {
        int len = (rgt-1)-(lft+1)+2;
        if (max(a, maxST.get(lft+1, rgt-1)) == len-1) {
            sumST.set(len-1, 1);
        }
        else {
            sumST.set(len-1, 0);
        }
    }
    sumST.set(0, 1);
    int res = sumST.get(0, p2-1);
    maxST.upd(posOf[a], b);
    maxST.upd(posOf[b], a);
    swap(posOf[a], posOf[b]);
    return res;
}

Compilation message (stderr)

seats.cpp: In function 'void give_initial_chart(int, int, std::vector<int>, std::vector<int>)':
seats.cpp:123:9: warning: unused variable 'log' [-Wunused-variable]
  123 |     int log = sumST.get(0, p2-1);
      |         ^~~

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