제출 #108469

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
108469		tictaccat	Seats (IOI18_seats)	C++14	25 / 100	4035 ms	103544 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

struct Node {
    int maxR, minR, maxC, minC;
    int val() {
        return (maxR-minR+1)*(maxC-minC+1);
    }
    Node merge(Node b) {
        return {max(maxR,b.maxR), min(minR,b.minR), max(maxC,b.maxC) ,min(minC,b.minC)};
    }
};

vector<int> R,C;
int H,W;
vector<bool> beautiful;
int beauty;

vector<Node> tr;

void build(int cur, int x, int y) {
    if (x == y) {
        tr[cur] = {R[x],R[x],C[x],C[x]};
        return;
    }
    int mid = (x+y)/2;
    build(cur*2,x,mid);
    build(cur*2+1,mid+1,y);
    tr[cur] = tr[cur*2].merge(tr[cur*2+1]);
}

void upd(int cur, int x, int y, int pos, int valR, int valC) {
    if (y < pos || x > pos) return;
    if (x == y) {
        tr[cur] = {valR, valR, valC, valC};
        return;
    }
    int mid = (x+y)/2;
    upd(cur*2, x, mid, pos, valR, valC);
    upd(cur*2+1, mid+1, y, pos, valR, valC);
    tr[cur] = tr[cur*2].merge(tr[cur*2+1]);
}

pair<int,int> query(int cur, int x, int y, int t, Node joined) {
    if (x == y) {
        int val = joined.merge(tr[cur]).val();
        if (val > t) return make_pair(x,val);
        else return make_pair(H*W,val);
    }
    int mid = (x+y)/2;
    if (joined.merge(tr[cur*2]).val() > t) {
        return query(cur*2, x, mid, t, joined);
    }
    else {
        joined = joined.merge(tr[cur*2]);
        return query(cur*2 + 1, mid + 1, y, t, joined);
    }
}

int findBeauty() {

    int t = -1;
    int z = -1;
    int b = 0;

    while (z < H*W) {
        pair<int,int> nxt = query(1,0,H*W-1,t,{-INF,INF,-INF,INF});
        if (z <= t-1 && t-1 < nxt.first) {
            //cout << t << "\n";
            b++;
        }
        tie(z,t) = nxt;
        //cout << t << " " << z << "\n";
    }

    return b;
}

void give_initial_chart(int tempH, int tempW, std::vector<int> tempR, std::vector<int> tempC) {
    H = tempH; W = tempW; R = tempR; C = tempC;
    tr.resize(4*H*W);
    build(1,0,H*W-1);

 //   cout << query(1,0,H*W-1, 4, {-INF,INF,-INF,INF}) << "\n";
    //ftR.build(H*W); ftC.build(H*W);
}

int swap_seats(int a, int b) {
    // ftR.upd(a,R[b]); ftR.upd(b,R[a]);
    // ftC.upd(a,C[b]); ftC.upd(b,C[a]);
    upd(1,0,H*W-1,a,R[b],C[b]);
    upd(1,0,H*W-1,b,R[a],C[a]);
    swap(R[a],R[b]);
    swap(C[a],C[b]);
    int res = findBeauty();
    //cout << "ans: ";
    return res;
}

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