제출 #1172012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172012		anmattroi	Seats (IOI18_seats)	C++17	100 / 100	2373 ms	133908 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define maxn 1000005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int h, w; vector<int> r, c;

struct node {
    int val1 = 0, val2 = 0, cnt = 1;
    node() {}
    node(int _val1, int _val2, int _cnt) : val1(_val1), val2(_val2), cnt(_cnt) {}

    node operator + (const node &other) const {
        if (val1 == other.val1 && val2 == other.val2) return node(val1, val2, cnt+other.cnt);
        if (val1 == other.val1) return val2 < other.val2 ? *this : other;
        return val1 < other.val1 ? *this : other;
    }

    bool operator == (const node &other) const {
        return val1 == other.val1 && val2 == other.val2;
    }
} st[4*maxn];

int lz1[4*maxn], lz2[4*maxn];

void down(int r) {
    if (lz1[r]) {
        int &d = lz1[r];
        st[r<<1].val1 += d;
        st[r<<1|1].val1 += d;
        lz1[r<<1] += d;
        lz1[r<<1|1] += d;
        d = 0;
    }

    if (lz2[r]) {
        int &d = lz2[r];
        st[r<<1].val2 += d;
        st[r<<1|1].val2 += d;
        lz2[r<<1] += d;
        lz2[r<<1|1] += d;
        d = 0;
    }
}

vector<vector<int> > matrix;

void update1(int u, int v, int d, int r = 1, int lo = 0, int hi = h*w-1) {
    if (u <= lo && hi <= v) {
        st[r].val1 += d; lz1[r] += d;
        return;
    }
    down(r);
    int mid = (lo + hi) >> 1;
    if (u <= mid) update1(u, v, d, r<<1, lo, mid);
    if (v > mid) update1(u, v, d, r<<1|1, mid+1, hi);
    st[r] = st[r<<1] + st[r<<1|1];
}

void update2(int u, int v, int d, int r = 1, int lo = 0, int hi = h*w-1) {
    if (u <= lo && hi <= v) {
        st[r].val2 += d; lz2[r] += d;
        return;
    }
    down(r);
    int mid = (lo + hi) >> 1;
    if (u <= mid) update2(u, v, d, r<<1, lo, mid);
    if (v > mid) update2(u, v, d, r<<1|1, mid+1, hi);
    st[r] = st[r<<1] + st[r<<1|1];
}

void try_case_one(const vector<int> &block, int mult) {
    int min1 = INT_MAX, min2 = INT_MAX; for (int i : block)
    if (min1 > i) {
        min2 = min1;
        min1 = i;
    } else if (min2 > i) min2 = i;
    if (min1 < min2) update1(min1, min2-1, mult);
}

void try_case_two(const vector<int> &block, int mult) {
    int max1 = 0, max2 = 0; for (int i : block)
    if (max1 < i) {
        max2 = max1;
        max1 = i;
    } else if (max2 < i) max2 = i;
    if (max2 < max1) update2(max2, max1-1, mult);
}


void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    h = H; w = W;
    r = R; c = C;
    for (int i = 0; i < H*W; i++) {
        ++r[i]; ++c[i];
    }
    matrix.assign(h+2, vector<int>(w+2, h*w));
    for (int i = 0; i < H*W; i++) matrix[r[i]][c[i]] = i;
    for (int i = 0; i <= h; i++)
    for (int j = 0; j <= w; j++) {
        try_case_one({matrix[i][j], matrix[i+1][j], matrix[i][j+1], matrix[i+1][j+1]}, 1);
        try_case_two({matrix[i][j], matrix[i+1][j], matrix[i][j+1], matrix[i+1][j+1]}, 1);
    }

}

int swap_seats(int a, int b) {
    vector<ii > nho;

    nho.emplace_back(r[a]-1, c[a]-1);
    nho.emplace_back(r[a], c[a]-1);
    nho.emplace_back(r[a]-1, c[a]);
    nho.emplace_back(r[a], c[a]);

    nho.emplace_back(r[b]-1, c[b]-1);
    nho.emplace_back(r[b], c[b]-1);
    nho.emplace_back(r[b]-1, c[b]);
    nho.emplace_back(r[b], c[b]);

    sort(nho.begin(), nho.end());
    nho.erase(unique(nho.begin(), nho.end()), nho.end());

    for (auto [u, v] : nho) {
        try_case_one({matrix[u][v], matrix[u+1][v], matrix[u][v+1], matrix[u+1][v+1]}, -1);
        try_case_two({matrix[u][v], matrix[u+1][v], matrix[u][v+1], matrix[u+1][v+1]}, -1);
    }
    swap(matrix[r[a]][c[a]], matrix[r[b]][c[b]]);
    swap(r[a], r[b]); swap(c[a], c[b]);
    for (auto [u, v] : nho) {
        try_case_one({matrix[u][v], matrix[u+1][v], matrix[u][v+1], matrix[u+1][v+1]}, 1);
        try_case_two({matrix[u][v], matrix[u+1][v], matrix[u][v+1], matrix[u+1][v+1]}, 1);
    }

    assert(st[1].val1 == 4 && st[1].val2 == 0);
    return st[1].cnt;
}
/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5

3 4
*/

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