oj.uz

Submission #919289

# Submission time Handle Problem Language Result Execution time Memory
919289 2024-01-31T14:30:50 Z boris_mihov Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 1722 ms 262532 KB 
#include "rainbow.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 400000 + 10;
const int INF  = 1e9;

int n, m;
struct Point
{
    int x, y;
    friend bool operator < (const Point &a, const Point &b)
    {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    }
};

struct MergeSortTree
{
    std::vector <int> tree[4*MAXN];
    std::vector <Point> points;

    void build(int l, int r, int node)
    {
        if (l == r)
        {
            tree[node].push_back(points[l].y);
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node);
        build(mid + 1, r, 2*node + 1);

        int lPtr = 0, rPtr = 0;
        tree[node].reserve(r - l + 1);
        for (int i = l ; i <= r ; ++i)
        {
            if (lPtr == tree[2*node].size())
            {
                tree[node].push_back(tree[2*node + 1][rPtr++]);
                continue;
            }

            if (rPtr == tree[2*node + 1].size())
            {
                tree[node].push_back(tree[2*node][lPtr++]);
                continue;
            }

            if (tree[2*node][lPtr] < tree[2*node + 1][rPtr])
            {
                tree[node].push_back(tree[2*node][lPtr++]);
            } else
            {
                tree[node].push_back(tree[2*node + 1][rPtr++]);
            }
        }
    }

    int countLess(int node, int value)
    {
        int l = -1, r = tree[node].size(), mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (tree[node][mid] <= value) l = mid;
            else r = mid;
        }

        return r;
    }

    int query(int l, int r, int node, int queryLPos, int queryRPos, int queryLVal, int queryRVal)
    {
        if (queryLPos <= l && r <= queryRPos)
        {
            return countLess(node, queryRVal) - countLess(node, queryLVal - 1);
        }

        int res = 0;
        int mid = (l + r) / 2;
        if (queryLPos <= mid) res += query(l, mid, 2*node, queryLPos, queryRPos, queryLVal, queryRVal);
        if (mid + 1 <= queryRPos) res += query(mid + 1, r, 2*node + 1, queryLPos, queryRPos, queryLVal, queryRVal);
        return res;
    }

    void build(const std::set <Point> &v)
    {
        points.reserve(v.size());
        for (const auto &[x, y] : v)
        {
            points.push_back({x, y});
        }

        if (points.size()) build(0, (int)points.size() - 1, 1);
    }

    int searchLeftPos(int value)
    {
        int l = -1, r = points.size(), mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (points[mid].x < value) l = mid;
            else r = mid;
        }

        return r;
    }

    int searchRightPos(int value)
    {
        int l = -1, r = points.size(), mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (points[mid].x <= value) l = mid;
            else r = mid;
        }

        return l;
    }

    llong query(int fromX, int fromY, int toX, int toY)
    {
        llong res = 1LL * (toX - fromX + 1) * (toY - fromY + 1);
        int left = searchLeftPos(fromX);
        int right = searchRightPos(toX);

        if (left <= right && fromY <= toY)
        {
            res -= query(0, (int)points.size() - 1, 1, left, right, fromY, toY);
        }

        return res;
    }
};

MergeSortTree vertexTree;
MergeSortTree edgesRightTree;
MergeSortTree edgesDownTree;
MergeSortTree sidesTree;

std::set <Point> vertexPoints;
std::set <Point> edgesRightPoints;
std::set <Point> edgesDownPoints;
std::set <Point> sidesPoints;
std::set <Point> s;

int minX = INF;
int minY = INF;
int maxX;
int maxY;


void init(int R, int C, int sr, int sc, int M, char *S) 
{
    n = R;
    m = C;

    for (int i = 0 ; i < M ; ++i)
    {
        minX = std::min(minX, sr);
        maxX = std::max(maxX, sr);
        minY = std::min(minY, sc);
        maxY = std::max(maxY, sc);
        s.insert({sr, sc});

        if (S[i] == 'N')
        {
            sr--;
        } else if (S[i] == 'E')
        {
            sc++;
        } else if (S[i] == 'S')
        {
            sr++;
        } else if (S[i] == 'W')
        {
            sc--;
        } else
        {
            assert(false);
        }
    }

    s.insert({sr, sc});
    minX = std::min(minX, sr);
    maxX = std::max(maxX, sr);
    minY = std::min(minY, sc);
    maxY = std::max(maxY, sc);

    for (const auto &[x, y] : s)
    {
        vertexPoints.insert({x, y});
        edgesRightPoints.insert({x, y});
        edgesDownPoints.insert({x, y});
        sidesPoints.insert({x, y});
        if (x > 1) edgesDownPoints.insert({x - 1, y});
        if (y > 1) edgesRightPoints.insert({x, y - 1});
        if (x > 1) sidesPoints.insert({x - 1, y});
        if (y > 1) sidesPoints.insert({x, y - 1});
        if (x > 1 && y > 1) sidesPoints.insert({x - 1, y - 1});
    }

    vertexTree.build(vertexPoints);
    edgesRightTree.build(edgesRightPoints);
    edgesDownTree.build(edgesDownPoints);
    sidesTree.build(sidesPoints);
    return;
}

int colour(int ar, int ac, int br, int bc) 
{
    llong res = 0;
    res += vertexTree.query(ar, ac, br, bc);
    res += sidesTree.query(ar, ac, br - 1, bc - 1);
    if (ar < minX && ac < minY && br > maxX && bc > maxY) // another side
    {
        res++;
    }

    res -= edgesRightTree.query(ar, ac, br, bc - 1);
    res -= edgesDownTree.query(ar, ac, br - 1, bc);
    return res;
}

Compilation message

rainbow.cpp: In member function 'void MergeSortTree::build(int, int, int)':
rainbow.cpp:44:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             if (lPtr == tree[2*node].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
rainbow.cpp:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |             if (rPtr == tree[2*node + 1].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 150608 KB Output is correct
2 Correct 47 ms 151384 KB Output is correct
3 Correct 46 ms 150660 KB Output is correct
4 Correct 44 ms 150864 KB Output is correct
5 Correct 46 ms 151376 KB Output is correct
6 Correct 41 ms 150616 KB Output is correct
7 Correct 47 ms 150668 KB Output is correct
8 Correct 40 ms 150612 KB Output is correct
9 Correct 42 ms 150608 KB Output is correct
10 Correct 47 ms 150868 KB Output is correct
11 Correct 45 ms 151000 KB Output is correct
12 Correct 45 ms 151284 KB Output is correct
13 Correct 53 ms 151912 KB Output is correct
14 Correct 51 ms 152156 KB Output is correct
15 Correct 42 ms 150608 KB Output is correct
16 Correct 43 ms 150992 KB Output is correct
17 Correct 41 ms 150616 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 150992 KB Output is correct
2 Correct 41 ms 150616 KB Output is correct
3 Correct 353 ms 205796 KB Output is correct
4 Correct 541 ms 244540 KB Output is correct
5 Correct 495 ms 242920 KB Output is correct
6 Correct 417 ms 220752 KB Output is correct
7 Correct 393 ms 216956 KB Output is correct
8 Correct 96 ms 154192 KB Output is correct
9 Correct 520 ms 243768 KB Output is correct
10 Correct 550 ms 242864 KB Output is correct
11 Correct 406 ms 220740 KB Output is correct
12 Correct 503 ms 241536 KB Output is correct
13 Correct 473 ms 244312 KB Output is correct
14 Correct 519 ms 243124 KB Output is correct
15 Correct 435 ms 221096 KB Output is correct
16 Correct 389 ms 212860 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 150608 KB Output is correct
2 Correct 480 ms 258800 KB Output is correct
3 Correct 415 ms 259000 KB Output is correct
4 Correct 423 ms 258788 KB Output is correct
5 Correct 305 ms 231268 KB Output is correct
6 Correct 100 ms 170324 KB Output is correct
7 Correct 179 ms 190548 KB Output is correct
8 Correct 314 ms 232792 KB Output is correct
9 Correct 286 ms 225456 KB Output is correct
10 Correct 109 ms 171340 KB Output is correct
11 Correct 198 ms 202576 KB Output is correct
12 Correct 483 ms 259140 KB Output is correct
13 Correct 414 ms 258848 KB Output is correct
14 Correct 426 ms 258992 KB Output is correct
15 Correct 342 ms 231324 KB Output is correct
16 Correct 96 ms 166312 KB Output is correct
17 Correct 190 ms 190624 KB Output is correct
18 Correct 439 ms 258436 KB Output is correct
19 Correct 377 ms 241040 KB Output is correct
20 Correct 388 ms 241076 KB Output is correct
21 Correct 300 ms 232904 KB Output is correct
22 Correct 296 ms 225572 KB Output is correct
23 Correct 106 ms 171088 KB Output is correct
24 Correct 221 ms 202604 KB Output is correct
25 Correct 492 ms 258956 KB Output is correct
26 Correct 431 ms 258776 KB Output is correct
27 Correct 410 ms 258876 KB Output is correct
28 Correct 328 ms 231324 KB Output is correct
29 Correct 94 ms 166428 KB Output is correct
30 Correct 195 ms 190784 KB Output is correct
31 Correct 434 ms 258384 KB Output is correct
32 Correct 385 ms 241124 KB Output is correct
33 Correct 381 ms 240984 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 150608 KB Output is correct
2 Correct 47 ms 151384 KB Output is correct
3 Correct 46 ms 150660 KB Output is correct
4 Correct 44 ms 150864 KB Output is correct
5 Correct 46 ms 151376 KB Output is correct
6 Correct 41 ms 150616 KB Output is correct
7 Correct 47 ms 150668 KB Output is correct
8 Correct 40 ms 150612 KB Output is correct
9 Correct 42 ms 150608 KB Output is correct
10 Correct 47 ms 150868 KB Output is correct
11 Correct 45 ms 151000 KB Output is correct
12 Correct 45 ms 151284 KB Output is correct
13 Correct 53 ms 151912 KB Output is correct
14 Correct 51 ms 152156 KB Output is correct
15 Correct 42 ms 150608 KB Output is correct
16 Correct 43 ms 150992 KB Output is correct
17 Correct 41 ms 150616 KB Output is correct
18 Correct 1722 ms 204316 KB Output is correct
19 Correct 275 ms 153496 KB Output is correct
20 Correct 261 ms 151632 KB Output is correct
21 Correct 291 ms 152140 KB Output is correct
22 Correct 328 ms 152656 KB Output is correct
23 Correct 269 ms 153424 KB Output is correct
24 Correct 309 ms 152164 KB Output is correct
25 Correct 315 ms 152316 KB Output is correct
26 Correct 318 ms 152656 KB Output is correct
27 Correct 667 ms 194516 KB Output is correct
28 Correct 401 ms 171912 KB Output is correct
29 Correct 517 ms 191300 KB Output is correct
30 Correct 1401 ms 259312 KB Output is correct
31 Correct 45 ms 150948 KB Output is correct
32 Correct 1249 ms 195240 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 150608 KB Output is correct
2 Correct 47 ms 151384 KB Output is correct
3 Correct 46 ms 150660 KB Output is correct
4 Correct 44 ms 150864 KB Output is correct
5 Correct 46 ms 151376 KB Output is correct
6 Correct 41 ms 150616 KB Output is correct
7 Correct 47 ms 150668 KB Output is correct
8 Correct 40 ms 150612 KB Output is correct
9 Correct 42 ms 150608 KB Output is correct
10 Correct 47 ms 150868 KB Output is correct
11 Correct 45 ms 151000 KB Output is correct
12 Correct 45 ms 151284 KB Output is correct
13 Correct 53 ms 151912 KB Output is correct
14 Correct 51 ms 152156 KB Output is correct
15 Correct 42 ms 150608 KB Output is correct
16 Correct 43 ms 150992 KB Output is correct
17 Correct 41 ms 150616 KB Output is correct
18 Correct 1722 ms 204316 KB Output is correct
19 Correct 275 ms 153496 KB Output is correct
20 Correct 261 ms 151632 KB Output is correct
21 Correct 291 ms 152140 KB Output is correct
22 Correct 328 ms 152656 KB Output is correct
23 Correct 269 ms 153424 KB Output is correct
24 Correct 309 ms 152164 KB Output is correct
25 Correct 315 ms 152316 KB Output is correct
26 Correct 318 ms 152656 KB Output is correct
27 Correct 667 ms 194516 KB Output is correct
28 Correct 401 ms 171912 KB Output is correct
29 Correct 517 ms 191300 KB Output is correct
30 Correct 1401 ms 259312 KB Output is correct
31 Correct 45 ms 150948 KB Output is correct
32 Correct 1249 ms 195240 KB Output is correct
33 Correct 480 ms 258800 KB Output is correct
34 Correct 415 ms 259000 KB Output is correct
35 Correct 423 ms 258788 KB Output is correct
36 Correct 305 ms 231268 KB Output is correct
37 Correct 100 ms 170324 KB Output is correct
38 Correct 179 ms 190548 KB Output is correct
39 Correct 314 ms 232792 KB Output is correct
40 Correct 286 ms 225456 KB Output is correct
41 Correct 109 ms 171340 KB Output is correct
42 Correct 198 ms 202576 KB Output is correct
43 Correct 483 ms 259140 KB Output is correct
44 Correct 414 ms 258848 KB Output is correct
45 Correct 426 ms 258992 KB Output is correct
46 Correct 342 ms 231324 KB Output is correct
47 Correct 96 ms 166312 KB Output is correct
48 Correct 190 ms 190624 KB Output is correct
49 Correct 439 ms 258436 KB Output is correct
50 Correct 377 ms 241040 KB Output is correct
51 Correct 388 ms 241076 KB Output is correct
52 Correct 300 ms 232904 KB Output is correct
53 Correct 296 ms 225572 KB Output is correct
54 Correct 106 ms 171088 KB Output is correct
55 Correct 221 ms 202604 KB Output is correct
56 Correct 492 ms 258956 KB Output is correct
57 Correct 431 ms 258776 KB Output is correct
58 Correct 410 ms 258876 KB Output is correct
59 Correct 328 ms 231324 KB Output is correct
60 Correct 94 ms 166428 KB Output is correct
61 Correct 195 ms 190784 KB Output is correct
62 Correct 434 ms 258384 KB Output is correct
63 Correct 385 ms 241124 KB Output is correct
64 Correct 381 ms 240984 KB Output is correct
65 Correct 353 ms 205796 KB Output is correct
66 Correct 541 ms 244540 KB Output is correct
67 Correct 495 ms 242920 KB Output is correct
68 Correct 417 ms 220752 KB Output is correct
69 Correct 393 ms 216956 KB Output is correct
70 Correct 96 ms 154192 KB Output is correct
71 Correct 520 ms 243768 KB Output is correct
72 Correct 550 ms 242864 KB Output is correct
73 Correct 406 ms 220740 KB Output is correct
74 Correct 503 ms 241536 KB Output is correct
75 Correct 473 ms 244312 KB Output is correct
76 Correct 519 ms 243124 KB Output is correct
77 Correct 435 ms 221096 KB Output is correct
78 Correct 389 ms 212860 KB Output is correct
79 Correct 762 ms 236456 KB Output is correct
80 Correct 849 ms 228952 KB Output is correct
81 Correct 510 ms 174704 KB Output is correct
82 Correct 791 ms 205964 KB Output is correct
83 Correct 567 ms 262528 KB Output is correct
84 Correct 1176 ms 262532 KB Output is correct
85 Correct 691 ms 262232 KB Output is correct
86 Correct 619 ms 234652 KB Output is correct
87 Correct 170 ms 169676 KB Output is correct
88 Correct 265 ms 194340 KB Output is correct
89 Correct 495 ms 262080 KB Output is correct
90 Correct 789 ms 244856 KB Output is correct
91 Correct 870 ms 244448 KB Output is correct