Submission #800206

#	Time	Username	Problem	Language	Result	Execution time	Memory
800206		Josia	Seats (IOI18_seats)	C++17	0 / 100	366 ms	175104 KiB

seats

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



struct seg {
    struct node {
        int iMin = 1e9, iMax = -1e9, jMin = 1e9, jMax = -1e9;
    };

    node op(node a, node b) {
        node res;

        res.iMin = min(a.iMin, b.iMin);
        res.iMax = min(a.iMax, b.iMax);
        res.jMin = min(a.jMin, b.jMin);
        res.jMax = min(a.jMax, b.jMax);
        
        return res;
    }

    vector<node> tree;


    void update(int v, int rl, int rr, int pos, int i, int j) {
        if (rl == rr) {
            tree[v].iMax = i;
            tree[v].iMin = i;
            tree[v].jMax = j;
            tree[v].jMin = j;
            return;
        }

        int rm = (rl + rr)/2;

        if (pos <= rm) update(v*2, rl, rm, pos, i, j);
        else update(v*2+1, rm+1, rr, pos, i, j);

        tree[v] = op(tree[v*2], tree[v*2+1]);
    }

    node query(int v, int rl, int rr, int ql, int qr) {
        if (ql > qr) return node();
        if (rl == ql && rr == qr) return tree[v];

        int rm = (rl + rr)/2;

        return op(query(v*2, rl, rm, ql, min(rm, qr)), query(v*2+1, rm+1, rr, max(rm+1, ql), qr));
    }

    void init(int n, vector<pair<int, int>> ass) {
        tree.resize(n*4);
        for (int i = 0; i<n; i++) {
            update(1, 0, n-1, i, ass[i].first, ass[i].second);
        }
    }

};




seg tree;
int n;
vector<pair<int, int>> seating;

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    n = H*W;
    seating.resize(n);
    for (int i = 0; i<n; i++) {
        seating[i].first = R[i];
        seating[i].first = C[i];
    }
    tree.init(n, seating);
}

int swap_seats(int a, int b) {
    tree.update(1, 0, n-1, a, seating[b].first, seating[b].second);
    tree.update(1, 0, n-1, b, seating[a].first, seating[a].second);

    swap(seating[a], seating[b]);


    int res = 0;

    for (int i = 0; i<n; i++) {
        auto blub = tree.query(1, 0, n-1, 0, i);

        int field = (blub.iMax-blub.iMin+1)*(blub.jMax-blub.jMin+1);
        assert(field>i);
        if (field == i+1) res++;
        else i = field-1;
    }

    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