oj.uz

Submission #920627

# Submission time Handle Problem Language Result Execution time Memory
920627 2024-02-02T19:51:45 Z danikoynov Land of the Rainbow Gold (APIO17_rainbow) C++14
100 / 100
 931 ms 423508 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;
persistent_segment_tree nodes_tree;
persistent_segment_tree ver_tree;
persistent_segment_tree hor_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);
    nodes_tree.init(nodes);
    ver_tree.init(ver_edges);
    hor_tree.init(hor_edges);

}

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 = nodes_tree.query_rectangle(ar + 1, br, ac + 1, bc);///fen_nodes.range_query(ar + 1, br, ac + 1, bc) ;
    int E = 0;
    E = E + hor_tree.query_rectangle(ar + 1, br, ac, bc);
    E = E + ver_tree.query_rectangle(ar, br, ac + 1, bc);
    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 90 ms 379216 KB Output is correct
2 Correct 89 ms 379512 KB Output is correct
3 Correct 86 ms 379136 KB Output is correct
4 Correct 87 ms 379220 KB Output is correct
5 Correct 89 ms 379472 KB Output is correct
6 Correct 83 ms 379216 KB Output is correct
7 Correct 83 ms 379220 KB Output is correct
8 Correct 91 ms 379060 KB Output is correct
9 Correct 89 ms 379288 KB Output is correct
10 Correct 87 ms 379084 KB Output is correct
11 Correct 88 ms 379216 KB Output is correct
12 Correct 89 ms 379472 KB Output is correct
13 Correct 87 ms 379628 KB Output is correct
14 Correct 89 ms 379728 KB Output is correct
15 Correct 82 ms 379216 KB Output is correct
16 Correct 84 ms 379180 KB Output is correct
17 Correct 85 ms 379216 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 379180 KB Output is correct
2 Correct 85 ms 379216 KB Output is correct
3 Correct 411 ms 398384 KB Output is correct
4 Correct 574 ms 410960 KB Output is correct
5 Correct 614 ms 413580 KB Output is correct
6 Correct 478 ms 406412 KB Output is correct
7 Correct 566 ms 405868 KB Output is correct
8 Correct 143 ms 382884 KB Output is correct
9 Correct 581 ms 413824 KB Output is correct
10 Correct 600 ms 413576 KB Output is correct
11 Correct 498 ms 406176 KB Output is correct
12 Correct 414 ms 411616 KB Output is correct
13 Correct 446 ms 413568 KB Output is correct
14 Correct 445 ms 413312 KB Output is correct
15 Correct 391 ms 406200 KB Output is correct
16 Correct 432 ms 405068 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 379216 KB Output is correct
2 Correct 376 ms 410076 KB Output is correct
3 Correct 349 ms 420508 KB Output is correct
4 Correct 345 ms 413668 KB Output is correct
5 Correct 299 ms 407380 KB Output is correct
6 Correct 182 ms 385104 KB Output is correct
7 Correct 231 ms 390996 KB Output is correct
8 Correct 356 ms 406900 KB Output is correct
9 Correct 332 ms 403720 KB Output is correct
10 Correct 175 ms 385364 KB Output is correct
11 Correct 254 ms 394576 KB Output is correct
12 Correct 374 ms 410268 KB Output is correct
13 Correct 344 ms 420392 KB Output is correct
14 Correct 354 ms 413840 KB Output is correct
15 Correct 303 ms 407404 KB Output is correct
16 Correct 162 ms 384084 KB Output is correct
17 Correct 226 ms 391252 KB Output is correct
18 Correct 368 ms 410448 KB Output is correct
19 Correct 352 ms 415136 KB Output is correct
20 Correct 351 ms 415052 KB Output is correct
21 Correct 345 ms 406856 KB Output is correct
22 Correct 335 ms 403968 KB Output is correct
23 Correct 162 ms 385356 KB Output is correct
24 Correct 260 ms 394976 KB Output is correct
25 Correct 385 ms 410072 KB Output is correct
26 Correct 343 ms 420240 KB Output is correct
27 Correct 364 ms 413668 KB Output is correct
28 Correct 301 ms 407408 KB Output is correct
29 Correct 161 ms 384108 KB Output is correct
30 Correct 221 ms 391152 KB Output is correct
31 Correct 383 ms 410848 KB Output is correct
32 Correct 352 ms 415192 KB Output is correct
33 Correct 346 ms 415048 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 379216 KB Output is correct
2 Correct 89 ms 379512 KB Output is correct
3 Correct 86 ms 379136 KB Output is correct
4 Correct 87 ms 379220 KB Output is correct
5 Correct 89 ms 379472 KB Output is correct
6 Correct 83 ms 379216 KB Output is correct
7 Correct 83 ms 379220 KB Output is correct
8 Correct 91 ms 379060 KB Output is correct
9 Correct 89 ms 379288 KB Output is correct
10 Correct 87 ms 379084 KB Output is correct
11 Correct 88 ms 379216 KB Output is correct
12 Correct 89 ms 379472 KB Output is correct
13 Correct 87 ms 379628 KB Output is correct
14 Correct 89 ms 379728 KB Output is correct
15 Correct 82 ms 379216 KB Output is correct
16 Correct 84 ms 379180 KB Output is correct
17 Correct 85 ms 379216 KB Output is correct
18 Correct 725 ms 396128 KB Output is correct
19 Correct 253 ms 380648 KB Output is correct
20 Correct 220 ms 379984 KB Output is correct
21 Correct 226 ms 380112 KB Output is correct
22 Correct 244 ms 380180 KB Output is correct
23 Correct 260 ms 380648 KB Output is correct
24 Correct 219 ms 380136 KB Output is correct
25 Correct 230 ms 380520 KB Output is correct
26 Correct 241 ms 380728 KB Output is correct
27 Correct 435 ms 392784 KB Output is correct
28 Correct 266 ms 386416 KB Output is correct
29 Correct 322 ms 391764 KB Output is correct
30 Correct 601 ms 411296 KB Output is correct
31 Correct 86 ms 379264 KB Output is correct
32 Correct 559 ms 393040 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 379216 KB Output is correct
2 Correct 89 ms 379512 KB Output is correct
3 Correct 86 ms 379136 KB Output is correct
4 Correct 87 ms 379220 KB Output is correct
5 Correct 89 ms 379472 KB Output is correct
6 Correct 83 ms 379216 KB Output is correct
7 Correct 83 ms 379220 KB Output is correct
8 Correct 91 ms 379060 KB Output is correct
9 Correct 89 ms 379288 KB Output is correct
10 Correct 87 ms 379084 KB Output is correct
11 Correct 88 ms 379216 KB Output is correct
12 Correct 89 ms 379472 KB Output is correct
13 Correct 87 ms 379628 KB Output is correct
14 Correct 89 ms 379728 KB Output is correct
15 Correct 82 ms 379216 KB Output is correct
16 Correct 84 ms 379180 KB Output is correct
17 Correct 85 ms 379216 KB Output is correct
18 Correct 725 ms 396128 KB Output is correct
19 Correct 253 ms 380648 KB Output is correct
20 Correct 220 ms 379984 KB Output is correct
21 Correct 226 ms 380112 KB Output is correct
22 Correct 244 ms 380180 KB Output is correct
23 Correct 260 ms 380648 KB Output is correct
24 Correct 219 ms 380136 KB Output is correct
25 Correct 230 ms 380520 KB Output is correct
26 Correct 241 ms 380728 KB Output is correct
27 Correct 435 ms 392784 KB Output is correct
28 Correct 266 ms 386416 KB Output is correct
29 Correct 322 ms 391764 KB Output is correct
30 Correct 601 ms 411296 KB Output is correct
31 Correct 86 ms 379264 KB Output is correct
32 Correct 559 ms 393040 KB Output is correct
33 Correct 376 ms 410076 KB Output is correct
34 Correct 349 ms 420508 KB Output is correct
35 Correct 345 ms 413668 KB Output is correct
36 Correct 299 ms 407380 KB Output is correct
37 Correct 182 ms 385104 KB Output is correct
38 Correct 231 ms 390996 KB Output is correct
39 Correct 356 ms 406900 KB Output is correct
40 Correct 332 ms 403720 KB Output is correct
41 Correct 175 ms 385364 KB Output is correct
42 Correct 254 ms 394576 KB Output is correct
43 Correct 374 ms 410268 KB Output is correct
44 Correct 344 ms 420392 KB Output is correct
45 Correct 354 ms 413840 KB Output is correct
46 Correct 303 ms 407404 KB Output is correct
47 Correct 162 ms 384084 KB Output is correct
48 Correct 226 ms 391252 KB Output is correct
49 Correct 368 ms 410448 KB Output is correct
50 Correct 352 ms 415136 KB Output is correct
51 Correct 351 ms 415052 KB Output is correct
52 Correct 345 ms 406856 KB Output is correct
53 Correct 335 ms 403968 KB Output is correct
54 Correct 162 ms 385356 KB Output is correct
55 Correct 260 ms 394976 KB Output is correct
56 Correct 385 ms 410072 KB Output is correct
57 Correct 343 ms 420240 KB Output is correct
58 Correct 364 ms 413668 KB Output is correct
59 Correct 301 ms 407408 KB Output is correct
60 Correct 161 ms 384108 KB Output is correct
61 Correct 221 ms 391152 KB Output is correct
62 Correct 383 ms 410848 KB Output is correct
63 Correct 352 ms 415192 KB Output is correct
64 Correct 346 ms 415048 KB Output is correct
65 Correct 411 ms 398384 KB Output is correct
66 Correct 574 ms 410960 KB Output is correct
67 Correct 614 ms 413580 KB Output is correct
68 Correct 478 ms 406412 KB Output is correct
69 Correct 566 ms 405868 KB Output is correct
70 Correct 143 ms 382884 KB Output is correct
71 Correct 581 ms 413824 KB Output is correct
72 Correct 600 ms 413576 KB Output is correct
73 Correct 498 ms 406176 KB Output is correct
74 Correct 414 ms 411616 KB Output is correct
75 Correct 446 ms 413568 KB Output is correct
76 Correct 445 ms 413312 KB Output is correct
77 Correct 391 ms 406200 KB Output is correct
78 Correct 432 ms 405068 KB Output is correct
79 Correct 894 ms 410808 KB Output is correct
80 Correct 931 ms 407408 KB Output is correct
81 Correct 324 ms 389000 KB Output is correct
82 Correct 373 ms 398104 KB Output is correct
83 Correct 575 ms 413816 KB Output is correct
84 Correct 425 ms 423508 KB Output is correct
85 Correct 448 ms 417356 KB Output is correct
86 Correct 392 ms 410864 KB Output is correct
87 Correct 218 ms 387712 KB Output is correct
88 Correct 290 ms 394836 KB Output is correct
89 Correct 433 ms 414164 KB Output is correct
90 Correct 514 ms 418552 KB Output is correct
91 Correct 541 ms 418476 KB Output is correct