제출 #891276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
891276		vjudge1	자리 배치 (IOI18_seats)	C++17	0 / 100	4096 ms	86588 KiB

seats

#include "seats.h"
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

struct AINT {
    int n;
    vi mi, ma;
    AINT(int N = 0) : n(N), mi(4 * N), ma(4 * N) {} 
    void init(int N) {
        n = N;
        mi.assign(4 * N, 0);
        ma.assign(4 * N, 0);
    }
    void update(int p, int v) { update(p, v, 1, 0, n - 1); }
    void update(int p, int v, int u, int s, int d) {
        if(d < p || p < s) return;
        if(s == d) {
            mi[u] = ma[u] = v;
            return;
        }
        update(p, v, u << 1, s, (s + d) >> 1);
        update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        mi[u] = min(mi[u << 1], mi[u << 1 | 1]);
        ma[u] = max(ma[u << 1], ma[u << 1 | 1]);
    }

    ii query(int l, int r) { return query(l, r, 1, 0, n - 1); }

    ii query(int l, int r, int u, int s, int d) {
        if( d < l || r < s ) return {1e9, 0};
        if(l <= s && d <= r)
            return make_pair(mi[u], ma[u]);
        auto [mi1, ma1] = query(l, r, u << 1, s, (s + d) >> 1);
        auto [mi2, ma2] = query(l, r, u << 1 | 1, ((s + d) >> 1) + 1, d);
        return make_pair(min(mi1, mi2), max(ma1, ma2));
    }
};

vi r, c;

int reg = 0;

int tip = 0;

AINT AR, AC;

int h, w;

void give_initial_chart(int H, int W, vi R, vi C) {
    h = H;
    w = W;

    r = R;
    c = C;
    AR.init(H * W);
    AC.init(H * W);
    for(int i = 0; i < H * W; ++i) {
        AR.update(i, R[i]);
        AC.update(i, C[i]);
    }
}

bool ok(int l, int c) {
    auto [mir, mar] = AR.query(0, l * c - 1); 
    auto [mic, mac] = AC.query(0, l * c - 1);
    return (l * c) == ((mar - mir + 1) * (mac - mic + 1));
}

int swap_seats(int a, int b) {
    swap(r[a], r[b]);
    swap(c[a], c[b]);

    AR.update(a, r[a]);
    AR.update(b, r[b]);
    AC.update(a, c[a]);
    AC.update(b, c[b]);

    int hc = 1, wc = 1, re = 1;

    while(hc < h || wc < w) {
        int facut = 0;
        for(int delta = 1;; ++delta) {
            int hh = hc + delta;
            int ww = wc + delta;
            if(hh > h && ww > w) break;
            if(hh <= h && ok(hh, wc)) {
                hc = hh;
                ++re;
                facut = 1;
                break;
            }
            if(ww <= w && ok(hc, ww)) {
                wc = ww;
                ++re;
                facut = 1;
                break;
            }
        }
        if(!facut) {
            if(hc < h)
                ++hc;
            else
                ++wc;
        }
    }
    return re;
}

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