Submission #256859

#	Time	Username	Problem	Language	Result	Execution time	Memory
256859		Hehehe	Seats (IOI18_seats)	C++14	100 / 100	2866 ms	131064 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
using namespace std;
const int NMAX = 4000005;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

typedef pair<int, int> pii;

pii t[4*NMAX];
int lz[4*NMAX];
pii seats[4000555];
int tsz, H, W;

void updateA(pii pos);
void deleteA(pii pos);
void updateB(pii pos);
void deleteB(pii pos);
int secondSmallestNeighbour(pii pos);
pii getB(pii pos);
bool ok(pii pos);
void rewrite(pii pos, int val);

vector<vector<int>> arr;

int ln(int n){
    return 2*n;
}
int rn(int n){
    return 2*n + 1;
}

pii merge(pii a, pii b){
    if(a.ff < b.ff)return a;
    if(a.ff > b.ff)return b;
    return {a.ff, a.ss + b.ss};
}

void push(int v){
    if(!lz[v])return;

    t[2*v].ff += lz[v];
    t[2*v + 1].ff += lz[v];

    lz[2*v] += lz[v];
    lz[2*v + 1] += lz[v];

    lz[v] = 0;
}

void build(int v, int l, int r){
    if(l == r){
        t[v] = {0, 1};
        return;
    }
    int mid = (l + r) >> 1;
    build(2*v, l, mid);
    build(2*v + 1, mid + 1, r);

    t[v] = merge(t[2*v], t[2*v + 1]);
}

void update(int v, int tl, int tr, int l, int r, int add){

    push(v);

    if(tl > r || tr < l)return;

    if(l <= tl && tr <= r){
        lz[v] += add;
        t[v].ff += add;
        push(v);
        return;
    }

    push(v);

    int mid = (tl + tr) >> 1;

    if(l <= mid)update(2*v, tl, mid, l, r, add);
    if(r > mid)update(2*v + 1, mid + 1, tr, l, r, add);

    t[v] = merge(t[2*v], t[2*v + 1]);

}

void give_initial_chart(int HH, int WW, vector<int> R, vector<int> C) {
    W = WW;
    H = HH;
    tsz = H*W;

    build(1, 1, tsz);

    arr = vector<vector<int>>(H+1, vector<int>(W+1, 0));

    for(int i=0; i<H*W; ++i){
        arr[R[i] + 1][C[i] + 1] = i + 1;
        seats[i] = {R[i] + 1, C[i] + 1};
    }
    for(int i = 1; i<=H; ++i){
        for(int j = 1; j<=W; ++j){
            updateA({i, j});
            updateB({i, j});
        }
    }

}

int swap_seats(int a, int b){

    rewrite(seats[a], b + 1);
    rewrite(seats[b], a + 1);

    swap(seats[a], seats[b]);

    return (t[1].first == 1 ? t[1].second : 0);
}

void rewrite(pii pos, int val){

    deleteA(pos);
    for(int i = 0; i < 4; ++i){
        pii aux = pos;
        aux.x += dx[i];
        aux.y += dy[i];
        if(ok(aux)){
            deleteA(aux);
        }
    }
    deleteB(pos);
    for(int i=2; i<4; ++i){
        pii aux = pos;
        aux.x += dx[i];
        aux.y += dy[i];
        if(ok(aux)){
            deleteB(aux);
        }
    }

    arr[pos.x][pos.y] = val;

    updateA(pos);
    for(int i=0; i<4; ++i){
        pii aux = pos;
        aux.x += dx[i];
        aux.y += dy[i];
        if(ok(aux)){
            updateA(aux);
        }
    }
    updateB(pos);
    for(int i=2; i<4; ++i){
        pii aux = pos;
        aux.x += dx[i];
        aux.y += dy[i];
        if(ok(aux)){
            updateB(aux);
        }
    }
}


void deleteA(pii pos){
    int l = secondSmallestNeighbour(pos);
    int r = arr[pos.x][pos.y];
    if(r > l){
        update(1, 1, tsz, l, r - 1, -1);
    }
}

void updateA(pii pos){
    int l = secondSmallestNeighbour(pos);
    int r = arr[pos.x][pos.y];
    if(r > l){
        update(1, 1, tsz, l, r - 1, +1);
    }
}

void deleteB(pii pos){
    pii p = getB(pos);
    if(p.y > p.x){
        update(1, 1, tsz, p.x, p.y - 1, -1);
    }
}

void updateB(pii pos){
    pii p = getB(pos);
    if(p.y > p.x){
        update(1, 1, tsz, p.x, p.y - 1, +1);
    }
}

int secondSmallestNeighbour(pii pos){
    vector<int>s;
    for(int i = 0; i < 4; i++){
        pii aux = pos;
        aux.x += dx[i];
        aux.y += dy[i];
        if(ok(aux))s.push_back(arr[aux.x][aux.y]);
    }
    
    sort(all(s));
    
    if(s.size() > 1)return s[1];
    return tsz+1;
}

pii getB(pii pos){
    int l = arr[pos.x][pos.y];
    int r = tsz + 1;
    for(int i=0; i<4; ++i){
        pii aux = pos;
        aux.x += dx[i];
        aux.y += dy[i];
        if(ok(aux)){
            if(i < 2)
                r = min(r, arr[aux.x][aux.y]);
        }
    }
    return {l, r};
}

bool ok(pii pos){
    if(pos.x <= 0 || pos.x > H || pos.y <= 0 || pos.y > W)return 0;
    return 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