Submission #172640

#	Time	Username	Problem	Language	Result	Execution time	Memory
172640		dolphingarlic	Land of the Rainbow Gold (APIO17_rainbow)	C++14	23 / 100	3055 ms	204636 KiB

rainbow

/*
APIO 2017 Rainbow
- We can view a rectangle as a planar graph
    - Put temporary rivers on the outside of the rectangle
    - Each river segment is a node and adjacent rivers constitute an edge
- This problem then becomes finding the number of faces of a planar graph
- We can solve this with Euler's formula
- By Euler's formula, we have
    F = E - V + 1 + C
  where F is faces, E is edges, V is vertices, and C is the number of components
- Each corner of a square is a vertex and each side of a square is an edge if it has a river
*/
 
#include "rainbow.h"
#include <bits/stdc++.h>
#pragma GCC Optimize("unroll-loops")
#pragma GCC Optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
 
int rnd() { return ((rand() % (1 << 15)) << 16) + (rand() % (1 << 15)); }
 
struct TreapNode {
    TreapNode *l, *r;
    int pos, key, mn, mx;
    int val, g;
    
    TreapNode(int position, int value) {
        l = r = nullptr;
        mn = mx = pos = position;
        key = rnd();
        val = g = value;
    }
 
    void update() {
        g = val;
        if (l) g += l->g;
        if (r) g += r->g;
        mn = (l ? l->mn : pos);
        mx = (r ? r->mx : pos);
    }
};
 
struct Treap {
    TreapNode *root;
 
    Treap() {
        root = nullptr;
        srand(rnd());
    }
 
    void split(TreapNode *t, int pos, TreapNode *&l, TreapNode *&r) {
        if (t == nullptr) {
            l = r = nullptr;
            return;
        }
        if (t->pos < pos) {
            split(t->r, pos, l, r);
            t->r = l;
            l = t;
        } else {
            split(t->l, pos, l, r);
            t->l = r;
            r = t;
        }
        t->update();
    }
 
    TreapNode* merge(TreapNode *l, TreapNode *r) {
        if (!l || !r) return l ? l : r;
        if (l->key < r->key) {
            l->r = merge(l->r, r);
            l->update();
            return l;
        } else {
            r->l = merge(l, r->l);
            r->update();
            return r;
        }
    }
 
    bool find(int pos) {
        TreapNode *t = root;
        while (t) {
            if (t->pos == pos) return true;
            if (t->pos > pos) t = t->l;
            else t = t->r;
        }
        return false;
    }
 
    void update(TreapNode *t, int pos, int val) {
        if (t->pos == pos) {
            t->val = val;
            t->update();
            return;
        }
        if (t->pos > pos) update(t->l, pos, val);
        else update(t->r, pos, val);
        t->update();
    }
 
    void insert(int pos, int val) {
        if (find(pos)) update(root, pos, val);
        else {
            TreapNode *l, *r;
            split(root, pos, l, r);
            root = merge(merge(l, new TreapNode(pos, val)), r);
        }
    }
 
    int query(TreapNode *t, int st, int en) {
        if (t->mx < st || en < t->mn) return 0;
        if (st <= t->mn && t->mx <= en) return t->g;
        
        int ans = (st <= t->pos && t->pos <= en ? t->val : 0);
        if (t->l) ans += query(t->l, st, en);
        if (t->r) ans += query(t->r, st, en);
        return ans;
    }
    int query(int st, int en) {
        if (!root) return 0;
        return query(root, st, en);
    }
};
 
struct Segtree {
    Segtree *l, *r;
    Treap treap;
    int lo, hi;
 
    Segtree() { l = r = nullptr; }
    Segtree(int st, int en) {
        l = r = nullptr;
        lo = st, hi = en;
    }
 
    void new_left() {
        if (!l) l = new Segtree(lo, (lo + hi) / 2);
    }
    void new_right() {
        if (!r) r = new Segtree((lo + hi) / 2 + 1, hi);
    }
    void fix(int pos) {
        int val = 0;
        if (l) val += l->treap.query(pos, pos);
        if (r) val += r->treap.query(pos, pos);
        treap.insert(pos, val);
    }
 
    void update(int x, int y, int val) {
        if (hi < x || x < lo) return;
        if (lo == hi) {
            treap.insert(y, val);
            return;
        }
 
        if (x <= (lo + hi) / 2) {
            new_left();
            l->update(x, y, val);
        } else {
            new_right();
            r->update(x, y, val);
        }
        fix(y);
    }
 
    int query(int t, int b, int st, int en) {
        if (hi < t || b < lo) return 0;
        if (t <= lo && hi <= b) return treap.query(st, en);
 
        int ans = 0;
        if (l) ans += l->query(t, b, st, en);
        if (r) ans += r->query(t, b, st, en);
        return ans;
    }
};
 
Segtree vertices, edges, rivers;
set<pair<int, int>> v, e, r;
int mx_r, mn_r, mx_c, mn_c;
 
void add_river(int x, int y) {
    v.insert({x, y}); v.insert({x + 1, y}); v.insert({x, y + 1}); v.insert({x + 1, y + 1});
    e.insert({2 * x - 1, 2 * y}); e.insert({2 * x + 1, 2 * y});
    e.insert({2 * x, 2 * y - 1}); e.insert({2 * x, 2 * y + 1});
    r.insert({x, y});
}
 
void init(int R, int C, int sr, int sc, int M, char *S) {
    srand(12341234);
    vertices = Segtree(1, R + 1);
    edges = Segtree(1, 2 * R + 1);
    rivers = Segtree(1, R);
 
    add_river(sr, sc);
    mx_r = mn_r = sr;
    mx_c = mn_c = sc;
    FOR(i, 0, M) {
        if (S[i] == 'N') sr--;
        if (S[i] == 'E') sc++;
        if (S[i] == 'S') sr++;
        if (S[i] == 'W') sc--;
        add_river(sr, sc);
        mx_r = max(mx_r, sr);
        mn_r = min(mn_r, sr);
        mx_c = max(mx_c, sc);
        mn_c = min(mn_c, sc);
    }
 
    for (pair<int, int> i : v) vertices.update(i.first, i.second, 1);
    for (pair<int, int> i : e) edges.update(i.first, i.second, 1);
    for (pair<int, int> i : r) rivers.update(i.first, i.second, 1);
}
 
int colour(int ar, int ac, int br, int bc) {
    int E = edges.query(2 * ar, 2 * br, 2 * ac, 2 * bc);
    int V = vertices.query(ar + 1, br, ac + 1, bc);
    int R = rivers.query(ar, br, ac, bc);
    int C = (ar >= mn_r || br <= mx_r || ac >= mn_c || bc <= mx_c ? 1 : 2);
    return E - V + C - R;
}

Compilation message (stderr)

rainbow.cpp:16:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("unroll-loops")
 
rainbow.cpp:17:0: warning: ignoring #pragma GCC Optimize [-Wunknown-pragmas]
 #pragma GCC Optimize("O3")

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26