Codeforces Round #295 (Div. 1 B / Div. 2 D) - Cubes

Problem Statement:
521B - Cubes

Solution:
This is a nice problem. Firstly, you can build a DAG out of the stacks of cubes, in which for each cube C(x, y), draw a directed edge from C to all C' with coordinates (x-1, y+1), (x, y+1) and (x+1, y+1). We also keep track of the total number of in-degree of each cubes, for which stored in an array support[i], which intuitively means cube i is supported by support[i] cubes.



What is the criteria to check whether a cube can be removed from the stack of cubes? At first one will think, of course cubes that are located on top. However if we think more carefully, actually any cubes that can be removed "safely" without affecting the cubes it supports will be one valid candidate. This means, for each cubes j that cube i support, if support[j] is all bigger than 1, it is safe to remove i. Let S be the set of cubes that we can remove.

At each turn, we will choose a cube from S, and depending on the parity of the turn, we will need to remove the highest or the lowest numbered cube out of S. Let's say we choose cube i from S. This means we remove i from S, and remove i from the stacks of cubes. Notice that now all cubes j that was supported by cube i will have support[j] decreased by one, and hence all cubes that are supported these j must be rechecked for safety of removal; i.e. if coordinate of of i is (x,y), we must update support[j] of each cubes supported by i, and check (x-2,y), (x-1,y), (x+1,y) and (x+2,y) for safety of removal, as some will becomes unsafe to remove, and hence must be taken out of S. Furthermore, when we remove cube i from the stacks of cubes, we also relieve cubes j that were supporting i, hence we must also check for their safety of removal as they might be added to S.

Finally, to efficiently support S, I used segment trees, but other data structures might work too.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
#include <cassert>
using namespace std;



int INF = 12345678;
long long MOD = (long long) 1e9 + 9LL;
int tree[400005][2];

map<pair<long long,long long>,int> ptr;
int support[100005];
vector<pair<long long,long long> > coor;
int in_tree[100005], used[100005];
int M;


void update(int p, int S, int L, int R, int val) {
    if(S < L || R < S) return;
    if(L == R && R == S) {
        if(val == 0) {
            tree[p][0] = -1;
            tree[p][1] = INF;
        } else {
            tree[p][0] = S;
            tree[p][1] = S;
        }
        return;
    }
    int M = (L+R)/2;
    update(2*p, S, L, M, val);
    update(2*p+1, S, M+1, R, val);
    tree[p][0] = max(tree[2*p][0], tree[2*p+1][0]);
    tree[p][1] = min(tree[2*p][1], tree[2*p+1][1]);
}

int rmaxq(int p, int S, int T, int L, int R) {
    if(T < L || R < S) return -1;
    if(S <= L && R <= T) return tree[p][0];
    int M = (L+R)/2;
    int left = rmaxq(2*p, S, T, L, M);
    int right = rmaxq(2*p+1, S, T, M+1, R);
    return max(left, right);
}

int rminq(int p, int S, int T, int L, int R) {
    if(T < L || R < S) return INF;
    if(S <= L && R <= T) return tree[p][1];
    int M = (L+R)/2;
    int left = rmaxq(2*p, S, T, L, M);
    int right = rmaxq(2*p+1, S, T, M+1, R);
    return min(left, right);
}

void build(int p, int L, int R) {
    if(L==R) {
        tree[p][0] = -1;
        tree[p][1] = INF;
        return;
    }
    int M = (L+R)/2;
    build(2*p, L, M);
    build(2*p+1,M+1,R);
    tree[p][0] = -1;
    tree[p][1] = INF;
}

int supportedBy(long long x, long long y) {
    if(ptr.count(make_pair(x,y))) {
        return support[ptr[make_pair(x,y)]];
    }
    return INF;
}

bool isRemovable(int u) {
    long long x = coor[u].first;
    long long y = coor[u].second;
    return supportedBy(x-1,y+1) > 1 && supportedBy(x,y+1) > 1 && supportedBy(x+1,y+1) > 1;
}

void insert_to_tree(int u) {
    if(used[u])return;
    if(in_tree[u]) return;
    in_tree[u] = 1;
    update(1, u, 0, M-1, 1);
}

void remove_from_tree(int u) {
    if(used[u])return;
    if(in_tree[u] == 0) return;
    in_tree[u] = 0;
    update(1, u, 0, M-1, 0);
}

void remove_support(long long x, long long y) {
    if(ptr.count(make_pair(x,y))){
        support[ptr[make_pair(x,y)]]--;
    }
}

void revalidate(long long x, long long y) {
    if(ptr.count(make_pair(x,y))){
        int u = ptr[make_pair(x,y)];
        if(isRemovable(u)) {
            insert_to_tree(u);
        } else {
            remove_from_tree(u);
        }
    }
}

void add_support(long long x, long long y) {
    if(ptr.count(make_pair(x,y))){
        support[ptr[make_pair(x,y)]]++;
    }
}

int main(){
    scanf("%d",&M);
    long long x, y;
    for(int i=0;i<M;++i){
        cin >> x >> y;
        coor.push_back(make_pair(x,y));
        ptr[make_pair(x,y)] = i;
    }

    build(1, 0, M-1);

    for(int i=0;i<M;++i){
        x = coor[i].first;
        y = coor[i].second;
        add_support(x-1,y+1);
        add_support(x,y+1);
        add_support(x+1,y+1);
    }

    for(int i=0;i<M;++i){
        if(isRemovable(i)) {
            insert_to_tree(i);
        }
    }

    int ans[100005];

    for(int cur = 0; cur < M; ++cur) {
        int u;
        if(cur % 2) {
            u = rminq(1, 0, M-1, 0, M-1);
        } else {
            u = rmaxq(1, 0, M-1, 0, M-1);
        }
        assert(u!=-1 && u != INF);
        x = coor[u].first;
        y = coor[u].second;
        ans[cur] = u;
        remove_from_tree(u);
        used[u] = 1;
        support[u] = INF;
        remove_support(x-1,y+1);
        remove_support(x, y+1);
        remove_support(x+1, y+1);
        revalidate(x-2,y);
        revalidate(x-1,y);
        revalidate(x+1,y);
        revalidate(x+2,y);
        revalidate(x,y-1);
        revalidate(x-1,y-1);
        revalidate(x+1,y-1);
    }
    long long sum = 0;
    for(int i=0;i<M;++i){
        sum *= M;
        sum %= MOD;
        sum += ans[i];
        sum %= MOD;
    }
    cout << sum << endl;
}