제출 #135923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
135923		Meloric	자리 배치 (IOI18_seats)	C++14	70 / 100	4064 ms	128632 KiB

seats

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "seats.h"

#define pb push_back
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
using namespace std;

struct node{
    int mnv, mna, lz;
};
vector<vector<int>> place;
vector<pii> pos;
vector<node> seg;
vector<pii> ord = {{0, 0},{0, -1},{-1, 0},{-1,-1}};
int N;
node conq(node& a, node& b){
    node c;
    if(a.mnv == b.mnv){
        c.mnv = a.mnv;
        c.mna = a.mna + b.mna;
    }
    if(a.mnv < b.mnv){
        c.mnv = a.mnv;
        c.mna = a.mna;
    }
    if(a.mnv > b.mnv){
        c.mnv = b.mnv;
        c.mna = b.mna;
    }
    return c;
}
void comb(int v){
    seg[v].lz += seg[v/2].lz;
}
void appl(int v){
    seg[v].mnv+=seg[v].lz;
    seg[v].lz = 0;
}
void build(int v, int tl, int tr){
    if(tl == tr){
        seg[v].mna = 1;
        return;
    }
    int tm = (tl+tr)/2;
    build(v*2, tl, tm);
    build(v*2+1, tm+1, tr);
}
void upd(int v, int tl, int tr, int l, int r, int val){
    if(r<l)return;
    if(seg[v].lz!= 0){
        if(tl!=tr){
            seg[2*v].lz+=seg[v].lz;
            seg[2*v+1].lz+=seg[v].lz;
        }
        seg[v].mnv+=seg[v].lz;
        seg[v].lz = 0;
    }
    if(tl>r || tr < l)return;
    if(tl >= l && tr <= r){
        seg[v].lz+= val;
        if(tl!=tr){
            comb(2*v);
            comb(2*v+1);
        }
        appl(v);
        return;
    }
    int tm = (tl+tr)/2;
    upd(v*2, tl, tm, l, r, val);
    upd(v*2+1, tm+1, tr, l, r, val);
    seg[v] = conq(seg[2*v], seg[2*v+1]);
}
void fix(int x, int y, int val){
    array<int, 4> tmp;
    tmp[0] = place[x][y];
    tmp[1] = place[x+1][y];
    tmp[2] = place[x][y+1];
    tmp[3] = place[x+1][y+1];
    sort(all(tmp));
    upd(1, 0, N-1, tmp[0], tmp[1]-1, val);
    upd(1, 0, N-1, tmp[2], tmp[3]-1, val);
}
pii operator +(pii& a, pii& b){
    pii c = {0, 0};
    c.X = a.X+b.X;
    c.Y = a.Y+b.Y;
    return c;
}
void give_initial_chart(int H, int W, vector<int> R, vector<int> C) {
    N = H*W;
    place.assign(H+2, vector<int>(W+2, H*W));
    pos.assign(H*W, {0,0});
    for(int i = 0; i< H*W; i++){
        place[R[i]+1][C[i]+1] = i;
        pos[i] = {R[i]+1, C[i]+1};
    }
    /*
    for(auto i : place){
        for(auto j : i){
            cout << j << ' ';
        }
        cout << '\n';
    }*/

    seg.assign(4*H*W, {0, 0, 0});
    build(1, 0, N-1);
    for(int i = 0; i< H+1; i++){
        for(int j = 0; j < W+1; j++){
            fix(i, j, 1);
        }
    }/*
    for(int i = 0; i< (int)seg.size(); i++){
        cout << i << ' '<< seg[i].mnv << ' '<<seg[i].mna<< ' '<< seg[i].lz<<'\n';
    }*/
}
int swap_seats(int a, int b) {
    for(int i = 0; i< 2; i++){
        for(int j = 0; j < 2; j++){
            fix(pos[a].X-i, pos[a].Y-j, -1);
            fix(pos[b].X-i, pos[b].Y-j, -1);
        }
    }/*
    for(auto i : ord){
        pii tmp = pos[a] + i;
        //cout <<'a'<< a << ' '<< tmp.X << ' '<< tmp.Y<<'\n';
        fix(tmp.X, tmp.Y, -1);
        tmp = pos[b] + i;
        fix(tmp.X, tmp.Y, -1);
    }*/
    swap(place[pos[a].X][pos[a].Y], place[pos[b].X][pos[b].Y]);
    swap(pos[a], pos[b]);
    for(int i = 0; i< 2; i++){
        for(int j = 0; j < 2; j++){
            fix(pos[a].X-i, pos[a].Y-j, 1);
            fix(pos[b].X-i, pos[b].Y-j, 1);
        }
    }/*
    for(auto i : ord){
        pii tmp = pos[a] + i;
        fix(tmp.X, tmp.Y, 1);
        tmp = pos[b] + i;
        fix(tmp.X, tmp.Y, 1);
    }*/
    return seg[1].mna;
}

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