Submission #402913

#	Time	Username	Problem	Language	Result	Execution time	Memory
402913		jhnah917	Seats (IOI18_seats)	C++14	37 / 100	4069 ms	135372 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
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
constexpr int INF = 0x3f3f3f3f;

struct Node{
    int X1, X2, Y1, Y2;
    Node() : Node(INF, -INF, INF, -INF) {}
    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<vector<int>> V;
Node T[1 << 21];

vector<Node> Prefix;
int ans_sub4;

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);
    V = vector<vector<int>>(N, vector<int>(M));
    for(int i=0; i<N*M; i++) V[X[i]][Y[i]] = i;

    if(N <= 1000 && M <= 1000) Init();
    else{
        Prefix.resize(N*M);
        for(int i=0; i<N*M; i++) Prefix[i].set(X[i], Y[i]);
        for(int i=1; i<N*M; i++) Prefix[i] = Merge(Prefix[i-1], Prefix[i]);
        for(int i=0; i<N*M; i++) if(Prefix[i].check(i+1)) ans_sub4++;
    }
}

int Subtask3(int a, int b){
    swap(V[X[a]][Y[a]], V[X[b]][Y[b]]);
    swap(X[a], X[b]); swap(Y[a], Y[b]);
    Update(a); Update(b);

    Node data;
    return Query(data);
}

// Subtask 1+2+3+4 = 37pts
int swap_seats(int a, int b){
    if(N <= 1000 && M <= 1000) return Subtask3(a, b);

    if(a > b) swap(a, b);
    for(int i=a; i<b; i++) if(Prefix[i].check(i+1)) ans_sub4--;
    swap(V[X[a]][Y[a]], V[X[b]][Y[b]]);
    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_sub4++;
    }
    return ans_sub4;
}

#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 constructor 'Node::Node(int, int, int, int)':
seats.cpp:23:17: warning: 'Node::Y1' will be initialized after [-Wreorder]
   23 |     int X1, X2, Y1, Y2;
      |                 ^~
seats.cpp:23:13: warning:   'int Node::X2' [-Wreorder]
   23 |     int X1, X2, Y1, Y2;
      |             ^~
seats.cpp:25:5: warning:   when initialized here [-Wreorder]
   25 |     Node(int X1, int X2, int Y1, int Y2) : X1(X1), Y1(Y1), X2(X2), Y2(Y2) {}
      |     ^~~~
seats.cpp: In function 'void Init(int, int, int)':
seats.cpp:48:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |     int m = s + e >> 1;
      |             ~~^~~
seats.cpp: In function 'void Update(int, int, int, int)':
seats.cpp:55:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int m = s + e >> 1;
      |             ~~^~~
seats.cpp: In function 'int Query(Node&, int, int, int)':
seats.cpp:63:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int m = s + e >> 1;
      |             ~~^~~

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