oj.uz

Submission #920209

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

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);
    }
    fen_river.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 = query_nodes(ar + 1, ac + 1, br, 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 17 ms 20824 KB Output is correct
2 Correct 38 ms 20920 KB Output is correct
3 Correct 18 ms 20828 KB Output is correct
4 Correct 19 ms 20936 KB Output is correct
5 Correct 43 ms 21080 KB Output is correct
6 Correct 12 ms 20568 KB Output is correct
7 Correct 13 ms 20568 KB Output is correct
8 Correct 12 ms 20572 KB Output is correct
9 Correct 12 ms 20572 KB Output is correct
10 Correct 12 ms 20568 KB Output is correct
11 Correct 21 ms 20956 KB Output is correct
12 Correct 31 ms 20824 KB Output is correct
13 Correct 54 ms 21080 KB Output is correct
14 Correct 63 ms 21336 KB Output is correct
15 Correct 16 ms 20980 KB Output is correct
16 Correct 12 ms 20568 KB Output is correct
17 Correct 13 ms 20568 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 20568 KB Output is correct
2 Correct 13 ms 20568 KB Output is correct
3 Execution timed out 3034 ms 94888 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 20980 KB Output is correct
2 Correct 429 ms 93016 KB Output is correct
3 Correct 185 ms 53840 KB Output is correct
4 Correct 296 ms 81492 KB Output is correct
5 Correct 197 ms 56548 KB Output is correct
6 Correct 97 ms 27988 KB Output is correct
7 Correct 139 ms 34896 KB Output is correct
8 Correct 382 ms 87972 KB Output is correct
9 Correct 335 ms 76780 KB Output is correct
10 Correct 80 ms 28612 KB Output is correct
11 Correct 185 ms 44308 KB Output is correct
12 Correct 446 ms 92976 KB Output is correct
13 Correct 196 ms 53764 KB Output is correct
14 Correct 291 ms 81640 KB Output is correct
15 Correct 195 ms 56552 KB Output is correct
16 Correct 83 ms 26448 KB Output is correct
17 Correct 135 ms 34896 KB Output is correct
18 Correct 247 ms 56660 KB Output is correct
19 Correct 278 ms 76348 KB Output is correct
20 Correct 325 ms 81364 KB Output is correct
21 Correct 389 ms 87944 KB Output is correct
22 Correct 328 ms 77052 KB Output is correct
23 Correct 81 ms 28496 KB Output is correct
24 Correct 191 ms 44508 KB Output is correct
25 Correct 431 ms 92852 KB Output is correct
26 Correct 181 ms 53840 KB Output is correct
27 Correct 294 ms 81492 KB Output is correct
28 Correct 201 ms 56548 KB Output is correct
29 Correct 84 ms 26452 KB Output is correct
30 Correct 144 ms 34968 KB Output is correct
31 Correct 243 ms 56780 KB Output is correct
32 Correct 294 ms 76244 KB Output is correct
33 Correct 315 ms 81380 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20824 KB Output is correct
2 Correct 38 ms 20920 KB Output is correct
3 Correct 18 ms 20828 KB Output is correct
4 Correct 19 ms 20936 KB Output is correct
5 Correct 43 ms 21080 KB Output is correct
6 Correct 12 ms 20568 KB Output is correct
7 Correct 13 ms 20568 KB Output is correct
8 Correct 12 ms 20572 KB Output is correct
9 Correct 12 ms 20572 KB Output is correct
10 Correct 12 ms 20568 KB Output is correct
11 Correct 21 ms 20956 KB Output is correct
12 Correct 31 ms 20824 KB Output is correct
13 Correct 54 ms 21080 KB Output is correct
14 Correct 63 ms 21336 KB Output is correct
15 Correct 16 ms 20980 KB Output is correct
16 Correct 12 ms 20568 KB Output is correct
17 Correct 13 ms 20568 KB Output is correct
18 Execution timed out 3031 ms 39188 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 20824 KB Output is correct
2 Correct 38 ms 20920 KB Output is correct
3 Correct 18 ms 20828 KB Output is correct
4 Correct 19 ms 20936 KB Output is correct
5 Correct 43 ms 21080 KB Output is correct
6 Correct 12 ms 20568 KB Output is correct
7 Correct 13 ms 20568 KB Output is correct
8 Correct 12 ms 20572 KB Output is correct
9 Correct 12 ms 20572 KB Output is correct
10 Correct 12 ms 20568 KB Output is correct
11 Correct 21 ms 20956 KB Output is correct
12 Correct 31 ms 20824 KB Output is correct
13 Correct 54 ms 21080 KB Output is correct
14 Correct 63 ms 21336 KB Output is correct
15 Correct 16 ms 20980 KB Output is correct
16 Correct 12 ms 20568 KB Output is correct
17 Correct 13 ms 20568 KB Output is correct
18 Execution timed out 3031 ms 39188 KB Time limit exceeded
19 Halted 0 ms 0 KB -