oj.uz

Submission #172640

# Submission time Handle Problem Language Result Execution time Memory
172640 2020-01-02T09:05:38 Z dolphingarlic Land of the Rainbow Gold (APIO17_rainbow) C++14
23 / 100
 3000 ms 204636 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>
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 22 ms 1272 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 8 ms 632 KB Output is correct
5 Correct 21 ms 1272 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 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 256 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 1784 KB Output is correct
14 Correct 34 ms 2044 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 128 KB Output is correct
17 Correct 2 ms 256 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 128 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 1122 ms 58556 KB Output is correct
4 Correct 1653 ms 97120 KB Output is correct
5 Correct 1591 ms 94888 KB Output is correct
6 Correct 1157 ms 68956 KB Output is correct
7 Correct 1345 ms 68252 KB Output is correct
8 Correct 85 ms 1272 KB Output is correct
9 Correct 1688 ms 97284 KB Output is correct
10 Correct 1850 ms 95012 KB Output is correct
11 Correct 1305 ms 69036 KB Output is correct
12 Correct 1279 ms 90256 KB Output is correct
13 Correct 1345 ms 97268 KB Output is correct
14 Correct 1299 ms 94976 KB Output is correct
15 Correct 1000 ms 69092 KB Output is correct
16 Correct 1189 ms 70124 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Execution timed out 3055 ms 204636 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 22 ms 1272 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 8 ms 632 KB Output is correct
5 Correct 21 ms 1272 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 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 256 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 1784 KB Output is correct
14 Correct 34 ms 2044 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 128 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Execution timed out 3032 ms 53828 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 22 ms 1272 KB Output is correct
3 Correct 7 ms 632 KB Output is correct
4 Correct 8 ms 632 KB Output is correct
5 Correct 21 ms 1272 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 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 256 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 1784 KB Output is correct
14 Correct 34 ms 2044 KB Output is correct
15 Correct 2 ms 252 KB Output is correct
16 Correct 2 ms 128 KB Output is correct
17 Correct 2 ms 256 KB Output is correct
18 Execution timed out 3032 ms 53828 KB Time limit exceeded
19 Halted 0 ms 0 KB -