제출 #113606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
113606		zoooma13	자리 배치 (IOI18_seats)	C++14	0 / 100	2640 ms	64496 KiB

seats

#include "seats.h"
#include "bits/stdc++.h"
using namespace std;

#define FL (p<<1)|1
#define FR (p<<1)+2
#define row 0
#define col 1

int h ,w ,n;
vector <pair<int ,int>> pos;

int tree[2][1003][4*1003];
void update(bool roc ,int mn ,int idx ,int val ,int l=0 ,int r=1000 ,int p=0){
    if(l == r){
        tree[roc][mn][p] = val;
        return;
    }
    int mid = (l+r)>>1;
    if(idx <= mid) update(roc ,mn ,idx ,val ,l ,mid ,FL);
    else           update(roc ,mn ,idx ,val ,mid+1 ,r ,FR);
    tree[roc][mn][p] = max(tree[roc][mn][FL] ,tree[roc][mn][FR]);
}
int ask(bool roc ,int mn ,int ql ,int qr ,int l=0 ,int r=1000 ,int p=0){
    if(ql <= l && r <= qr)
        return tree[roc][mn][p];
    if(r < ql || qr < l)
        return -1e9;
    int mid = (l+r)>>1;
    return max(ask(roc ,mn ,ql ,qr ,l ,mid ,FL),
               ask(roc ,mn ,ql ,qr ,mid+1 ,r ,FR));
}

void give_initial_chart(int H, int W, std::vector<int> R, std::vector<int> C) {
    h = H ,w = W ,n = H*W;
    assert(H <= 1000 && W <= 1000);
    for(int i=0; i<n; i++){
        update(row ,R[i] ,C[i] ,i);
        update(col ,C[i] ,R[i] ,i);
        pos.push_back({R[i] ,C[i]});
    }
}

int swap_seats(int a, int b) {
    int ret = 1;
    update(row ,pos[a].first ,pos[a].second ,b);
    update(col ,pos[a].second ,pos[a].first ,b);
    update(row ,pos[b].first ,pos[b].second ,a);
    update(col ,pos[b].second ,pos[b].first ,a);
    swap(pos[a] ,pos[b]);

    int curr_max_seat = 0;
    int min_r = pos[0].first ,min_c = pos[0].second;
    int max_r = pos[0].first ,max_c = pos[0].second;
    for(int i=1; i<n; ){ ///O(H+W = 2000)
        int lst_min_r = min_r ,lst_min_c = min_c;
        int lst_max_r = max_r ,lst_max_c = max_c;
        min_r = min(min_r ,pos[i].first);
        min_c = min(min_c ,pos[i].second);
        max_r = max(max_r ,pos[i].first);
        max_c = max(max_c ,pos[i].second);


        while(lst_max_c < max_c)
            curr_max_seat = max(curr_max_seat ,ask(col ,++lst_max_c ,lst_min_r ,lst_max_r));
        while(min_c < lst_min_c)
            curr_max_seat = max(curr_max_seat ,ask(col ,--lst_min_c ,lst_min_r ,lst_max_r));
        while(lst_max_r < max_r)
            curr_max_seat = max(curr_max_seat ,ask(row ,++lst_max_r ,lst_min_c ,lst_max_c));
        while(min_r < lst_min_r)
            curr_max_seat = max(curr_max_seat ,ask(row ,--lst_min_r ,lst_min_c ,lst_max_c));

        //cout << i << " - (" << min_c << ',' << min_r << ") : (" << max_c << ',' << max_r << ") = " << curr_max_seat << endl;
        if(curr_max_seat == i)
            ret++ ,i++;
        else
            i = curr_max_seat;
    }

    return ret;
}

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