oj.uz

Submission #172645

# Submission time Handle Problem Language Result Execution time Memory
172645 2020-01-02T09:11:54 Z dolphingarlic Land of the Rainbow Gold (APIO17_rainbow) C++14
23 / 100
 3000 ms 182264 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 = 1) {
        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) {
    vertices.update(x, y);
    vertices.update(x + 1, y);
    vertices.update(x, y + 1);
    vertices.update(x + 1, y + 1);
    edges.update(2 * x - 1, 2 * y);
    edges.update(2 * x + 1, 2 * y);
    edges.update(2 * x, 2 * y - 1);
    edges.update(2 * x, 2 * y + 1);
    rivers.update(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);
    }
}
 
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 376 KB Output is correct
2 Correct 23 ms 888 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 9 ms 632 KB Output is correct
5 Correct 32 ms 1092 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 14 ms 632 KB Output is correct
12 Correct 21 ms 760 KB Output is correct
13 Correct 29 ms 1272 KB Output is correct
14 Correct 60 ms 1528 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 348 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 348 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 779 ms 41628 KB Output is correct
4 Correct 1369 ms 69104 KB Output is correct
5 Correct 1497 ms 66868 KB Output is correct
6 Correct 1224 ms 47432 KB Output is correct
7 Correct 1456 ms 46988 KB Output is correct
8 Correct 153 ms 1104 KB Output is correct
9 Correct 1406 ms 68916 KB Output is correct
10 Correct 1514 ms 67064 KB Output is correct
11 Correct 1257 ms 47352 KB Output is correct
12 Correct 875 ms 64120 KB Output is correct
13 Correct 974 ms 68836 KB Output is correct
14 Correct 1031 ms 66792 KB Output is correct
15 Correct 1002 ms 47608 KB Output is correct
16 Correct 901 ms 49908 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 3069 ms 182264 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 376 KB Output is correct
2 Correct 23 ms 888 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 9 ms 632 KB Output is correct
5 Correct 32 ms 1092 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 14 ms 632 KB Output is correct
12 Correct 21 ms 760 KB Output is correct
13 Correct 29 ms 1272 KB Output is correct
14 Correct 60 ms 1528 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Execution timed out 3033 ms 39452 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 376 KB Output is correct
2 Correct 23 ms 888 KB Output is correct
3 Correct 7 ms 504 KB Output is correct
4 Correct 9 ms 632 KB Output is correct
5 Correct 32 ms 1092 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 256 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 14 ms 632 KB Output is correct
12 Correct 21 ms 760 KB Output is correct
13 Correct 29 ms 1272 KB Output is correct
14 Correct 60 ms 1528 KB Output is correct
15 Correct 2 ms 256 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Execution timed out 3033 ms 39452 KB Time limit exceeded
19 Halted 0 ms 0 KB -