oj.uz

Submission #172625

# Submission time Handle Problem Language Result Execution time Memory
172625 2020-01-02T08:31:00 Z dolphingarlic Land of the Rainbow Gold (APIO17_rainbow) C++14
23 / 100
 3000 ms 213672 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(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;
}

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 5 ms 632 KB Output is correct
4 Correct 8 ms 760 KB Output is correct
5 Correct 21 ms 1380 KB Output is correct
6 Correct 2 ms 376 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 376 KB Output is correct
10 Correct 2 ms 392 KB Output is correct
11 Correct 9 ms 760 KB Output is correct
12 Correct 14 ms 1016 KB Output is correct
13 Correct 26 ms 1756 KB Output is correct
14 Correct 34 ms 2040 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 256 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 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 1031 ms 61164 KB Output is correct
4 Correct 1671 ms 100008 KB Output is correct
5 Correct 1624 ms 97588 KB Output is correct
6 Correct 1153 ms 71780 KB Output is correct
7 Correct 1390 ms 70984 KB Output is correct
8 Correct 87 ms 4088 KB Output is correct
9 Correct 1704 ms 100020 KB Output is correct
10 Correct 1708 ms 97656 KB Output is correct
11 Correct 1235 ms 71992 KB Output is correct
12 Correct 1261 ms 92920 KB Output is correct
13 Correct 1317 ms 99756 KB Output is correct
14 Correct 1304 ms 97584 KB Output is correct
15 Correct 1025 ms 71880 KB Output is correct
16 Correct 1127 ms 72636 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Execution timed out 3036 ms 213672 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 5 ms 632 KB Output is correct
4 Correct 8 ms 760 KB Output is correct
5 Correct 21 ms 1380 KB Output is correct
6 Correct 2 ms 376 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 376 KB Output is correct
10 Correct 2 ms 392 KB Output is correct
11 Correct 9 ms 760 KB Output is correct
12 Correct 14 ms 1016 KB Output is correct
13 Correct 26 ms 1756 KB Output is correct
14 Correct 34 ms 2040 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Execution timed out 3096 ms 56596 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 5 ms 632 KB Output is correct
4 Correct 8 ms 760 KB Output is correct
5 Correct 21 ms 1380 KB Output is correct
6 Correct 2 ms 376 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 376 KB Output is correct
10 Correct 2 ms 392 KB Output is correct
11 Correct 9 ms 760 KB Output is correct
12 Correct 14 ms 1016 KB Output is correct
13 Correct 26 ms 1756 KB Output is correct
14 Correct 34 ms 2040 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 256 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Execution timed out 3096 ms 56596 KB Time limit exceeded
19 Halted 0 ms 0 KB -