Submission #403080

#	Time	Username	Problem	Language	Result	Execution time	Memory
403080		jhnah917	Seats (IOI18_seats)	C++14	70 / 100	4051 ms	94132 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;

constexpr int INF = 0x3f3f3f3f;

namespace Subtask5{
using PII = pair<int, int>;
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;
}
}

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];
vector<Node> Prefix;
int ans_4;

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;
    if(H == 1){ Subtask5::give_initial_chart(H, W, _R, _C); return; }
    swap(X, _R); swap(Y, _C);

    if(N <= 1000 && M <= 1000){ Init(); return; } // Subtask3

    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+3+4+5 = 70pts
int swap_seats(int a, int b){
    if(N == 1) return Subtask5::swap_seats(a, b);
    if(a > b) swap(a, b);
    swap(X[a], X[b]); swap(Y[a], Y[b]);

    if(N <= 1000 && M <= 1000){ // Subtask3
        Update(a); Update(b);
        Node data;
        return Query(data);
    }

    for(int i=a; i<b; i++) if(Prefix[i].check(i+1)) ans_4--;
    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
 */

Compilation message (stderr)

seats.cpp: In function 'void Subtask5::Init(int, int, int)':
seats.cpp:33:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |     int m = s + e >> 1;
      |             ~~^~~
seats.cpp: In function 'void Subtask5::Update(int, int, int, int, int, int)':
seats.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |     int m = s + e >> 1;
      |             ~~^~~
seats.cpp: In constructor 'Node::Node(int, int, int, int)':
seats.cpp:78:17: warning: 'Node::Y1' will be initialized after [-Wreorder]
   78 |     int X1, X2, Y1, Y2;
      |                 ^~
seats.cpp:78:13: warning:   'int Node::X2' [-Wreorder]
   78 |     int X1, X2, Y1, Y2;
      |             ^~
seats.cpp:81:5: warning:   when initialized here [-Wreorder]
   81 |     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:102:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |     int m = s + e >> 1;
      |             ~~^~~
seats.cpp: In function 'void Update(int, int, int, int)':
seats.cpp:109:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  109 |     int m = s + e >> 1;
      |             ~~^~~
seats.cpp: In function 'int Query(Node&, int, int, int)':
seats.cpp:117:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  117 |     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: 0 / 30