제출 #800331

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
800331		jasmin	자리 배치 (IOI18_seats)	C++17	11 / 100	4054 ms	86884 KiB

seats

#include<bits/stdc++.h>
using namespace std;

vector<bool> good;
int ans=0;
vector<int> r;
vector<int> c;
int n;

const int INF=1e9+7;

struct node{
    int maxi = 0;
    int mini = INF;
};
node zero={0, INF};

struct segtree{
    vector<node> tree;

    void init(int n){
        tree.assign(n*4, zero);
    }

    node merge(node a, node b){
        a.maxi = max(a.maxi, b.maxi);
        a.mini = min(a.mini, b.mini);
        return a;
    }

    node update(int l,int r, int v, int x, int val){
        if(x<l || r<=x) return tree[v];
        if(l+1==r){
            return tree[v]={val, val};
        }
        int m=l+(r-l)/2;
        return tree[v]=merge(update(l, m, v*2+1, x, val), update(m, r, v*2+2, x, val));
    }

    node query(int l, int r, int v, int ql, int qr){
        if(qr<=l || r<=ql) return zero;
        if(ql<=l && r<=qr){
            return tree[v];
        }
        int m=l+(r-l)/2;
        return merge(query(l, m, v*2+1, ql, qr), query(m, r, v*2+2, ql, qr));
    }
};
segtree segr;
segtree segc;

void give_initial_chart(int h, int w, vector<int> R, vector<int> C) {
    r=R;
    c=C;

    n=h*w;
    good.assign(n, 0);
    segr.init(n);
    segc.init(n);

    for(int i=0; i<n; i++){
        segr.update(0, n, 0, i, r[i]);
        segc.update(0, n, 0, i, c[i]);

        auto valr=segr.query(0, n, 0, 0, i+1);
        auto valc=segc.query(0, n, 0, 0, i+1);

        int size = (valr.maxi - valr.mini + 1) * (valc.maxi - valc.mini + 1);
        if(size == i+1){
            good[i]=true;
            ans++;
        }
    }

}

int swap_seats3(int a, int b){

    int oldr = r[a];
    segr.update(0, n, 0, a, r[b]);
    segr.update(0, n, 0, b, oldr);
    swap(r[a], r[b]);

    int oldc=c[a];
    segc.update(0, n, 0, a, c[b]);
    segc.update(0, n, 0, b, oldc);
    swap(c[a], c[b]);

    good.assign(n, false);
    ans=0;
    for(int i=0; i<n; i++){

        auto valr=segr.query(0, n, 0, 0, i+1);
        auto valc=segc.query(0, n, 0, 0, i+1);

        int size = (valr.maxi - valr.mini +1) * (valc.maxi - valc.mini +1);
        if(size == i+1){
            good[i]=true;
            ans++;
        }

        i = max(i, size -2);
    }

    return ans;
}

int swap_seats4(int a, int b){

    int oldr = r[a];
    segr.update(0, n, 0, a, r[b]);
    segr.update(0, n, 0, b, oldr);
    swap(r[a], r[b]);

    int oldc=c[a];
    segc.update(0, n, 0, a, c[b]);
    segc.update(0, n, 0, b, oldc);
    swap(c[a], c[b]);

    if(b<a) swap(a, b);
    for(int i=a; i<b; i++){
        ans -= good[i];
        good[i]=0;

        auto valr=segr.query(0, n, 0, 0, i+1);
        auto valc=segc.query(0, n, 0, 0, i+1);

        int size = (valr.maxi - valr.mini +1) * (valc.maxi - valc.mini +1);

        if(size == i+1){
            good[i]=true;
            ans++;
        }

    }
    return ans;
}

int swap_seats(int a, int b) {

    if(abs(a-b)<=10000){
        return swap_seats4(a, b);
    }

    return swap_seats3(a, b);

}

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