제출 #596326

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

seats

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

using namespace std;

const int N = 1e6 + 5, INF = 1e9 + 5;

int n;

pair<int, int> merge(pair<int, int> a, pair<int, int> b){
    return {min(a.first, b.first), max(a.second, b.second)};
}

struct SegTree{
    pair<int, int> tree[N * 4];

    void build(vector<int> &arr, int v = 1, int l = 0, int r = n - 1){
        if(l == r) tree[v] = {arr[l], arr[l]};
        else{
            int m = l + (r - l) / 2;

            build(arr, v * 2, l, m);
            build(arr, v * 2 + 1, m + 1, r);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
        }
    }

    pair<int, int> query(int l, int r, int v = 1, int tl = 0, int tr = n - 1){
        if(l > r) return {INF, -INF};
        else if(l == tl && r == tr) return tree[v];
        else{
            int tm = tl + (tr - tl) / 2;

            return merge(query(l, min(tm, r), v * 2, tl, tm), query(max(tm + 1, l), r, v * 2 + 1, tm + 1, tr));
        }
    }

    void update(int pos, int val, int v = 1, int l = 0, int r = n - 1){
        if(l == r) tree[v] = {val, val};
        else{
            int m = l + (r - l) / 2;

            if(pos <= m) update(pos, val, v * 2, l, m);
            else update(pos, val, v * 2 + 1, m + 1, r);

            tree[v] = merge(tree[v * 2], tree[v * 2 + 1]);
        }
    }
};

SegTree sgtx, sgty;

vector<int> X, Y;

void give_initial_chart(int H, int W, vector<int> X_, vector<int> Y_) {
    X = X_, Y = Y_;

    n = H * W;

    sgtx.build(X);
    sgty.build(Y);
}

int swap_seats(int a, int b){
    sgtx.update(a, X[b]);
    sgty.update(a, Y[b]);

    sgtx.update(b, X[a]);
    sgty.update(b, Y[a]);

    swap(X[a], X[b]);
    swap(Y[a], Y[b]);

    int ans = 0;

    if(n <= 10000){
        pair<int, int> x = {INF, -INF}, y = {INF, -INF};

        for(int i = 0; i < n; i++){
            x = merge(x, {X[i], X[i]});
            y = merge(y, {Y[i], Y[i]});

            if((x.second - x.first + 1) * (y.second - y.first + 1) == i + 1) ans++;
        }
    }
    else{
        pair<int, int> x, y;

        int cur = 0;

        while(cur < n){
            x = sgtx.query(0, cur);
            y = sgty.query(0, cur);

            if((x.second - x.first + 1) * (y.second - y.first + 1) == cur + 1) ans++, cur++;
            else cur = (x.second - x.first + 1) * (y.second - y.first + 1) - 1;
        }
    }

    return ans;
}

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