답안 #732003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
732003	2023-04-28T08:26:03 Z	Josia	무지개나라 (APIO17_rainbow)	C++17	62 / 100	3000 ms	701308 KB

rainbow

#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].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

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	852 KB	Output is correct
2	Correct	12 ms	3276 KB	Output is correct
3	Correct	5 ms	912 KB	Output is correct
4	Correct	6 ms	1264 KB	Output is correct
5	Correct	14 ms	3920 KB	Output is correct
6	Correct	1 ms	308 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	308 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	7 ms	1412 KB	Output is correct
12	Correct	10 ms	2520 KB	Output is correct
13	Correct	16 ms	4448 KB	Output is correct
14	Correct	25 ms	7112 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct

Subtask #2

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	2369 ms	368480 KB	Output is correct
4	Execution timed out	3069 ms	680612 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #3

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1701 ms	685236 KB	Output is correct
3	Correct	1594 ms	620192 KB	Output is correct
4	Correct	1688 ms	700664 KB	Output is correct
5	Correct	1247 ms	494540 KB	Output is correct
6	Correct	362 ms	159120 KB	Output is correct
7	Correct	742 ms	342428 KB	Output is correct
8	Correct	1466 ms	547204 KB	Output is correct
9	Correct	1301 ms	407056 KB	Output is correct
10	Correct	334 ms	115112 KB	Output is correct
11	Correct	864 ms	298020 KB	Output is correct
12	Correct	1793 ms	685392 KB	Output is correct
13	Correct	1605 ms	620212 KB	Output is correct
14	Correct	1621 ms	700616 KB	Output is correct
15	Correct	1282 ms	494512 KB	Output is correct
16	Correct	307 ms	127152 KB	Output is correct
17	Correct	707 ms	342684 KB	Output is correct
18	Correct	1606 ms	693820 KB	Output is correct
19	Correct	1842 ms	701308 KB	Output is correct
20	Correct	1715 ms	700912 KB	Output is correct
21	Correct	1474 ms	547232 KB	Output is correct
22	Correct	1254 ms	407200 KB	Output is correct
23	Correct	290 ms	115164 KB	Output is correct
24	Correct	753 ms	298116 KB	Output is correct
25	Correct	1759 ms	685424 KB	Output is correct
26	Correct	1642 ms	620208 KB	Output is correct
27	Correct	1629 ms	700752 KB	Output is correct
28	Correct	1258 ms	494596 KB	Output is correct
29	Correct	341 ms	127216 KB	Output is correct
30	Correct	741 ms	342680 KB	Output is correct
31	Correct	1592 ms	693956 KB	Output is correct
32	Correct	1737 ms	701236 KB	Output is correct
33	Correct	1728 ms	701004 KB	Output is correct

Subtask #4

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	852 KB	Output is correct
2	Correct	12 ms	3276 KB	Output is correct
3	Correct	5 ms	912 KB	Output is correct
4	Correct	6 ms	1264 KB	Output is correct
5	Correct	14 ms	3920 KB	Output is correct
6	Correct	1 ms	308 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	308 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	7 ms	1412 KB	Output is correct
12	Correct	10 ms	2520 KB	Output is correct
13	Correct	16 ms	4448 KB	Output is correct
14	Correct	25 ms	7112 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1727 ms	235700 KB	Output is correct
19	Correct	614 ms	16448 KB	Output is correct
20	Correct	363 ms	5236 KB	Output is correct
21	Correct	421 ms	7396 KB	Output is correct
22	Correct	444 ms	10024 KB	Output is correct
23	Correct	576 ms	16388 KB	Output is correct
24	Correct	375 ms	6900 KB	Output is correct
25	Correct	447 ms	8716 KB	Output is correct
26	Correct	444 ms	9112 KB	Output is correct
27	Correct	1305 ms	213208 KB	Output is correct
28	Correct	877 ms	104980 KB	Output is correct
29	Correct	1178 ms	203900 KB	Output is correct
30	Correct	2204 ms	404392 KB	Output is correct
31	Correct	9 ms	596 KB	Output is correct
32	Correct	1867 ms	212172 KB	Output is correct

Subtask #5

0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	852 KB	Output is correct
2	Correct	12 ms	3276 KB	Output is correct
3	Correct	5 ms	912 KB	Output is correct
4	Correct	6 ms	1264 KB	Output is correct
5	Correct	14 ms	3920 KB	Output is correct
6	Correct	1 ms	308 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	308 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	7 ms	1412 KB	Output is correct
12	Correct	10 ms	2520 KB	Output is correct
13	Correct	16 ms	4448 KB	Output is correct
14	Correct	25 ms	7112 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	1 ms	212 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	1727 ms	235700 KB	Output is correct
19	Correct	614 ms	16448 KB	Output is correct
20	Correct	363 ms	5236 KB	Output is correct
21	Correct	421 ms	7396 KB	Output is correct
22	Correct	444 ms	10024 KB	Output is correct
23	Correct	576 ms	16388 KB	Output is correct
24	Correct	375 ms	6900 KB	Output is correct
25	Correct	447 ms	8716 KB	Output is correct
26	Correct	444 ms	9112 KB	Output is correct
27	Correct	1305 ms	213208 KB	Output is correct
28	Correct	877 ms	104980 KB	Output is correct
29	Correct	1178 ms	203900 KB	Output is correct
30	Correct	2204 ms	404392 KB	Output is correct
31	Correct	9 ms	596 KB	Output is correct
32	Correct	1867 ms	212172 KB	Output is correct
33	Correct	1701 ms	685236 KB	Output is correct
34	Correct	1594 ms	620192 KB	Output is correct
35	Correct	1688 ms	700664 KB	Output is correct
36	Correct	1247 ms	494540 KB	Output is correct
37	Correct	362 ms	159120 KB	Output is correct
38	Correct	742 ms	342428 KB	Output is correct
39	Correct	1466 ms	547204 KB	Output is correct
40	Correct	1301 ms	407056 KB	Output is correct
41	Correct	334 ms	115112 KB	Output is correct
42	Correct	864 ms	298020 KB	Output is correct
43	Correct	1793 ms	685392 KB	Output is correct
44	Correct	1605 ms	620212 KB	Output is correct
45	Correct	1621 ms	700616 KB	Output is correct
46	Correct	1282 ms	494512 KB	Output is correct
47	Correct	307 ms	127152 KB	Output is correct
48	Correct	707 ms	342684 KB	Output is correct
49	Correct	1606 ms	693820 KB	Output is correct
50	Correct	1842 ms	701308 KB	Output is correct
51	Correct	1715 ms	700912 KB	Output is correct
52	Correct	1474 ms	547232 KB	Output is correct
53	Correct	1254 ms	407200 KB	Output is correct
54	Correct	290 ms	115164 KB	Output is correct
55	Correct	753 ms	298116 KB	Output is correct
56	Correct	1759 ms	685424 KB	Output is correct
57	Correct	1642 ms	620208 KB	Output is correct
58	Correct	1629 ms	700752 KB	Output is correct
59	Correct	1258 ms	494596 KB	Output is correct
60	Correct	341 ms	127216 KB	Output is correct
61	Correct	741 ms	342680 KB	Output is correct
62	Correct	1592 ms	693956 KB	Output is correct
63	Correct	1737 ms	701236 KB	Output is correct
64	Correct	1728 ms	701004 KB	Output is correct
65	Correct	2369 ms	368480 KB	Output is correct
66	Execution timed out	3069 ms	680612 KB	Time limit exceeded
67	Halted	0 ms	0 KB	-