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;

using PII = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;

int N, M, K;
vector<int> X, Y, V, A;
PII T[1 << 21];
int L[1 << 21];

PII Merge(const PII &l, const PII &r){
    return l.x == r.x ? PII(l.x, l.y+r.y) : min(l, r);
}
void Push(int node, int s, int e){
    T[node].x += L[node];
    if(s != e) L[node<<1] += L[node], L[node<<1|1] += L[node];
    L[node] = 0;
}
void Init(int node=1, int s=0, int e=K-1){
    if(s == e){ T[node] = {A[s], 1}; 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 l, int r, int v, int node=1, int s=0, int e=K-1){
    Push(node, s, e);
    if(r < s || e < l) return;
    if(l <= s && e <= r){ L[node] += v; Push(node, s, e); return; }
    int m = s + e >> 1;
    Update(l, r, v, node<<1, s, m);
    Update(l, r, v, node<<1|1, m+1, e);
    T[node] = Merge(T[node<<1], T[node<<1|1]);
}

int Value(int v){
    int pos = Y[v], ret = 0;
    ret += (pos == 0 || V[pos-1] > v) ? 1 : -1;
    ret += (pos == K-1 || V[pos+1] > v) ? 1 : -1;
    return ret;
}

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);
    A.resize(K); V.resize(K);
    for(int i=0; i<K; i++) V[Y[i]] = i;
    for(int i=0; i<K; i++) A[i] = Value(i);
    partial_sum(A.begin(), A.end(), A.begin());
    Init();
    for(int i=K-1; i>=1; i--) A[i] -= A[i-1];
}

int swap_seats(int a, int b){
    swap(Y[a], Y[b]);
    swap(V[Y[a]], V[Y[b]]);

    for(auto i : {Y[a]-1, Y[a], Y[a]+1, Y[b]-1, Y[b], Y[b]+1}){
        if(i < 0 || i >= K) continue;
        Update(V[i], K-1, Value(V[i])-A[V[i]]);
        A[V[i]] = Value(V[i]);
    }
    return T[1].y;
}

#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
 */

/*
1 5 3
0 0
0 4
0 2
0 1
0 3
0 3
1 4
0 4
 */
결과	메모리	시간	코드 길이
33점	50436	308	2481
문제

문제

출처

ICPC

C++14

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
