제출 #937050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937050		azberjibiou	자리 배치 (IOI18_seats)	C++17	100 / 100	1847 ms	119640 KiB

seats

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=1001000;
const int mxM=200100;
const int mxK=61;
const int MOD=1e9;
const ll INF=1e18;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1, 0};
typedef struct lazyseg{
    pii seg[4*mxN]={};
    int lazy[4*mxN]={};
    pii mrg(pii a, pii b){
        if(a.fi!=b.fi) return max(a, b);
        return pii(a.fi, a.se+b.se);
    }
    void init(int idx, int s, int e){
        seg[idx]=pii(0, e-s+1);
        if(s==e) return;
        int mid=(s+e)/2;
        init(2*idx, s, mid);
        init(2*idx+1, mid+1, e);
    }
    void propagate(int idx){
        seg[2*idx].fi+=lazy[idx];
        seg[2*idx+1].fi+=lazy[idx];
        lazy[2*idx]+=lazy[idx];
        lazy[2*idx+1]+=lazy[idx];
        lazy[idx]=0;
    }
    void upd(int idx, int s1, int e1, int s2, int e2, int x){
        if(s2>e1 || s1>e2) return;
        if(s2<=s1 && e1<=e2){
            seg[idx].fi+=x, lazy[idx]+=x;
            return;
        }
        propagate(idx);
        int mid=(s1+e1)/2;
        upd(2*idx, s1, mid, s2, e2, x);
        upd(2*idx+1, mid+1, e1, s2, e2, x);
        seg[idx]=mrg(seg[2*idx], seg[2*idx+1]);
    }
}lazyseg;
int H, W, Q;
vector <vector <int>> v;
bool Chk[mxN];
pii pos[mxN];
pii qry[mxN];
lazyseg T1;
int S[mxN];
void input(){
    cin >> H >> W >> Q;
    v.resize(H);
    for(int i=0;i<H;i++) v[i].resize(W);
    for(int i=0;i<H*W;i++){
        int a, b;
        cin >> a >> b;
        v[a][b]=i;
        pos[i]=pii(a, b);
    }
    for(int i=1;i<=Q;i++) cin >> qry[i].fi >> qry[i].se;
}

bool not_ok(int a, int b){
    return (a<0 || a>=H || b<0 || b>=W);
}
void add(int a, int rev, bool init){
    auto [ax, ay]=pos[a];
    for(int i=0;i<4;i++){
        int nx1=ax+dx[i], ny1=ay+dy[i], nx2=ax+dx[(i+1)%4], ny2=ay+dy[(i+1)%4];
        int val1, val2;
        if(not_ok(nx1, ny1)) val1=H*W;
        else val1=v[nx1][ny1];
        if(not_ok(nx2, ny2)) val2=H*W;
        else val2=v[nx2][ny2];
        if(a<val1 && a<val2){
            if(!init) T1.upd(1, 0, H*W-1, a, min(val1, val2)-1, -rev);
            else S[a]-=rev, S[min(val1, val2)]+=rev;
        }
        if(a>val1 && a>val2) {
            if(!init) T1.upd(1, 0, H*W-1, max(val1, val2), a-1, -rev);
            else S[max(val1, val2)]-=rev, S[a]+=rev;
        }
    }
}
void add_area(int a, bool rev){ //rev가 true면 제거하는 것
    int flag=(rev ? -1 : 1);
    auto [ax, ay]=pos[a];
    if(Chk[a]==rev) Chk[a]=(!rev), add(a, flag, false);
    for(int i=0;i<4;i++){
        if(not_ok(ax+dx[i], ay+dy[i])) continue;
        int av=v[ax+dx[i]][ay+dy[i]];
        if(Chk[av]==rev) Chk[av]=(!rev), add(av, flag, false);
    }
}
void init(){
    T1.init(1, 0, H*W-1);
    for(int i=0;i<H*W;i++){
        add(i, 1, true);
        Chk[i]=true;
    }
    for(int i=0;i<H*W;i++){
        if(i!=0) S[i]+=S[i-1];
        T1.upd(1, 0, H*W-1, i, i, S[i]);
    }
}
int swap_seats(int a, int b){
    add_area(a, true), add_area(b, true);
    auto [ax, ay]=pos[a];
    auto [bx, by]=pos[b];
    swap(v[ax][ay], v[bx][by]);
    swap(pos[a], pos[b]);
    add_area(a, false), add_area(b, false);
    return (T1.seg[1].fi==-4 ? T1.seg[1].se : 0);
}
void give_initial_chart(int h, int w, vector <int> r, vector <int> c){
    H=h, W=w;
    v.resize(H);
    for(int i=0;i<H;i++) v[i].resize(W);
    for(int i=0;i<H*W;i++){
        v[r[i]][c[i]]=i;
        pos[i]=pii(r[i], c[i]);
    }
    init();
}
/*
int main()
{
    gibon
    input();
    init();
    for(int i=1;i<=Q;i++) cout << swap_seats(qry[i].fi, qry[i].se) << '\n';
}
*/

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