oj.uz

Submission #920211

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

using namespace std;

const int inf = 1e9;

const int maxn = 2e5 + 10;

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 < pair < int, int > > vec[maxn];

    void build()
    {


        for (int i = 0; i < maxn; i ++)
        {
            vec[i].push_back({0, 0});
            for (pair < int, int > cur : data[i])
            {
                //if (i == 2)
                {
                    //cout << cur.first << " ------- " << cur.second << " " << vec[i].back().second << endl;
                }
                int new_val = vec[i].back().second + cur.second;
                vec[i].push_back({cur.first, 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].first <= 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 + (vec[i][right - 1 ].second - vec[i][left - 1].second);
        }
        //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();
}

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 - 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 49 ms 82000 KB Output is correct
2 Correct 52 ms 82416 KB Output is correct
3 Correct 50 ms 82000 KB Output is correct
4 Correct 49 ms 82000 KB Output is correct
5 Correct 54 ms 82512 KB Output is correct
6 Correct 45 ms 81744 KB Output is correct
7 Correct 45 ms 81744 KB Output is correct
8 Correct 45 ms 81748 KB Output is correct
9 Correct 46 ms 81748 KB Output is correct
10 Correct 47 ms 81744 KB Output is correct
11 Correct 52 ms 82260 KB Output is correct
12 Correct 51 ms 82256 KB Output is correct
13 Correct 53 ms 82768 KB Output is correct
14 Correct 56 ms 82800 KB Output is correct
15 Correct 46 ms 81756 KB Output is correct
16 Correct 45 ms 81840 KB Output is correct
17 Correct 45 ms 81744 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 81840 KB Output is correct
2 Correct 45 ms 81744 KB Output is correct
3 Correct 1555 ms 333808 KB Output is correct
4 Execution timed out 3033 ms 495612 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 81756 KB Output is correct
2 Correct 1600 ms 340420 KB Output is correct
3 Correct 293 ms 141392 KB Output is correct
4 Correct 876 ms 251224 KB Output is correct
5 Correct 459 ms 178972 KB Output is correct
6 Correct 166 ms 95056 KB Output is correct
7 Correct 257 ms 107032 KB Output is correct
8 Correct 1305 ms 280356 KB Output is correct
9 Correct 1065 ms 243588 KB Output is correct
10 Correct 169 ms 98128 KB Output is correct
11 Correct 423 ms 147860 KB Output is correct
12 Correct 1644 ms 340304 KB Output is correct
13 Correct 271 ms 141420 KB Output is correct
14 Correct 887 ms 251364 KB Output is correct
15 Correct 457 ms 179040 KB Output is correct
16 Correct 155 ms 92240 KB Output is correct
17 Correct 251 ms 107224 KB Output is correct
18 Correct 503 ms 148304 KB Output is correct
19 Correct 776 ms 229844 KB Output is correct
20 Correct 995 ms 262592 KB Output is correct
21 Correct 1321 ms 280148 KB Output is correct
22 Correct 1066 ms 243700 KB Output is correct
23 Correct 176 ms 98372 KB Output is correct
24 Correct 422 ms 147864 KB Output is correct
25 Correct 1642 ms 340200 KB Output is correct
26 Correct 282 ms 141420 KB Output is correct
27 Correct 873 ms 251376 KB Output is correct
28 Correct 466 ms 179348 KB Output is correct
29 Correct 158 ms 92328 KB Output is correct
30 Correct 269 ms 107536 KB Output is correct
31 Correct 500 ms 148532 KB Output is correct
32 Correct 727 ms 229744 KB Output is correct
33 Correct 1002 ms 262876 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 82000 KB Output is correct
2 Correct 52 ms 82416 KB Output is correct
3 Correct 50 ms 82000 KB Output is correct
4 Correct 49 ms 82000 KB Output is correct
5 Correct 54 ms 82512 KB Output is correct
6 Correct 45 ms 81744 KB Output is correct
7 Correct 45 ms 81744 KB Output is correct
8 Correct 45 ms 81748 KB Output is correct
9 Correct 46 ms 81748 KB Output is correct
10 Correct 47 ms 81744 KB Output is correct
11 Correct 52 ms 82260 KB Output is correct
12 Correct 51 ms 82256 KB Output is correct
13 Correct 53 ms 82768 KB Output is correct
14 Correct 56 ms 82800 KB Output is correct
15 Correct 46 ms 81756 KB Output is correct
16 Correct 45 ms 81840 KB Output is correct
17 Correct 45 ms 81744 KB Output is correct
18 Correct 676 ms 120596 KB Output is correct
19 Correct 240 ms 90548 KB Output is correct
20 Correct 182 ms 85840 KB Output is correct
21 Correct 186 ms 86484 KB Output is correct
22 Correct 193 ms 87376 KB Output is correct
23 Correct 250 ms 90528 KB Output is correct
24 Correct 186 ms 86204 KB Output is correct
25 Correct 196 ms 86608 KB Output is correct
26 Correct 203 ms 87536 KB Output is correct
27 Correct 423 ms 111924 KB Output is correct
28 Correct 328 ms 100016 KB Output is correct
29 Correct 425 ms 110928 KB Output is correct
30 Correct 697 ms 151884 KB Output is correct
31 Correct 48 ms 82000 KB Output is correct
32 Correct 532 ms 113512 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 82000 KB Output is correct
2 Correct 52 ms 82416 KB Output is correct
3 Correct 50 ms 82000 KB Output is correct
4 Correct 49 ms 82000 KB Output is correct
5 Correct 54 ms 82512 KB Output is correct
6 Correct 45 ms 81744 KB Output is correct
7 Correct 45 ms 81744 KB Output is correct
8 Correct 45 ms 81748 KB Output is correct
9 Correct 46 ms 81748 KB Output is correct
10 Correct 47 ms 81744 KB Output is correct
11 Correct 52 ms 82260 KB Output is correct
12 Correct 51 ms 82256 KB Output is correct
13 Correct 53 ms 82768 KB Output is correct
14 Correct 56 ms 82800 KB Output is correct
15 Correct 46 ms 81756 KB Output is correct
16 Correct 45 ms 81840 KB Output is correct
17 Correct 45 ms 81744 KB Output is correct
18 Correct 676 ms 120596 KB Output is correct
19 Correct 240 ms 90548 KB Output is correct
20 Correct 182 ms 85840 KB Output is correct
21 Correct 186 ms 86484 KB Output is correct
22 Correct 193 ms 87376 KB Output is correct
23 Correct 250 ms 90528 KB Output is correct
24 Correct 186 ms 86204 KB Output is correct
25 Correct 196 ms 86608 KB Output is correct
26 Correct 203 ms 87536 KB Output is correct
27 Correct 423 ms 111924 KB Output is correct
28 Correct 328 ms 100016 KB Output is correct
29 Correct 425 ms 110928 KB Output is correct
30 Correct 697 ms 151884 KB Output is correct
31 Correct 48 ms 82000 KB Output is correct
32 Correct 532 ms 113512 KB Output is correct
33 Correct 1600 ms 340420 KB Output is correct
34 Correct 293 ms 141392 KB Output is correct
35 Correct 876 ms 251224 KB Output is correct
36 Correct 459 ms 178972 KB Output is correct
37 Correct 166 ms 95056 KB Output is correct
38 Correct 257 ms 107032 KB Output is correct
39 Correct 1305 ms 280356 KB Output is correct
40 Correct 1065 ms 243588 KB Output is correct
41 Correct 169 ms 98128 KB Output is correct
42 Correct 423 ms 147860 KB Output is correct
43 Correct 1644 ms 340304 KB Output is correct
44 Correct 271 ms 141420 KB Output is correct
45 Correct 887 ms 251364 KB Output is correct
46 Correct 457 ms 179040 KB Output is correct
47 Correct 155 ms 92240 KB Output is correct
48 Correct 251 ms 107224 KB Output is correct
49 Correct 503 ms 148304 KB Output is correct
50 Correct 776 ms 229844 KB Output is correct
51 Correct 995 ms 262592 KB Output is correct
52 Correct 1321 ms 280148 KB Output is correct
53 Correct 1066 ms 243700 KB Output is correct
54 Correct 176 ms 98372 KB Output is correct
55 Correct 422 ms 147864 KB Output is correct
56 Correct 1642 ms 340200 KB Output is correct
57 Correct 282 ms 141420 KB Output is correct
58 Correct 873 ms 251376 KB Output is correct
59 Correct 466 ms 179348 KB Output is correct
60 Correct 158 ms 92328 KB Output is correct
61 Correct 269 ms 107536 KB Output is correct
62 Correct 500 ms 148532 KB Output is correct
63 Correct 727 ms 229744 KB Output is correct
64 Correct 1002 ms 262876 KB Output is correct
65 Correct 1555 ms 333808 KB Output is correct
66 Execution timed out 3033 ms 495612 KB Time limit exceeded
67 Halted 0 ms 0 KB -