제출 #393864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393864		phathnv	자리 배치 (IOI18_seats)	C++11	33 / 100	2296 ms	71372 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;
    vector<int> lazy;
    vector<Node> d;
    void build(int id, int l, int r){
        lazy[id] = 0;
        if (l == r){
            d[id] = Node(0, 1);
            return;
        }
        int mid = (l + r) >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        d[id] = d[id << 1] + d[id << 1 | 1];
    }
    void init(int _n){
        n = _n;
        d.assign(n * 4 + 1, Node(0, 1));
        lazy.assign(n * 4 + 1, 0);
    }
    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 == 2);
        return d[1].cntMin;
    }
} st;

int n;
vector<int> val, pos;

void updateLink(int l, int type){
    int r = l + 1;
    if (l < 0) {
        st.update(val[r], type);
    } else if (r >= n) {
        st.update(val[l], type);
    } else {
        st.update(min(val[l], val[r]), type);
        st.update(max(val[l], val[r]), -type);
    }
}

void give_initial_chart(int h, int w, vector<int> r, vector<int> c) {
    assert(h == 1);
    n = w;
    val.resize(n);
    pos.resize(n);
    pos = c;
    for(int i = 0; i < n; i++)
        val[pos[i]] = i;
    st.init(n);
    for(int i = 0; i <= n; i++)
        updateLink(i - 1, +1);
}

int swap_seats(int a, int b) {
    updateLink(pos[a] - 1, -1);
    updateLink(pos[a], -1);
    updateLink(pos[b] - 1, -1);
    updateLink(pos[b], -1);
    assert(val[pos[a]] == a);
    assert(val[pos[b]] == b);
    swap(val[pos[a]], val[pos[b]]);
    swap(pos[a], pos[b]);
    updateLink(pos[a] - 1, +1);
    updateLink(pos[a], +1);
    updateLink(pos[b] - 1, +1);
    updateLink(pos[b], +1);
//    cerr << "val: ";
//    for(int x : val)
//        cerr << x << ' ';
//    cerr << endl;
    return st.getCnt();
}

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