oj.uz

Submission #920622

# Submission time Handle Problem Language Result Execution time Memory
920622 2024-02-02T19:48:34 Z danikoynov Land of the Rainbow Gold (APIO17_rainbow) C++14
62 / 100
 3000 ms 619444 KB 
#include "rainbow.h"
#include<bits/stdc++.h>

using namespace std;

const int inf = 1e9;

const int maxn = 2e5 + 10;

struct node
{
    int lc, rc, sum;

    node()
    {
        lc = rc = -1;
        sum = 0;
    }
};


struct persistent_segment_tree
{
    node tree[30 * maxn];
    int roots[maxn], last_used;
    vector < int > data[maxn];

    int update(int root, int left, int right, int pos, int val)
    {
        int new_node = ++ last_used;
        if (root != -1)
            tree[new_node] = tree[root];
        if (left == right)
        {
            tree[new_node].sum += val;
            return new_node;
        }

        int mid = (left + right) / 2;
        if (pos <= mid)
            tree[new_node].lc = update(tree[new_node].lc, left, mid, pos, val);
        else
            tree[new_node].rc = update(tree[new_node].rc, mid + 1, right, pos, val);

        tree[new_node].sum = 0;
        if (tree[new_node].lc != -1)
            tree[new_node].sum += tree[tree[new_node].lc].sum;
                if (tree[new_node].rc != -1)
            tree[new_node].sum += tree[tree[new_node].rc].sum;

        return new_node;
    }

    int query(int root, int left, int right, int qleft, int qright)
    {
        if (left > qright || right < qleft || root == -1)
            return 0;
        if (left >= qleft && right <= qright)
            return tree[root].sum;

        int mid = (left + right) / 2;
        return query(tree[root].lc, left, mid, qleft, qright) +
                query(tree[root].rc, mid + 1, right, qleft, qright);
    }


    void init(set < pair < int, int > > &my_set)
    {
        last_used = 0;
        for (pair < int, int > cur : my_set)
        {
            data[cur.first].push_back(cur.second);
        }

        roots[0] = -1;
        for (int i = 1; i < maxn; i ++)
        {
            roots[i] = roots[i - 1];
            for (int cur : data[i])
            {
                roots[i] = update(roots[i], 1, maxn - 1, cur, 1);
            }
        }
    }
    int query_rectangle(int lb, int rb, int dw, int up)
    {
        return query(roots[rb], 1, maxn - 1, dw, up) -
                query(roots[lb - 1], 1, maxn - 1, dw, up);
    }
};

persistent_segment_tree river_tree;

set < pair < int, int > > nodes, ver_edges, hor_edges, river;

int min_x = inf, max_x = -inf, min_y = inf, max_y = -inf;


struct fenwick_2d
{
    map < int, int > data[maxn];
    vector < int > vec[maxn], pref[maxn];

    void build()
    {


        for (int i = 0; i < maxn; i ++)
        {
            vec[i].push_back(0);
            pref[i].push_back(0);
            for (pair < int, int > cur : data[i])
            {
                //if (i == 2)
                {
                    //cout << cur.first << " ------- " << cur.second << " " << vec[i].back().second << endl;
                }
                int new_val = pref[i].back() + cur.second;
                vec[i].push_back(cur.first);
                pref[i].push_back(new_val);
            }
        }

        /**for (int i = 0; i < 10; i ++)
        {
            cout << "step " << i << endl;
            for (int cur : vec[i])
                cout << cur << " ";
            cout << endl;
        }*/
    }

    void add(int pos, int val)
    {
        for (int i = pos; i < maxn; i += (i & -i))
        {
            data[i][val] ++;
        }
    }

    int bin_search(int idx, int val)
    {
        int lf = 0, rf = (int)(vec[idx].size()) - 1;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (vec[idx][mf] <= val)
                lf = mf + 1;
            else
                rf = mf - 1;
        }
        return lf;
    }

    int query(int pos, int lb, int rb)
    {
        ///cout << "QUERY " << pos << " " << lb << " " << rb << endl;
        int ans = 0;
        for (int i = pos; i > 0; i -= (i & -i))
        {

            int left = bin_search(i, lb - 1), right = bin_search(i, rb);
            //cout << "left right " << left << " " << right << " " << vec[i][left].second << " :: " << vec[i][right].second << endl;
            ans = ans + (pref[i][right - 1 ]- pref[i][left - 1]);
        }
        //cout << "Ans " << ans << endl;
        return ans;
    }

    int range_query(int from, int to, int lb, int rb)
    {
        return query(to, lb, rb) - query(from - 1, lb, rb);
    }
};

fenwick_2d fen_river;
fenwick_2d fen_nodes;
fenwick_2d fen_hor;
fenwick_2d fen_ver;


void add_node(int x, int y)
{
    nodes.insert({x, y});
}

void add_hor_edge(int x, int y)
{
    hor_edges.insert({x, y});
}

void add_ver_edge(int x, int y)
{
    ver_edges.insert({x, y});
}

void add_river(int x, int y)
{
    add_node(x, y);
    add_node(x, y + 1);
    add_node(x + 1, y);
    add_node(x + 1, y + 1);
    add_hor_edge(x, y);
    add_hor_edge(x + 1, y);
    add_ver_edge(x, y);
    add_ver_edge(x, y + 1);
    min_x = min(min_x, x);
    max_x = max(max_x, x);
    min_y = min(min_y, y);
    max_y = max(max_y, y);
    river.insert({x, y});

}

void init(int R, int C, int sr, int sc, int M, char *S)
{
    add_river(sr, sc);
    for (int i = 0; i < M; i ++)
    {
        if (S[i] == 'N')
            sr --;
        else if (S[i] == 'S')
            sr ++;
        else if (S[i] == 'W')
            sc --;
        else if (S[i] == 'E')
            sc ++;
        else assert(false);

        add_river(sr, sc);
    }

    for (pair < int, int > cur : river)
    {
        fen_river.add(cur.first, cur.second);
    }
    for (pair < int, int > cur : nodes)
    {
        fen_nodes.add(cur.first, cur.second);
    }
    for (pair < int, int > cur : hor_edges)
    {
        fen_hor.add(cur.first, cur.second);
    }
    for (pair < int, int > cur : ver_edges)
    {
        fen_ver.add(cur.first, cur.second);
    }
    fen_river.build();
    fen_nodes.build();
    fen_hor.build();
    fen_ver.build();

    river_tree.init(river);

}

int query_nodes(int ar, int ac, int br, int bc)
{
    int cnt = 0;
    for (pair < int, int > cur : nodes)
    {
        if (cur.first >= ar && cur.first <= br &&
                cur.second >= ac && cur.second <= bc)
            cnt ++;
    }
    return cnt;
}

int query_hor_edges(int ar, int ac, int br, int bc)
{
    int cnt = 0;
    for (pair < int, int > cur : hor_edges)
    {
        if (cur.first >= ar && cur.first <= br &&
                cur.second >= ac && cur.second <= bc)
            cnt ++;
    }
    return cnt;
}

int query_ver_edges(int ar, int ac, int br, int bc)
{
    int cnt = 0;
    for (pair < int, int > cur : ver_edges)
    {
        if (cur.first >= ar && cur.first <= br &&
                cur.second >= ac && cur.second <= bc)
            cnt ++;
    }
    return cnt;
}

int query_river(int ar, int ac, int br, int bc)
{
    int cnt = 0;
    for (pair < int, int > cur : river)
    {
        if (cur.first >= ar && cur.first <= br &&
                cur.second >= ac && cur.second <= bc)
            cnt ++;
    }
    return cnt;
}

int colour(int ar, int ac, int br, int bc)
{
    int V = fen_nodes.range_query(ar + 1, br, ac + 1, bc) + (br - ar + 2) * 2 + (bc - ac) * 2;
    int E = 0;
    E = E + fen_hor.range_query(ar + 1, br, ac, bc) + (bc - ac + 1) * 2;
    E = E + fen_ver.range_query(ar, br, ac + 1, bc) + (br - ar + 1) * 2;
    int C = 1;

    if (ar < min_x && ac < min_y && br > max_x && bc > max_y)
        C ++;
    /// V + F = E + C + 1
    /// F = E - V + C + 1

    int F = E - V + C - river_tree.query_rectangle(ar, br, ac, bc);///fen_river.range_query(ar, br, ac, bc); //query_river(ar, ac, br, bc);
    ///cout << "V " << V << " E " << E << " C " << C << endl;
    //cout << "Faces " << F << endl;
    ///exit(0);
    return F;

}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 201812 KB Output is correct
2 Correct 103 ms 202292 KB Output is correct
3 Correct 99 ms 201948 KB Output is correct
4 Correct 96 ms 201880 KB Output is correct
5 Correct 100 ms 202208 KB Output is correct
6 Correct 94 ms 201600 KB Output is correct
7 Correct 103 ms 201436 KB Output is correct
8 Correct 97 ms 201456 KB Output is correct
9 Correct 96 ms 201552 KB Output is correct
10 Correct 96 ms 201552 KB Output is correct
11 Correct 96 ms 201812 KB Output is correct
12 Correct 103 ms 202056 KB Output is correct
13 Correct 104 ms 202644 KB Output is correct
14 Correct 105 ms 202580 KB Output is correct
15 Correct 96 ms 201552 KB Output is correct
16 Correct 95 ms 201568 KB Output is correct
17 Correct 95 ms 201560 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 201568 KB Output is correct
2 Correct 95 ms 201560 KB Output is correct
3 Correct 1713 ms 455336 KB Output is correct
4 Execution timed out 3050 ms 619444 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 201552 KB Output is correct
2 Correct 1787 ms 465904 KB Output is correct
3 Correct 389 ms 261288 KB Output is correct
4 Correct 1066 ms 371116 KB Output is correct
5 Correct 583 ms 299812 KB Output is correct
6 Correct 241 ms 214916 KB Output is correct
7 Correct 339 ms 227412 KB Output is correct
8 Correct 1666 ms 403892 KB Output is correct
9 Correct 1253 ms 364540 KB Output is correct
10 Correct 242 ms 218168 KB Output is correct
11 Correct 574 ms 270028 KB Output is correct
12 Correct 1759 ms 466124 KB Output is correct
13 Correct 383 ms 261204 KB Output is correct
14 Correct 1033 ms 371360 KB Output is correct
15 Correct 603 ms 299884 KB Output is correct
16 Correct 213 ms 212436 KB Output is correct
17 Correct 331 ms 227920 KB Output is correct
18 Correct 675 ms 268836 KB Output is correct
19 Correct 822 ms 350096 KB Output is correct
20 Correct 1117 ms 382792 KB Output is correct
21 Correct 1461 ms 403792 KB Output is correct
22 Correct 1221 ms 364692 KB Output is correct
23 Correct 247 ms 218104 KB Output is correct
24 Correct 541 ms 270268 KB Output is correct
25 Correct 1747 ms 465860 KB Output is correct
26 Correct 384 ms 261204 KB Output is correct
27 Correct 1008 ms 371104 KB Output is correct
28 Correct 592 ms 299872 KB Output is correct
29 Correct 216 ms 212468 KB Output is correct
30 Correct 349 ms 227376 KB Output is correct
31 Correct 623 ms 268884 KB Output is correct
32 Correct 820 ms 350116 KB Output is correct
33 Correct 1201 ms 382964 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 201812 KB Output is correct
2 Correct 103 ms 202292 KB Output is correct
3 Correct 99 ms 201948 KB Output is correct
4 Correct 96 ms 201880 KB Output is correct
5 Correct 100 ms 202208 KB Output is correct
6 Correct 94 ms 201600 KB Output is correct
7 Correct 103 ms 201436 KB Output is correct
8 Correct 97 ms 201456 KB Output is correct
9 Correct 96 ms 201552 KB Output is correct
10 Correct 96 ms 201552 KB Output is correct
11 Correct 96 ms 201812 KB Output is correct
12 Correct 103 ms 202056 KB Output is correct
13 Correct 104 ms 202644 KB Output is correct
14 Correct 105 ms 202580 KB Output is correct
15 Correct 96 ms 201552 KB Output is correct
16 Correct 95 ms 201568 KB Output is correct
17 Correct 95 ms 201560 KB Output is correct
18 Correct 727 ms 240940 KB Output is correct
19 Correct 283 ms 210260 KB Output is correct
20 Correct 256 ms 205980 KB Output is correct
21 Correct 231 ms 206148 KB Output is correct
22 Correct 251 ms 207180 KB Output is correct
23 Correct 276 ms 210484 KB Output is correct
24 Correct 234 ms 205832 KB Output is correct
25 Correct 242 ms 206416 KB Output is correct
26 Correct 252 ms 207188 KB Output is correct
27 Correct 514 ms 231900 KB Output is correct
28 Correct 369 ms 219520 KB Output is correct
29 Correct 474 ms 230996 KB Output is correct
30 Correct 844 ms 272524 KB Output is correct
31 Correct 104 ms 201560 KB Output is correct
32 Correct 611 ms 233260 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 201812 KB Output is correct
2 Correct 103 ms 202292 KB Output is correct
3 Correct 99 ms 201948 KB Output is correct
4 Correct 96 ms 201880 KB Output is correct
5 Correct 100 ms 202208 KB Output is correct
6 Correct 94 ms 201600 KB Output is correct
7 Correct 103 ms 201436 KB Output is correct
8 Correct 97 ms 201456 KB Output is correct
9 Correct 96 ms 201552 KB Output is correct
10 Correct 96 ms 201552 KB Output is correct
11 Correct 96 ms 201812 KB Output is correct
12 Correct 103 ms 202056 KB Output is correct
13 Correct 104 ms 202644 KB Output is correct
14 Correct 105 ms 202580 KB Output is correct
15 Correct 96 ms 201552 KB Output is correct
16 Correct 95 ms 201568 KB Output is correct
17 Correct 95 ms 201560 KB Output is correct
18 Correct 727 ms 240940 KB Output is correct
19 Correct 283 ms 210260 KB Output is correct
20 Correct 256 ms 205980 KB Output is correct
21 Correct 231 ms 206148 KB Output is correct
22 Correct 251 ms 207180 KB Output is correct
23 Correct 276 ms 210484 KB Output is correct
24 Correct 234 ms 205832 KB Output is correct
25 Correct 242 ms 206416 KB Output is correct
26 Correct 252 ms 207188 KB Output is correct
27 Correct 514 ms 231900 KB Output is correct
28 Correct 369 ms 219520 KB Output is correct
29 Correct 474 ms 230996 KB Output is correct
30 Correct 844 ms 272524 KB Output is correct
31 Correct 104 ms 201560 KB Output is correct
32 Correct 611 ms 233260 KB Output is correct
33 Correct 1787 ms 465904 KB Output is correct
34 Correct 389 ms 261288 KB Output is correct
35 Correct 1066 ms 371116 KB Output is correct
36 Correct 583 ms 299812 KB Output is correct
37 Correct 241 ms 214916 KB Output is correct
38 Correct 339 ms 227412 KB Output is correct
39 Correct 1666 ms 403892 KB Output is correct
40 Correct 1253 ms 364540 KB Output is correct
41 Correct 242 ms 218168 KB Output is correct
42 Correct 574 ms 270028 KB Output is correct
43 Correct 1759 ms 466124 KB Output is correct
44 Correct 383 ms 261204 KB Output is correct
45 Correct 1033 ms 371360 KB Output is correct
46 Correct 603 ms 299884 KB Output is correct
47 Correct 213 ms 212436 KB Output is correct
48 Correct 331 ms 227920 KB Output is correct
49 Correct 675 ms 268836 KB Output is correct
50 Correct 822 ms 350096 KB Output is correct
51 Correct 1117 ms 382792 KB Output is correct
52 Correct 1461 ms 403792 KB Output is correct
53 Correct 1221 ms 364692 KB Output is correct
54 Correct 247 ms 218104 KB Output is correct
55 Correct 541 ms 270268 KB Output is correct
56 Correct 1747 ms 465860 KB Output is correct
57 Correct 384 ms 261204 KB Output is correct
58 Correct 1008 ms 371104 KB Output is correct
59 Correct 592 ms 299872 KB Output is correct
60 Correct 216 ms 212468 KB Output is correct
61 Correct 349 ms 227376 KB Output is correct
62 Correct 623 ms 268884 KB Output is correct
63 Correct 820 ms 350116 KB Output is correct
64 Correct 1201 ms 382964 KB Output is correct
65 Correct 1713 ms 455336 KB Output is correct
66 Execution timed out 3050 ms 619444 KB Time limit exceeded
67 Halted 0 ms 0 KB -