oj.uz

Submission #732007

# Submission time Handle Problem Language Result Execution time Memory
732007 2023-04-28T08:32:10 Z Josia Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 2850 ms 701436 KB 
#include "rainbow.h"

#include <bits/stdc++.h>

using namespace std;


// #define int int64_t



int convert(int x) {
    return x*2+1;
}




struct seg {
    struct node {
        int val=0, l=-1, r=-1;
    };


    vector<node> tree;

    seg() {
        tree.assign(2, node());
    }

    int update(int v, int rl, int rr, int pos, int x) {
        int newV = tree.size();
        tree.push_back(tree[v]);

        if (rl == rr) {
            assert(pos == rl);
            tree[newV].val += x;
            return newV;
        }

        if (tree[newV].l == -1) {tree[newV].l = tree.size(); tree.push_back(node());}
        if (tree[newV].r == -1) {tree[newV].r = tree.size(); tree.push_back(node());}
        int rm = (rl + rr)/2;
        if (pos <= rm) {
            tree[newV].l = update(tree[newV].l, rl, rm, pos, x);
        }
        else {
            tree[newV].r = update(tree[newV].r, rm+1, rr, pos, x);
        }

        tree[newV].val = tree[tree[newV].l].val + tree[tree[newV].r].val;

        return newV;
    }

    int query(int v, int rl, int rr, int ql, int qr) {
        if (ql > qr) return 0;
        if (ql == rl && qr == rr) {
            return tree[v].val;
        }

        int rm = (rl + rr)/2;

        if (tree[v].l == -1 && tree[v].r == -1) return tree[v].val;
        if (tree[v].l == -1) return tree[tree[v].r].val;
        if (tree[v].r == -1) return tree[tree[v].l].val;

        // if (tree[v].l == -1) {tree[v].l = tree.size(); tree.push_back(node());}
        // if (tree[v].r == -1) {tree[v].r = tree.size(); tree.push_back(node());}
        return query(tree[v].r, rm+1, rr, max(ql, rm+1), qr) + query(tree[v].l, rl, rm, ql, min(qr, rm));
    }
};


seg squares = seg();
seg edgesFrst = seg();
seg edgesScnd = seg();
seg nodes = seg();

vector<int> queryTimeNodes;
vector<int> queryTimeSquares;
vector<int> queryTimeEdgesFrst;
vector<int> queryTimeEdgesScnd;


vector<pair<int, int>> eightConnected = {
    {1, 1},
    {-1, -1},
    {1, -1},
    {-1, 1},
    {0, 1},
    {0, -1},
    {1, 0},
    {-1, 0},
};



int R, C;

void init(signed r, signed c, signed sr, signed sc, signed M, char *S) {
    squares = seg();
    edgesFrst = seg();
    edgesScnd = seg();
    nodes = seg();


    R = r+4; C = c+4;
    R = R*2 + 1;
    C = C*2 + 1;
    map<char, pair<int, int>> dir;
    dir['N'] = {-2, 0};
    dir['S'] = {2, 0};
    dir['W'] = {0, -2};
    dir['E'] = {0, 2};


    pair<int, int> pos = {convert(sr+1), convert(sc+1)};                                                                                  // We can use 2-indexed because we added 1 margin!

    set<pair<int, int>> rivers;
    rivers.insert(pos);
    for (auto j: eightConnected) {
        rivers.insert({pos.first + j.first, pos.second + j.second});
    }

    for (int i = 0; i<M; i++) {
        pos.first += dir[S[i]].first;
        pos.second += dir[S[i]].second;

        rivers.insert(pos);

        for (auto j: eightConnected) {
            rivers.insert({pos.first + j.first, pos.second + j.second});
        }
    }


    set<pair<int, int>> eFrst, eScnd, sqrs;

    for (auto i: rivers) {
        bool scnd = rivers.count({i.first, i.second+1});
        bool frst = rivers.count({i.first+1, i.second});
        bool frstscnd = rivers.count({i.first+1, i.second+1});

        if (scnd) eScnd.insert(i);
        if (frst) eFrst.insert(i);
        if (scnd&&frst&&frstscnd) sqrs.insert(i);
    }

    queryTimeNodes.clear();
    {
        int ROW = 0;
        int root = 1;
        for (auto i: rivers) {
            while (i.first > ROW) {
                ROW++;
                queryTimeNodes.push_back(root);
            }

            root = nodes.update(root, 0, C-1, i.second, 1);
        }
        while ((int)queryTimeNodes.size() < R) queryTimeNodes.push_back(root);
    }

    queryTimeSquares.clear();
    {
        int ROW = 0;
        int root = 1;
        for (auto i: sqrs) {
            while (i.first > ROW) {
                ROW++;
                queryTimeSquares.push_back(root);
            }

            root = squares.update(root, 0, C-1, i.second, 1);
        }
        while ((int)queryTimeSquares.size() < R) queryTimeSquares.push_back(root);
    }

    queryTimeEdgesFrst.clear();
    {
        int ROW = 0;
        int root = 1;
        for (auto i: eFrst) {
            while (i.first > ROW) {
                ROW++;
                queryTimeEdgesFrst.push_back(root);
            }

            root = edgesFrst.update(root, 0, C-1, i.second, 1);
        }
        while ((int)queryTimeEdgesFrst.size() < R) queryTimeEdgesFrst.push_back(root);
    }

    queryTimeEdgesScnd.clear();
    {
        int ROW = 0;
        int root = 1;
        for (auto i: eScnd) {
            while (i.first > ROW) {
                ROW++;
                queryTimeEdgesScnd.push_back(root);
            }

            root = edgesScnd.update(root, 0, C-1, i.second, 1);
        }
        while ((int)queryTimeEdgesScnd.size() < R) queryTimeEdgesScnd.push_back(root);
    }


}

signed colour(signed ar, signed ac, signed br, signed bc) {

    ar++; ac++; br++; bc++;                                                                                        // We can use 2-indexed because we added 1 margin!

    ar = convert(ar);
    ac = convert(ac);
    br = convert(br);
    bc = convert(bc);


    int countNodes=0, countEdges=0, countSquares=0;
    bool connected=0;


    countNodes += nodes.query(queryTimeNodes[br], 0, C-1, ac, bc);
    countNodes -= nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, bc);

    countEdges += edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, ac, bc);
    countEdges -= edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, ac, bc);
    countEdges += edgesScnd.query(queryTimeEdgesScnd[br], 0, C-1, ac, bc-1);
    countEdges -= edgesScnd.query(queryTimeEdgesScnd[ar-1], 0, C-1, ac, bc-1);

    countSquares += squares.query(queryTimeSquares[br-1], 0, C-1, ac, bc-1);
    countSquares -= squares.query(queryTimeSquares[ar-1], 0, C-1, ac, bc-1);


    if (countNodes == 0) connected = 1;
    connected=connected||nodes.query(queryTimeNodes[ar], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, bc);
    connected=connected||nodes.query(queryTimeNodes[br], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[br-1], 0, C-1, ac, bc);
    connected=connected||nodes.query(queryTimeNodes[br], 0, C-1, ac, ac)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, ac);
    connected=connected||nodes.query(queryTimeNodes[br], 0, C-1, bc, bc)-nodes.query(queryTimeNodes[ar-1], 0, C-1, bc, bc);


    // cerr << "edges:" << countEdges << " " << "nodes:" << countNodes << " " << "squares:" << countSquares << " " <<  "connected:" << connected << "\n";

    if (!connected) {
        return countEdges-countNodes+2-countSquares;
    }


    int lenR = br-ar+1, lenC = bc-ac+1;

    countNodes+=2*(lenR+lenC)+4;

    // countNodes-=nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[ar-2], 0, C-1, ac, bc);
    // countNodes-=nodes.query(queryTimeNodes[br+1], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[br], 0, C-1, ac, bc);
    // countNodes-=nodes.query(queryTimeNodes[br], 0, C-1, ac-1, ac-1)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac-1, ac-1);
    // countNodes-=nodes.query(queryTimeNodes[br], 0, C-1, bc+1, bc+1)-nodes.query(queryTimeNodes[ar-1], 0, C-1, bc+1, bc+1);

    countEdges+=nodes.query(queryTimeNodes[ar], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, bc);
    countEdges+=nodes.query(queryTimeNodes[br], 0, C-1, ac, bc)-nodes.query(queryTimeNodes[br-1], 0, C-1, ac, bc);
    countEdges+=nodes.query(queryTimeNodes[br], 0, C-1, ac, ac)-nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, ac);
    countEdges+=nodes.query(queryTimeNodes[br], 0, C-1, bc, bc)-nodes.query(queryTimeNodes[ar-1], 0, C-1, bc, bc);
    
    countEdges+=2*(lenR-1+lenC-1)+8;

    // countEdges-=edgesScnd.query(queryTimeEdgesScnd[ar-1], 0, C-1, ac, bc-1)-edgesScnd.query(queryTimeEdgesScnd[ar-2], 0, C-1, ac, bc-1);
    // countEdges-=edgesScnd.query(queryTimeEdgesScnd[br+1], 0, C-1, ac, bc-1)-edgesScnd.query(queryTimeEdgesScnd[br], 0, C-1, ac, bc-1);
    // countEdges-=edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, ac-1, ac-1)-edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, ac-1, ac-1);
    // countEdges-=edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, bc+1, bc+1)-edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, bc+1, bc+1);

    countSquares+=edgesScnd.query(queryTimeEdgesScnd[ar], 0, C-1, ac, bc-1)-edgesScnd.query(queryTimeEdgesScnd[ar-1], 0, C-1, ac, bc-1);
    countSquares+=edgesScnd.query(queryTimeEdgesScnd[br], 0, C-1, ac, bc-1)-edgesScnd.query(queryTimeEdgesScnd[br-1], 0, C-1, ac, bc-1);
    countSquares+=edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, ac, ac)-edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, ac, ac);
    countSquares+=edgesFrst.query(queryTimeEdgesFrst[br-1], 0, C-1, bc, bc)-edgesFrst.query(queryTimeEdgesFrst[ar-1], 0, C-1, bc, bc);



    if (nodes.query(queryTimeNodes[ar], 0, C-1, ac, ac) - nodes.query(queryTimeNodes[ar-1], 0, C-1, ac, ac)) countSquares++;
    if (nodes.query(queryTimeNodes[br], 0, C-1, ac, ac) - nodes.query(queryTimeNodes[br-1], 0, C-1, ac, ac)) countSquares++;
    if (nodes.query(queryTimeNodes[ar], 0, C-1, bc, bc) - nodes.query(queryTimeNodes[ar-1], 0, C-1, bc, bc)) countSquares++;
    if (nodes.query(queryTimeNodes[br], 0, C-1, bc, bc) - nodes.query(queryTimeNodes[br-1], 0, C-1, bc, bc)) countSquares++;




    // cerr << "edges:" << countEdges << " " << "nodes:" << countNodes << " " << "squares:" << countSquares << " " <<  "connected:" << connected << "\n";


    return countEdges-countNodes-countSquares+1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 10 ms 3192 KB Output is correct
3 Correct 4 ms 920 KB Output is correct
4 Correct 5 ms 1156 KB Output is correct
5 Correct 12 ms 3920 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 6 ms 1368 KB Output is correct
12 Correct 8 ms 2392 KB Output is correct
13 Correct 14 ms 4484 KB Output is correct
14 Correct 18 ms 6992 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1409 ms 356392 KB Output is correct
4 Correct 2195 ms 629672 KB Output is correct
5 Correct 2247 ms 629528 KB Output is correct
6 Correct 1783 ms 545816 KB Output is correct
7 Correct 2144 ms 431140 KB Output is correct
8 Correct 159 ms 4004 KB Output is correct
9 Correct 2260 ms 630028 KB Output is correct
10 Correct 2331 ms 629000 KB Output is correct
11 Correct 2107 ms 545716 KB Output is correct
12 Correct 1665 ms 598812 KB Output is correct
13 Correct 1787 ms 629672 KB Output is correct
14 Correct 1982 ms 629256 KB Output is correct
15 Correct 1620 ms 546356 KB Output is correct
16 Correct 1688 ms 502676 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1703 ms 685304 KB Output is correct
3 Correct 1609 ms 620276 KB Output is correct
4 Correct 1565 ms 700660 KB Output is correct
5 Correct 1211 ms 494528 KB Output is correct
6 Correct 356 ms 159056 KB Output is correct
7 Correct 732 ms 342580 KB Output is correct
8 Correct 1451 ms 547360 KB Output is correct
9 Correct 1199 ms 407004 KB Output is correct
10 Correct 272 ms 115060 KB Output is correct
11 Correct 759 ms 297908 KB Output is correct
12 Correct 1706 ms 685448 KB Output is correct
13 Correct 1562 ms 620232 KB Output is correct
14 Correct 1602 ms 700612 KB Output is correct
15 Correct 1224 ms 494276 KB Output is correct
16 Correct 334 ms 127048 KB Output is correct
17 Correct 702 ms 342764 KB Output is correct
18 Correct 1513 ms 693648 KB Output is correct
19 Correct 1672 ms 701212 KB Output is correct
20 Correct 1674 ms 700780 KB Output is correct
21 Correct 1453 ms 547188 KB Output is correct
22 Correct 1201 ms 407108 KB Output is correct
23 Correct 282 ms 115056 KB Output is correct
24 Correct 725 ms 297872 KB Output is correct
25 Correct 1696 ms 685444 KB Output is correct
26 Correct 1593 ms 620120 KB Output is correct
27 Correct 1600 ms 700628 KB Output is correct
28 Correct 1237 ms 494320 KB Output is correct
29 Correct 302 ms 127156 KB Output is correct
30 Correct 699 ms 342660 KB Output is correct
31 Correct 1519 ms 693740 KB Output is correct
32 Correct 1695 ms 701168 KB Output is correct
33 Correct 1659 ms 700784 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 10 ms 3192 KB Output is correct
3 Correct 4 ms 920 KB Output is correct
4 Correct 5 ms 1156 KB Output is correct
5 Correct 12 ms 3920 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 6 ms 1368 KB Output is correct
12 Correct 8 ms 2392 KB Output is correct
13 Correct 14 ms 4484 KB Output is correct
14 Correct 18 ms 6992 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1546 ms 235408 KB Output is correct
19 Correct 460 ms 13592 KB Output is correct
20 Correct 338 ms 2424 KB Output is correct
21 Correct 330 ms 4508 KB Output is correct
22 Correct 396 ms 7228 KB Output is correct
23 Correct 453 ms 13164 KB Output is correct
24 Correct 292 ms 3744 KB Output is correct
25 Correct 355 ms 6108 KB Output is correct
26 Correct 365 ms 6872 KB Output is correct
27 Correct 805 ms 212792 KB Output is correct
28 Correct 546 ms 104732 KB Output is correct
29 Correct 760 ms 203668 KB Output is correct
30 Correct 1639 ms 404256 KB Output is correct
31 Correct 5 ms 468 KB Output is correct
32 Correct 1398 ms 211984 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 852 KB Output is correct
2 Correct 10 ms 3192 KB Output is correct
3 Correct 4 ms 920 KB Output is correct
4 Correct 5 ms 1156 KB Output is correct
5 Correct 12 ms 3920 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 6 ms 1368 KB Output is correct
12 Correct 8 ms 2392 KB Output is correct
13 Correct 14 ms 4484 KB Output is correct
14 Correct 18 ms 6992 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1546 ms 235408 KB Output is correct
19 Correct 460 ms 13592 KB Output is correct
20 Correct 338 ms 2424 KB Output is correct
21 Correct 330 ms 4508 KB Output is correct
22 Correct 396 ms 7228 KB Output is correct
23 Correct 453 ms 13164 KB Output is correct
24 Correct 292 ms 3744 KB Output is correct
25 Correct 355 ms 6108 KB Output is correct
26 Correct 365 ms 6872 KB Output is correct
27 Correct 805 ms 212792 KB Output is correct
28 Correct 546 ms 104732 KB Output is correct
29 Correct 760 ms 203668 KB Output is correct
30 Correct 1639 ms 404256 KB Output is correct
31 Correct 5 ms 468 KB Output is correct
32 Correct 1398 ms 211984 KB Output is correct
33 Correct 1703 ms 685304 KB Output is correct
34 Correct 1609 ms 620276 KB Output is correct
35 Correct 1565 ms 700660 KB Output is correct
36 Correct 1211 ms 494528 KB Output is correct
37 Correct 356 ms 159056 KB Output is correct
38 Correct 732 ms 342580 KB Output is correct
39 Correct 1451 ms 547360 KB Output is correct
40 Correct 1199 ms 407004 KB Output is correct
41 Correct 272 ms 115060 KB Output is correct
42 Correct 759 ms 297908 KB Output is correct
43 Correct 1706 ms 685448 KB Output is correct
44 Correct 1562 ms 620232 KB Output is correct
45 Correct 1602 ms 700612 KB Output is correct
46 Correct 1224 ms 494276 KB Output is correct
47 Correct 334 ms 127048 KB Output is correct
48 Correct 702 ms 342764 KB Output is correct
49 Correct 1513 ms 693648 KB Output is correct
50 Correct 1672 ms 701212 KB Output is correct
51 Correct 1674 ms 700780 KB Output is correct
52 Correct 1453 ms 547188 KB Output is correct
53 Correct 1201 ms 407108 KB Output is correct
54 Correct 282 ms 115056 KB Output is correct
55 Correct 725 ms 297872 KB Output is correct
56 Correct 1696 ms 685444 KB Output is correct
57 Correct 1593 ms 620120 KB Output is correct
58 Correct 1600 ms 700628 KB Output is correct
59 Correct 1237 ms 494320 KB Output is correct
60 Correct 302 ms 127156 KB Output is correct
61 Correct 699 ms 342660 KB Output is correct
62 Correct 1519 ms 693740 KB Output is correct
63 Correct 1695 ms 701168 KB Output is correct
64 Correct 1659 ms 700784 KB Output is correct
65 Correct 1409 ms 356392 KB Output is correct
66 Correct 2195 ms 629672 KB Output is correct
67 Correct 2247 ms 629528 KB Output is correct
68 Correct 1783 ms 545816 KB Output is correct
69 Correct 2144 ms 431140 KB Output is correct
70 Correct 159 ms 4004 KB Output is correct
71 Correct 2260 ms 630028 KB Output is correct
72 Correct 2331 ms 629000 KB Output is correct
73 Correct 2107 ms 545716 KB Output is correct
74 Correct 1665 ms 598812 KB Output is correct
75 Correct 1787 ms 629672 KB Output is correct
76 Correct 1982 ms 629256 KB Output is correct
77 Correct 1620 ms 546356 KB Output is correct
78 Correct 1688 ms 502676 KB Output is correct
79 Correct 2850 ms 547448 KB Output is correct
80 Correct 2790 ms 407216 KB Output is correct
81 Correct 760 ms 118748 KB Output is correct
82 Correct 1074 ms 301436 KB Output is correct
83 Correct 2070 ms 685468 KB Output is correct
84 Correct 1729 ms 620500 KB Output is correct
85 Correct 1843 ms 700744 KB Output is correct
86 Correct 1463 ms 494676 KB Output is correct
87 Correct 407 ms 130648 KB Output is correct
88 Correct 796 ms 342872 KB Output is correct
89 Correct 1681 ms 694016 KB Output is correct
90 Correct 2075 ms 701436 KB Output is correct
91 Correct 2083 ms 701208 KB Output is correct