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;
Node T[1 << 21];

void Init(int node=1, int s=0, int e=K-1){
    if(s == e){ T[node].set(X[s], Y[s]); return; }
    int m = s + e >> 1;
    Init(node<<1, s, m);
    Init(node<<1|1, m+1, e);
    T[node] = Merge(T[node<<1], T[node<<1|1]);
}
void Update(int pos, int node=1, int s=0, int e=K-1){
    if(s == e){ T[node].set(X[s], Y[s]); return; }
    int m = s + e >> 1;
    if(pos <= m) Update(pos, node<<1, s, m);
    else Update(pos, node<<1|1, m+1, e);
    T[node] = Merge(T[node<<1], T[node<<1|1]);
}
int Query(Node &data, int node=1, int s=0, int e=K-1){
    if(s == e) return (data = Merge(data, T[node])).check(s+1);
    if(data.in(T[node])) return data.check(e+1);
    int m = s + e >> 1;
    return Query(data, node<<1, s, m) + Query(data, node<<1|1, m+1, e);
}

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);
    Init();
}

// Subtask 1+2+3 = 31pts
int swap_seats(int a, int b){
    swap(X[a], X[b]); swap(Y[a], Y[b]);
    Update(a); Update(b);

    Node data;
    return Query(data);
}

#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
 */
결과	메모리	시간	코드 길이
31점	50420	644	2411
문제

문제

출처

ICPC

C++14

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
