oj.uz

Submission #920210

# Submission time Handle Problem Language Result Execution time Memory
920210 2024-02-02T09:27:59 Z danikoynov Land of the Rainbow Gold (APIO17_rainbow) C++14
35 / 100
 3000 ms 184544 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;

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);
    }
    fen_river.build();
    fen_nodes.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 + query_hor_edges(ar + 1, ac, br, bc) + (bc - ac + 1) * 2;
    E = E + query_ver_edges(ar, ac + 1, br, 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 28 ms 41304 KB Output is correct
2 Correct 41 ms 41560 KB Output is correct
3 Correct 28 ms 41304 KB Output is correct
4 Correct 30 ms 41304 KB Output is correct
5 Correct 44 ms 41560 KB Output is correct
6 Correct 26 ms 41044 KB Output is correct
7 Correct 24 ms 41048 KB Output is correct
8 Correct 25 ms 41052 KB Output is correct
9 Correct 25 ms 41080 KB Output is correct
10 Correct 25 ms 41040 KB Output is correct
11 Correct 31 ms 41304 KB Output is correct
12 Correct 38 ms 41296 KB Output is correct
13 Correct 52 ms 41820 KB Output is correct
14 Correct 67 ms 41816 KB Output is correct
15 Correct 24 ms 41048 KB Output is correct
16 Correct 26 ms 41040 KB Output is correct
17 Correct 24 ms 41048 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 41040 KB Output is correct
2 Correct 24 ms 41048 KB Output is correct
3 Execution timed out 3029 ms 173888 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 41048 KB Output is correct
2 Correct 923 ms 184484 KB Output is correct
3 Correct 220 ms 85016 KB Output is correct
4 Correct 489 ms 139992 KB Output is correct
5 Correct 294 ms 100260 KB Output is correct
6 Correct 115 ms 50256 KB Output is correct
7 Correct 179 ms 59012 KB Output is correct
8 Correct 730 ms 153212 KB Output is correct
9 Correct 588 ms 133280 KB Output is correct
10 Correct 113 ms 52184 KB Output is correct
11 Correct 271 ms 81216 KB Output is correct
12 Correct 899 ms 184508 KB Output is correct
13 Correct 225 ms 84816 KB Output is correct
14 Correct 482 ms 140044 KB Output is correct
15 Correct 298 ms 100384 KB Output is correct
16 Correct 111 ms 48504 KB Output is correct
17 Correct 177 ms 58960 KB Output is correct
18 Correct 334 ms 88316 KB Output is correct
19 Correct 443 ms 129252 KB Output is correct
20 Correct 567 ms 145692 KB Output is correct
21 Correct 732 ms 153272 KB Output is correct
22 Correct 593 ms 133204 KB Output is correct
23 Correct 115 ms 52048 KB Output is correct
24 Correct 273 ms 81388 KB Output is correct
25 Correct 897 ms 184544 KB Output is correct
26 Correct 219 ms 84816 KB Output is correct
27 Correct 494 ms 140248 KB Output is correct
28 Correct 301 ms 100460 KB Output is correct
29 Correct 109 ms 48440 KB Output is correct
30 Correct 176 ms 59320 KB Output is correct
31 Correct 328 ms 88476 KB Output is correct
32 Correct 445 ms 129140 KB Output is correct
33 Correct 554 ms 145932 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 41304 KB Output is correct
2 Correct 41 ms 41560 KB Output is correct
3 Correct 28 ms 41304 KB Output is correct
4 Correct 30 ms 41304 KB Output is correct
5 Correct 44 ms 41560 KB Output is correct
6 Correct 26 ms 41044 KB Output is correct
7 Correct 24 ms 41048 KB Output is correct
8 Correct 25 ms 41052 KB Output is correct
9 Correct 25 ms 41080 KB Output is correct
10 Correct 25 ms 41040 KB Output is correct
11 Correct 31 ms 41304 KB Output is correct
12 Correct 38 ms 41296 KB Output is correct
13 Correct 52 ms 41820 KB Output is correct
14 Correct 67 ms 41816 KB Output is correct
15 Correct 24 ms 41048 KB Output is correct
16 Correct 26 ms 41040 KB Output is correct
17 Correct 24 ms 41048 KB Output is correct
18 Execution timed out 3049 ms 66068 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 41304 KB Output is correct
2 Correct 41 ms 41560 KB Output is correct
3 Correct 28 ms 41304 KB Output is correct
4 Correct 30 ms 41304 KB Output is correct
5 Correct 44 ms 41560 KB Output is correct
6 Correct 26 ms 41044 KB Output is correct
7 Correct 24 ms 41048 KB Output is correct
8 Correct 25 ms 41052 KB Output is correct
9 Correct 25 ms 41080 KB Output is correct
10 Correct 25 ms 41040 KB Output is correct
11 Correct 31 ms 41304 KB Output is correct
12 Correct 38 ms 41296 KB Output is correct
13 Correct 52 ms 41820 KB Output is correct
14 Correct 67 ms 41816 KB Output is correct
15 Correct 24 ms 41048 KB Output is correct
16 Correct 26 ms 41040 KB Output is correct
17 Correct 24 ms 41048 KB Output is correct
18 Execution timed out 3049 ms 66068 KB Time limit exceeded
19 Halted 0 ms 0 KB -