oj.uz

Submission #920215

# Submission time Handle Problem Language Result Execution time Memory
920215 2024-02-02T09:36:26 Z danikoynov Land of the Rainbow Gold (APIO17_rainbow) C++14
62 / 100
 3000 ms 541624 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 < 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();
}

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 80 ms 125804 KB Output is correct
2 Correct 82 ms 126288 KB Output is correct
3 Correct 80 ms 125776 KB Output is correct
4 Correct 81 ms 125776 KB Output is correct
5 Correct 84 ms 126204 KB Output is correct
6 Correct 77 ms 125452 KB Output is correct
7 Correct 75 ms 125484 KB Output is correct
8 Correct 83 ms 125524 KB Output is correct
9 Correct 79 ms 125520 KB Output is correct
10 Correct 79 ms 125520 KB Output is correct
11 Correct 83 ms 125780 KB Output is correct
12 Correct 79 ms 126032 KB Output is correct
13 Correct 89 ms 126436 KB Output is correct
14 Correct 83 ms 126692 KB Output is correct
15 Correct 121 ms 125496 KB Output is correct
16 Correct 85 ms 125676 KB Output is correct
17 Correct 83 ms 125588 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 125676 KB Output is correct
2 Correct 83 ms 125588 KB Output is correct
3 Correct 1818 ms 376112 KB Output is correct
4 Execution timed out 3060 ms 541624 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 125496 KB Output is correct
2 Correct 1744 ms 389416 KB Output is correct
3 Correct 341 ms 182396 KB Output is correct
4 Correct 983 ms 293596 KB Output is correct
5 Correct 572 ms 222512 KB Output is correct
6 Correct 207 ms 138832 KB Output is correct
7 Correct 300 ms 151120 KB Output is correct
8 Correct 1417 ms 327344 KB Output is correct
9 Correct 1166 ms 288128 KB Output is correct
10 Correct 212 ms 141904 KB Output is correct
11 Correct 510 ms 193580 KB Output is correct
12 Correct 1723 ms 389180 KB Output is correct
13 Correct 340 ms 182196 KB Output is correct
14 Correct 981 ms 293620 KB Output is correct
15 Correct 565 ms 222256 KB Output is correct
16 Correct 200 ms 136272 KB Output is correct
17 Correct 319 ms 151128 KB Output is correct
18 Correct 592 ms 192336 KB Output is correct
19 Correct 910 ms 272140 KB Output is correct
20 Correct 1133 ms 305056 KB Output is correct
21 Correct 1471 ms 327184 KB Output is correct
22 Correct 1259 ms 288452 KB Output is correct
23 Correct 226 ms 142080 KB Output is correct
24 Correct 522 ms 193580 KB Output is correct
25 Correct 1780 ms 389204 KB Output is correct
26 Correct 365 ms 182200 KB Output is correct
27 Correct 983 ms 293784 KB Output is correct
28 Correct 649 ms 222256 KB Output is correct
29 Correct 210 ms 136388 KB Output is correct
30 Correct 310 ms 151228 KB Output is correct
31 Correct 573 ms 192420 KB Output is correct
32 Correct 856 ms 272296 KB Output is correct
33 Correct 1202 ms 304856 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 125804 KB Output is correct
2 Correct 82 ms 126288 KB Output is correct
3 Correct 80 ms 125776 KB Output is correct
4 Correct 81 ms 125776 KB Output is correct
5 Correct 84 ms 126204 KB Output is correct
6 Correct 77 ms 125452 KB Output is correct
7 Correct 75 ms 125484 KB Output is correct
8 Correct 83 ms 125524 KB Output is correct
9 Correct 79 ms 125520 KB Output is correct
10 Correct 79 ms 125520 KB Output is correct
11 Correct 83 ms 125780 KB Output is correct
12 Correct 79 ms 126032 KB Output is correct
13 Correct 89 ms 126436 KB Output is correct
14 Correct 83 ms 126692 KB Output is correct
15 Correct 121 ms 125496 KB Output is correct
16 Correct 85 ms 125676 KB Output is correct
17 Correct 83 ms 125588 KB Output is correct
18 Correct 734 ms 163664 KB Output is correct
19 Correct 290 ms 133204 KB Output is correct
20 Correct 207 ms 128552 KB Output is correct
21 Correct 221 ms 129104 KB Output is correct
22 Correct 244 ms 129860 KB Output is correct
23 Correct 267 ms 133300 KB Output is correct
24 Correct 230 ms 128736 KB Output is correct
25 Correct 233 ms 129432 KB Output is correct
26 Correct 237 ms 130232 KB Output is correct
27 Correct 458 ms 154576 KB Output is correct
28 Correct 374 ms 142556 KB Output is correct
29 Correct 492 ms 153552 KB Output is correct
30 Correct 801 ms 194820 KB Output is correct
31 Correct 84 ms 125780 KB Output is correct
32 Correct 578 ms 156004 KB Output is correct

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 125804 KB Output is correct
2 Correct 82 ms 126288 KB Output is correct
3 Correct 80 ms 125776 KB Output is correct
4 Correct 81 ms 125776 KB Output is correct
5 Correct 84 ms 126204 KB Output is correct
6 Correct 77 ms 125452 KB Output is correct
7 Correct 75 ms 125484 KB Output is correct
8 Correct 83 ms 125524 KB Output is correct
9 Correct 79 ms 125520 KB Output is correct
10 Correct 79 ms 125520 KB Output is correct
11 Correct 83 ms 125780 KB Output is correct
12 Correct 79 ms 126032 KB Output is correct
13 Correct 89 ms 126436 KB Output is correct
14 Correct 83 ms 126692 KB Output is correct
15 Correct 121 ms 125496 KB Output is correct
16 Correct 85 ms 125676 KB Output is correct
17 Correct 83 ms 125588 KB Output is correct
18 Correct 734 ms 163664 KB Output is correct
19 Correct 290 ms 133204 KB Output is correct
20 Correct 207 ms 128552 KB Output is correct
21 Correct 221 ms 129104 KB Output is correct
22 Correct 244 ms 129860 KB Output is correct
23 Correct 267 ms 133300 KB Output is correct
24 Correct 230 ms 128736 KB Output is correct
25 Correct 233 ms 129432 KB Output is correct
26 Correct 237 ms 130232 KB Output is correct
27 Correct 458 ms 154576 KB Output is correct
28 Correct 374 ms 142556 KB Output is correct
29 Correct 492 ms 153552 KB Output is correct
30 Correct 801 ms 194820 KB Output is correct
31 Correct 84 ms 125780 KB Output is correct
32 Correct 578 ms 156004 KB Output is correct
33 Correct 1744 ms 389416 KB Output is correct
34 Correct 341 ms 182396 KB Output is correct
35 Correct 983 ms 293596 KB Output is correct
36 Correct 572 ms 222512 KB Output is correct
37 Correct 207 ms 138832 KB Output is correct
38 Correct 300 ms 151120 KB Output is correct
39 Correct 1417 ms 327344 KB Output is correct
40 Correct 1166 ms 288128 KB Output is correct
41 Correct 212 ms 141904 KB Output is correct
42 Correct 510 ms 193580 KB Output is correct
43 Correct 1723 ms 389180 KB Output is correct
44 Correct 340 ms 182196 KB Output is correct
45 Correct 981 ms 293620 KB Output is correct
46 Correct 565 ms 222256 KB Output is correct
47 Correct 200 ms 136272 KB Output is correct
48 Correct 319 ms 151128 KB Output is correct
49 Correct 592 ms 192336 KB Output is correct
50 Correct 910 ms 272140 KB Output is correct
51 Correct 1133 ms 305056 KB Output is correct
52 Correct 1471 ms 327184 KB Output is correct
53 Correct 1259 ms 288452 KB Output is correct
54 Correct 226 ms 142080 KB Output is correct
55 Correct 522 ms 193580 KB Output is correct
56 Correct 1780 ms 389204 KB Output is correct
57 Correct 365 ms 182200 KB Output is correct
58 Correct 983 ms 293784 KB Output is correct
59 Correct 649 ms 222256 KB Output is correct
60 Correct 210 ms 136388 KB Output is correct
61 Correct 310 ms 151228 KB Output is correct
62 Correct 573 ms 192420 KB Output is correct
63 Correct 856 ms 272296 KB Output is correct
64 Correct 1202 ms 304856 KB Output is correct
65 Correct 1818 ms 376112 KB Output is correct
66 Execution timed out 3060 ms 541624 KB Time limit exceeded
67 Halted 0 ms 0 KB -