20062번 - Seats

C++14

/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#ifndef LOCAL
#include "seats.h"
#endif
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

constexpr int INF = 0x3f3f3f3f;

struct Node{
    int X1, X2, Y1, Y2;
    Node() : Node(INF, -INF, INF, -INF) {}
    Node(int x, int y) : Node(x, x, y, y) {}
    Node(int X1, int X2, int Y1, int Y2) : X1(X1), Y1(Y1), X2(X2), Y2(Y2) {}
    void set(int x, int y){ X1 = X2 = x; Y1 = Y2 = y; }
    bool in(const Node &t){
        return X1 <= t.X1 && t.X2 <= X2 && Y1 <= t.Y1 && t.Y2 <= Y2;
    }
    bool check(int sz){
        return (X2-X1+1) * (Y2-Y1+1) == sz;
    }
};
Node Merge(const Node &l, const Node &r){
    return {min(l.X1, r.X1), max(l.X2, r.X2), min(l.Y1, r.Y1), max(l.Y2, r.Y2)};
}

int N, M, K;
vector<int> X, Y;
vector<Node> Prefix;

int ans_4;

void give_initial_chart(int H, int W, vector<int> _R, vector<int> _C){
    N = H; M = W; K = N * M;
    swap(X, _R); swap(Y, _C);

    Prefix.resize(K);
    for(int i=0; i<K; i++) Prefix[i].set(X[i], Y[i]);
    for(int i=1; i<K; i++) Prefix[i] = Merge(Prefix[i-1], Prefix[i]);
    for(int i=0; i<K; i++) ans_4 += Prefix[i].check(i+1);
}

// Subtask 1+2+4 = 17pts
int swap_seats(int a, int b){
    if(a > b) swap(a, b);
    for(int i=a; i<b; i++) if(Prefix[i].check(i+1)) ans_4--;

    swap(X[a], X[b]); swap(Y[a], Y[b]);
    for(int i=a; i<b; i++){
        Prefix[i].set(X[i], Y[i]);
        if(i) Prefix[i] = Merge(Prefix[i-1], Prefix[i]);
        if(Prefix[i].check(i+1)) ans_4++;
    }
    return ans_4;
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int H, W, Q;
    cin >> H >> W >> Q;
    vector<int> R(H*W), C(H*W);
    for(int i=0; i<H*W; i++) cin >> R[i] >> C[i];
    vector<int> A(Q), B(Q);
    for(int i=0; i<Q; i++) cin >> A[i] >> B[i];
    give_initial_chart(H, W, R, C);
    for(int i=0; i<Q; i++){
        cout << swap_seats(A[i], B[i]) << "\n";
    }
    return 0;
}
#endif

/*
2 3 2
0 0
1 0
1 1
0 1
0 2
1 2
0 5
0 5
 */
결과	메모리	시간	코드 길이
17점	33280	212	2076
문제

문제

출처

ICPC

C++14

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
