Submission #75417

#	Time	Username	Problem	Language	Result	Execution time	Memory
75417		mammamia	Seats (IOI18_seats)	C++14	100 / 100	3135 ms	111776 KiB

seats

#include "seats.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int NMAX = 4000005;

const int dxa[] = {1, 0, -1, 0};
const int dya[] = {0, 1, 0, -1};

const int dxb[] = {0, -1, -1};
const int dyb[] = {-1, -1, 0};

const int dxbdown[] = {0, 1, 1};
const int dybdown[] = {1, 1, 0};

typedef pair<int, int> pii;

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

void updateAtPositionA(pii pos);
void deleteAtPositionA(pii pos);
void updateAtPositionB(pii pos);
void deleteAtPositionB(pii pos);
int secondSmallestNeighbourA(pii pos);
pii getCornerIntervalB(pii pos);
bool inBound(pii pos);
void addInterval(int l, int r);
void subInterval(int l, int r);
void rewriteAtPosition(pii pos, int val);

vector<vector<int>> arr;

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

pii tcombine(pii a, pii b){
    if(a.first < b.first){
        return a;
    } else if(a.first > b.first) {
        return b;
    } else {
        return {a.first, a.second + b.second};
    }
}

void push(int n){
    if(lz[n]){
        t[n].first += lz[n];
        lz[ln(n)] += lz[n];
        lz[rn(n)] += lz[n];
        lz[n] = 0;
    }
}

void build(int n, int l, int r){
    if(l == r){
        t[n] = {0, 1};
        return;
    }
    int pivot = (l+r)>>1;
    build(ln(n), l, pivot);
    build(rn(n), pivot + 1, r);

    t[n] = tcombine(t[ln(n)], t[rn(n)]);
}

void update(int n, int l, int r, int ql, int qr, int add){
    push(n);
    if(ql <= l && r <= qr){
        lz[n] += add;
        push(n);
        return;
    }
    int pivot = (l+r)>>1;
    if(ql <= pivot)
        update(ln(n), l, pivot, ql, qr, add);
    if(qr > pivot)
        update(rn(n), pivot+1, r, ql, qr, add);

    push(ln(n));
    push(rn(n));
    t[n] = tcombine(t[ln(n)], t[rn(n)]);

}

void give_initial_chart(int _H, int _W, vector<int> R, vector<int> C) {
    W = _W;
    H = _H;
    tsz = H*W; // add the right endpoint
    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)
        {
            updateAtPositionA({i, j});
            updateAtPositionB({i, j});
        }
    }
    //cout<<t[1].first<<" "<<t[1].second<<"\n";

}

int swap_seats(int a, int b) {
    pii pa = seats[a];
    pii pb = seats[b];

    //cout<<"swap "<<a<<" "<<b<<"\n";


    rewriteAtPosition(pa, b + 1);
    rewriteAtPosition(pb, a + 1);

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


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

void rewriteAtPosition(pii pos, int val){

    // delete previous connections
    deleteAtPositionA(pos);
    for(int i=0; i<4; ++i){
        pii aux = pos;
        aux.x += dxa[i];
        aux.y += dya[i];
        if(inBound(aux)){
            deleteAtPositionA(aux);
        }
    }
    deleteAtPositionB(pos);
    for(int i=2; i<4; ++i){
        pii aux = pos;
        aux.x += dxa[i];
        aux.y += dya[i];
        if(inBound(aux)){
            deleteAtPositionB(aux);
        }
    }

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

    // add the new connections
    updateAtPositionA(pos);
    for(int i=0; i<4; ++i){
        pii aux = pos;
        aux.x += dxa[i];
        aux.y += dya[i];
        if(inBound(aux)){
            updateAtPositionA(aux);
        }
    }
    updateAtPositionB(pos);
    for(int i=2; i<4; ++i){
        pii aux = pos;
        aux.x += dxa[i];
        aux.y += dya[i];
        if(inBound(aux)){
            updateAtPositionB(aux);
        }
    }
}


void deleteAtPositionA(pii pos){
    int l = secondSmallestNeighbourA(pos);
    int r = arr[pos.x][pos.y];
    if(r > l){
        subInterval(l, r - 1);
    }
}

void updateAtPositionA(pii pos){
    int l = secondSmallestNeighbourA(pos);
    int r = arr[pos.x][pos.y];
    if(r > l){
        addInterval(l, r - 1);
    }
}

void deleteAtPositionB(pii pos){
    pii p = getCornerIntervalB(pos);
    if(p.y > p.x){
        subInterval(p.x, p.y - 1);
    }
}

void updateAtPositionB(pii pos){
    pii p = getCornerIntervalB(pos);
    if(p.y > p.x){
        addInterval(p.x, p.y - 1);
    }
}

int secondSmallestNeighbourA(pii pos){
    set<int> countSet;
    for(int i=0; i<4; ++i){
        pii aux = pos;
        aux.x += dxa[i];
        aux.y += dya[i];
        if(inBound(aux)){
            countSet.insert(arr[aux.x][aux.y]);
        }
    }
    if(countSet.size() > 1){
        return *(++countSet.begin());
    } else {
        return tsz+1;
    }
}

pii getCornerIntervalB(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 += dxa[i];
        aux.y += dya[i];
        if(inBound(aux)){
            if(i < 2)
                r = min(r, arr[aux.x][aux.y]);
        }
    }
    //cout<<"corner for "<<pos.x<<" "<<pos.y<<" "<<l<<" "<<r<<"\n";
    return {l, r};
}

bool inBound(pii pos){
    if(pos.x > 0 && pos.x <= H){
        if(pos.y > 0 && pos.y <= W){
            return 1;
        }
    }
    return 0;
}

void addInterval(int l, int r){

    //cout<<"add "<<l<<" "<<r<<"\n";
    update(1, 1, tsz, l, r, +1);
}

void subInterval(int l, int r){
    //cout<<"sub "<<l<<" "<<r<<"\n";
    update(1, 1, tsz, l, r, -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