Submission #403115

#	Time	Username	Problem	Language	Result	Execution time	Memory
403115		jhnah917	Seats (IOI18_seats)	C++14	100 / 100	2570 ms	102512 KiB

seats

/******************************
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, A[1 << 20];
vector<int> X, Y;
vector<vector<int>> V;
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=1, int e=K){
    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=1, int e=K){
    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]);
}

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);

    V = vector<vector<int>>(N+2, vector<int>(M+2, K+1));
    for(int i=0; i<K; i++) V[++X[i]][++Y[i]] = i+1;

    for(int i=0; i<=N; i++){
        for(int j=0; j<=M; j++){
            vector<int> tmp = {V[i][j], V[i+1][j], V[i][j+1], V[i+1][j+1]};
            sort(tmp.begin(), tmp.end());
            A[tmp[0]]++; A[tmp[1]]--;
            A[tmp[2]]++; A[tmp[3]]--;
        }
    }
    partial_sum(A, A+(1<<20), A);
    Init();
}

void Change(int x, int y, int v){
    for(int dx=0; dx<2; dx++) for(int dy=0; dy<2; dy++) {
        int i = x - dx, j = y - dy;
        vector<int> tmp = {V[i][j], V[i+1][j], V[i][j+1], V[i+1][j+1]};
        sort(tmp.begin(), tmp.end());
        Update(tmp[0], tmp[1]-1, v);
        Update(tmp[2], tmp[3]-1, v);
    }
}

int swap_seats(int a, int b){
    Change(X[a], Y[a], -1); Change(X[b], Y[b], -1);
    swap(X[a], X[b]); swap(Y[a], Y[b]);
    swap(V[X[a]][Y[a]], V[X[b]][Y[b]]);
    Change(X[a], Y[a], +1); Change(X[b], Y[b], +1);
    return T[1].x == 4 ? T[1].y : 0;
}

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

Compilation message (stderr)

seats.cpp: In function 'void Init(int, int, int)':
seats.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int m = s + e >> 1;
      |             ~~^~~
seats.cpp: In function 'void Update(int, int, int, int, int, int)':
seats.cpp:40:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int m = s + e >> 1;
      |             ~~^~~

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