Submission #394011

#	Time	Username	Problem	Language	Result	Execution time	Memory
394011		phathnv	Seats (IOI18_seats)	C++11	70 / 100	4064 ms	118232 KiB

seats

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

using namespace std;

struct Node{
    int minVal, cntMin;
    Node(int x = 0, int cnt = 1){
        minVal = x;
        cntMin = cnt;
    }
    void update(int x){
        minVal += x;
    }
    Node operator + (const Node &oth){
        if (minVal < oth.minVal)
            return *this;
        if (minVal > oth.minVal)
            return oth;
        return Node(minVal, cntMin + oth.cntMin);
    }
};

struct SegmentTree{
    int n;
    int lazy[4000007];
    Node d[4000007];
    void init(int _n){
        n = _n;
    }
    void doLazy(int id, int l, int r){
        d[id].update(lazy[id]);
        if (l < r){
            lazy[id << 1] += lazy[id];
            lazy[id << 1 | 1] += lazy[id];
        }
        lazy[id] = 0;
    }
    void update(int id, int l, int r, int u, int v, int val){
        doLazy(id, l, r);
        if (v < l || r < u)
            return;
        if (u <= l && r <= v){
            lazy[id] += val;
            doLazy(id, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid + 1, r, u, v, val);
        d[id] = d[id << 1] + d[id << 1 | 1];
    }
    void update(int pos, int val){
        update(1, 0, n - 1, pos, n - 1, val);
    }
    int getCnt(){
        doLazy(1, 0, n - 1);
        assert(d[1].minVal == 4);
        return d[1].cntMin;
    }
} st;

int h, w, tmp[4], nTmp;
vector<vector<int>> chair;
vector<int> x, y;

bool inSide(int x, int y){
    return (0 <= x && x < h && 0 <= y && y < w);
}

void UpdateSquare(int x, int y, int type){
    nTmp = 0;
    for(int dx = 0; dx < 2; dx++)
        for(int dy = 0; dy < 2; dy++)
            if (inSide(x + dx, y + dy))
                tmp[nTmp++] = chair[x + dx][y + dy];
    sort(tmp, tmp + nTmp);
    for(int i = 0; i < nTmp; i++){
        st.update(tmp[i], type);
        type *= -1;
    }
}

void give_initial_chart(int hh, int ww, vector<int> r, vector<int> c) {
    h = hh;
    w = ww;
    x = r;
    y = c;
    chair.assign(h, vector<int>(w, 0));
    for(int i = 0; i < w * h; i++)
        chair[r[i]][c[i]] = i;
    st.init(h * w);
    for(int i = -1; i < h; i++)
        for(int j = -1; j < w; j++)
            UpdateSquare(i, j, 1);
}

int swap_seats(int a, int b) {
    for(int dx = -1; dx < 1; dx++)
        for(int dy = -1; dy < 1; dy++){
            UpdateSquare(x[a] + dx, y[a] + dy, -1);
            UpdateSquare(x[b] + dx, y[b] + dy, -1);
        }
    swap(chair[x[a]][y[a]], chair[x[b]][y[b]]);
    swap(x[a], x[b]);
    swap(y[a], y[b]);
    for(int dx = -1; dx < 1; dx++)
        for(int dy = -1; dy < 1; dy++){
            UpdateSquare(x[a] + dx, y[a] + dy, +1);
            UpdateSquare(x[b] + dx, y[b] + dy, +1);
        }
    return st.getCnt();
}

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