oj.uz

Submission #172628

# Submission time Handle Problem Language Result Execution time Memory
172628 2020-01-02T08:33:57 Z dolphingarlic Land of the Rainbow Gold (APIO17_rainbow) C++14
23 / 100
 3000 ms 213700 KB 
/*
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>
#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(1e9+7);
    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;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 17 ms 1144 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 8 ms 632 KB Output is correct
5 Correct 24 ms 1272 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 9 ms 632 KB Output is correct
12 Correct 14 ms 988 KB Output is correct
13 Correct 28 ms 1656 KB Output is correct
14 Correct 33 ms 2016 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 982 ms 58612 KB Output is correct
4 Correct 1637 ms 96988 KB Output is correct
5 Correct 1670 ms 94832 KB Output is correct
6 Correct 1150 ms 69208 KB Output is correct
7 Correct 1366 ms 68284 KB Output is correct
8 Correct 83 ms 1144 KB Output is correct
9 Correct 1698 ms 97008 KB Output is correct
10 Correct 1682 ms 94712 KB Output is correct
11 Correct 1227 ms 69064 KB Output is correct
12 Correct 1228 ms 90360 KB Output is correct
13 Correct 1305 ms 96888 KB Output is correct
14 Correct 1309 ms 94712 KB Output is correct
15 Correct 1002 ms 69036 KB Output is correct
16 Correct 1108 ms 69752 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Execution timed out 3054 ms 213700 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 17 ms 1144 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 8 ms 632 KB Output is correct
5 Correct 24 ms 1272 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 9 ms 632 KB Output is correct
12 Correct 14 ms 988 KB Output is correct
13 Correct 28 ms 1656 KB Output is correct
14 Correct 33 ms 2016 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Execution timed out 3096 ms 54468 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 17 ms 1144 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 8 ms 632 KB Output is correct
5 Correct 24 ms 1272 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 9 ms 632 KB Output is correct
12 Correct 14 ms 988 KB Output is correct
13 Correct 28 ms 1656 KB Output is correct
14 Correct 33 ms 2016 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Execution timed out 3096 ms 54468 KB Time limit exceeded
19 Halted 0 ms 0 KB -