Submission #119483

#	Time	Username	Problem	Language	Result	Execution time	Memory
119483		songc	Seats (IOI18_seats)	C++14	100 / 100	2554 ms	103016 KiB

seats

#include <bits/stdc++.h>
#include "seats.h"
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int H, W;
vector<vector<int>> M;
int Min[4040404], Cnt[4040404];
int S[1010101], lazy[4040404];
int R[1010101], C[1010101];

void init(int id, int s, int e){
    if (s == e){
        Min[id] = S[s];
        Cnt[id] = 1;
        return;
    }
    int mid = (s+e)/2;
    init(id*2, s, mid);
    init(id*2+1, mid+1, e);
    Min[id] = min(Min[id*2], Min[id*2+1]), Cnt[id] = 0;
    if (Min[id] == Min[id*2]) Cnt[id] += Cnt[id*2];
    if (Min[id] == Min[id*2+1]) Cnt[id] += Cnt[id*2+1];
}

void update(int id, int s, int e, int ts, int te, int v){
    if (e < ts || te < s) return;
    if (ts <= s && e <= te){
        Min[id] += v;
        lazy[id] += v;
        return;
    }
    Min[id*2] += lazy[id];
    Min[id*2+1] += lazy[id];
    lazy[id*2] += lazy[id];
    lazy[id*2+1] += lazy[id];
    lazy[id] = 0;

    int mid = (s+e)/2;
    update(id*2, s, mid, ts, te, v);
    update(id*2+1, mid+1, e, ts, te, v);
    Min[id] = min(Min[id*2], Min[id*2+1]), Cnt[id] = 0;
    if (Min[id] == Min[id*2]) Cnt[id] += Cnt[id*2];
    if (Min[id] == Min[id*2+1]) Cnt[id] += Cnt[id*2+1];
}

void give_initial_chart(int h, int w, vector<int> r, vector<int> c){
    H=h, W=w;
    M.reserve(H+2);
    for (int i=0; i<=H+1; i++) M[i].reserve(W+2);
    for (int i=0; i<=W+1; i++) M[0][i] = M[H+1][i] = H*W+1;
    for (int i=0; i<=H+1; i++) M[i][0] = M[i][W+1] = H*W+1;
    for (int i=1; i<=H*W; i++){
        R[i] = r[i-1]+1, C[i] = c[i-1]+1;
        M[R[i]][C[i]] = i;
    }
    for (int i=0; i<=H; i++) for (int j=0; j<=W; j++){
        vector<int> t;
        t.push_back(M[i][j]); t.push_back(M[i][j+1]);
        t.push_back(M[i+1][j]); t.push_back(M[i+1][j+1]);
        sort(t.begin(), t.end());
        S[t[0]]++, S[t[1]]--;
        S[t[2]]++, S[t[3]]--;
    }
    for (int i=1; i<=H*W; i++) S[i] += S[i-1];
    init(1, 1, H*W);
}

void angle(int x, int y, int v){
    vector<int> t;
    t.push_back(M[x][y]); t.push_back(M[x][y+1]);
    t.push_back(M[x+1][y]); t.push_back(M[x+1][y+1]);
    sort(t.begin(), t.end());
    update(1, 1, H*W, t[0], t[1]-1, v);
    update(1, 1, H*W, t[2], t[3]-1, v);
}

int swap_seats(int a, int b) {
    a++, b++;

    angle(R[a]-1, C[a]-1, -1);
    angle(R[a], C[a]-1, -1);
    angle(R[a]-1, C[a], -1);
    angle(R[a], C[a], -1);

    angle(R[b]-1, C[b]-1, -1);
    angle(R[b], C[b]-1, -1);
    angle(R[b]-1, C[b], -1);
    angle(R[b], C[b], -1);

    swap(M[R[a]][C[a]], M[R[b]][C[b]]);
    swap(R[a], R[b]);
    swap(C[a], C[b]);

    angle(R[a]-1, C[a]-1, 1);
    angle(R[a], C[a]-1, 1);
    angle(R[a]-1, C[a], 1);
    angle(R[a], C[a], 1);

    angle(R[b]-1, C[b]-1, 1);
    angle(R[b], C[b]-1, 1);
    angle(R[b]-1, C[b], 1);
    angle(R[b], C[b], 1);

    return Cnt[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