oj.uz

Submission #549673

# Submission time Handle Problem Language Result Execution time Memory
549673 2022-04-16T09:45:11 Z Zanite Land of the Rainbow Gold (APIO17_rainbow) C++17
100 / 100
 915 ms 332776 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

const int _R = 2e5 + 5;

struct PSTRangeSum {
    struct Node {
        int idx, val;
        Node* left;
        Node* right;
        
        Node(int _idx) : idx(_idx), val(0), left(nullptr), right(nullptr) {}
    };

    int dim[2];
    vector<set<int>> temp;
    vector<Node*> roots;

    PSTRangeSum(int _dim1, int _dim2) {
        dim[0] = _dim1;
        dim[1] = _dim2;

        temp.assign(_dim1 + 1, set<int>());
    }

    void add(int x, int y) {
        temp[x].insert(y);
    }

    void build() {
        roots.push_back(new Node(0));

        for (int i = 1; i <= dim[0]; i++) {
            roots.push_back(new Node(i));
            roots[i]->val = roots[i-1]->val;
            roots[i]->left = roots[i-1]->left;
            roots[i]->right = roots[i-1]->right;

            //cout << i << ": ";
            for (auto j : temp[i]) {
                //cout << j << " ";
                update(roots[i], roots[i-1], 1, dim[1], i, j);
            }
            //cout << '\n';
        }
    }

    void update(Node* cur, Node* prv, int l, int r, int x, int idx) {
        if (l == r) {
            cur->val++;
            return;
        }

        int m = (l + r) >> 1;
        if (idx <= m) {
            if (!cur->left || cur->left->idx != x) {
                cur->left = new Node(x);
                if (prv && prv->left) {
                    cur->left->val = prv->left->val;
                }
            }

            if (!cur->right || cur->right->idx != x) {
                if (prv) {
                    cur->right = prv->right;
                }
            }

            if (prv) {
                update(cur->left, prv->left, l, m, x, idx);
            } else {
                update(cur->left, nullptr, l, m, x, idx);
            }
        } else {
            if (!cur->right || cur->right->idx != x) {
                cur->right = new Node(x);
                if (prv && prv->right) {
                    cur->right->val = prv->right->val;
                }
            }

            if (!cur->left || cur->left->idx != x) {
                if (prv) {
                    cur->left = prv->left;
                }
            }

            if (prv) {
                update(cur->right, prv->right, m+1, r, x, idx);
            } else {
                update(cur->right, nullptr, m+1, r, x, idx);
            }
        }

        cur->val = 0;
        if (cur->left) {cur->val += cur->left->val;}
        if (cur->right) {cur->val += cur->right->val;}
    }

	void traverse(Node* cur, int depth) {
		if (!cur) return;

		string s(depth, ' ');
		cout << s;
		printf("%d %d\n", cur->idx, cur->val);

		traverse(cur->left, depth+1);
		traverse(cur->right, depth+1);
	}

    int query(Node* cur, int l, int r, int ql, int qr) {
        if (!cur) return 0;
        if (l > qr || ql > r) return 0;
        if (ql <= l && r <= qr) return cur->val;

        int m = (l + r) >> 1;
        return query(cur->left, l, m, ql, qr) + query(cur->right, m+1, r, ql, qr);
    }

	int rangequery(int x1, int x2, int y1, int y2) {
		return query(roots[x2], 1, dim[1], y1, y2) - query(roots[x1-1], 1, dim[1], y1, y2);
	}
} vertices(_R, _R), edgesH(_R, _R), edgesV(_R, _R), rivers(_R, _R);

int minR, maxR, minC, maxC;

void insert(int x, int y) {
    vertices.add(x, y);
    vertices.add(x+1, y);
    vertices.add(x, y+1);
    vertices.add(x+1, y+1);

    edgesH.add(x, y);
    edgesH.add(x+1, y);

    edgesV.add(x, y);
    edgesV.add(x, y+1);

    rivers.add(x, y);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    insert(sr, sc);
    minR = maxR = sr;
    minC = maxC = 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 {sc++;}
        insert(sr, sc);

        minR = min(minR, sr);
        maxR = max(maxR, sr);

        minC = min(minC, sc);
        maxC = max(maxC, sc);
    }
    vertices.build();
    edgesH.build();
    edgesV.build();
    rivers.build();

    //cout << "Vertices\n";
    //for (int i = 0; i <= maxR+1; i++) {vertices.traverse(vertices.roots[i], 0);}
}

int colour(int ar, int ac, int br, int bc) {
    int E = edgesH.rangequery(ar+1, br, ac, bc) + edgesV.rangequery(ar, br, ac+1, bc);
    int V = vertices.rangequery(ar+1, br, ac+1, bc);
    int R = rivers.rangequery(ar, br, ac, bc);
    int C = 1 + (int)(ar < minR && br > maxR && ac < minC && bc > maxC);

    //printf("%d %d %d %d\n", E, V, R, C);

    return E - V - R + C;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 69316 KB Output is correct
2 Correct 59 ms 69900 KB Output is correct
3 Correct 65 ms 69444 KB Output is correct
4 Correct 53 ms 69468 KB Output is correct
5 Correct 56 ms 70000 KB Output is correct
6 Correct 58 ms 69184 KB Output is correct
7 Correct 54 ms 69120 KB Output is correct
8 Correct 62 ms 69116 KB Output is correct
9 Correct 62 ms 69180 KB Output is correct
10 Correct 53 ms 69172 KB Output is correct
11 Correct 54 ms 69436 KB Output is correct
12 Correct 53 ms 69740 KB Output is correct
13 Correct 59 ms 70156 KB Output is correct
14 Correct 59 ms 70352 KB Output is correct
15 Correct 52 ms 69172 KB Output is correct
16 Correct 49 ms 69120 KB Output is correct
17 Correct 50 ms 69204 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 69120 KB Output is correct
2 Correct 50 ms 69204 KB Output is correct
3 Correct 419 ms 111984 KB Output is correct
4 Correct 605 ms 139828 KB Output is correct
5 Correct 634 ms 140960 KB Output is correct
6 Correct 543 ms 124196 KB Output is correct
7 Correct 650 ms 123904 KB Output is correct
8 Correct 122 ms 72764 KB Output is correct
9 Correct 644 ms 139800 KB Output is correct
10 Correct 648 ms 141024 KB Output is correct
11 Correct 561 ms 124136 KB Output is correct
12 Correct 422 ms 133996 KB Output is correct
13 Correct 434 ms 139708 KB Output is correct
14 Correct 441 ms 140980 KB Output is correct
15 Correct 432 ms 124120 KB Output is correct
16 Correct 471 ms 119236 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 69172 KB Output is correct
2 Correct 430 ms 135252 KB Output is correct
3 Correct 379 ms 329364 KB Output is correct
4 Correct 383 ms 233392 KB Output is correct
5 Correct 292 ms 215716 KB Output is correct
6 Correct 136 ms 83220 KB Output is correct
7 Correct 188 ms 95676 KB Output is correct
8 Correct 329 ms 131584 KB Output is correct
9 Correct 308 ms 128220 KB Output is correct
10 Correct 130 ms 83752 KB Output is correct
11 Correct 236 ms 125304 KB Output is correct
12 Correct 378 ms 135124 KB Output is correct
13 Correct 437 ms 329212 KB Output is correct
14 Correct 334 ms 233356 KB Output is correct
15 Correct 317 ms 215744 KB Output is correct
16 Correct 116 ms 80316 KB Output is correct
17 Correct 184 ms 96296 KB Output is correct
18 Correct 295 ms 138960 KB Output is correct
19 Correct 405 ms 232136 KB Output is correct
20 Correct 376 ms 232008 KB Output is correct
21 Correct 341 ms 131468 KB Output is correct
22 Correct 354 ms 128188 KB Output is correct
23 Correct 134 ms 83784 KB Output is correct
24 Correct 236 ms 125272 KB Output is correct
25 Correct 399 ms 135084 KB Output is correct
26 Correct 398 ms 329336 KB Output is correct
27 Correct 355 ms 233412 KB Output is correct
28 Correct 298 ms 215712 KB Output is correct
29 Correct 127 ms 80356 KB Output is correct
30 Correct 178 ms 96248 KB Output is correct
31 Correct 300 ms 139004 KB Output is correct
32 Correct 376 ms 232188 KB Output is correct
33 Correct 398 ms 232180 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 69316 KB Output is correct
2 Correct 59 ms 69900 KB Output is correct
3 Correct 65 ms 69444 KB Output is correct
4 Correct 53 ms 69468 KB Output is correct
5 Correct 56 ms 70000 KB Output is correct
6 Correct 58 ms 69184 KB Output is correct
7 Correct 54 ms 69120 KB Output is correct
8 Correct 62 ms 69116 KB Output is correct
9 Correct 62 ms 69180 KB Output is correct
10 Correct 53 ms 69172 KB Output is correct
11 Correct 54 ms 69436 KB Output is correct
12 Correct 53 ms 69740 KB Output is correct
13 Correct 59 ms 70156 KB Output is correct
14 Correct 59 ms 70352 KB Output is correct
15 Correct 52 ms 69172 KB Output is correct
16 Correct 49 ms 69120 KB Output is correct
17 Correct 50 ms 69204 KB Output is correct
18 Correct 680 ms 129768 KB Output is correct
19 Correct 253 ms 74380 KB Output is correct
20 Correct 226 ms 73084 KB Output is correct
21 Correct 222 ms 73788 KB Output is correct
22 Correct 240 ms 74324 KB Output is correct
23 Correct 273 ms 74268 KB Output is correct
24 Correct 205 ms 73264 KB Output is correct
25 Correct 278 ms 73916 KB Output is correct
26 Correct 227 ms 74452 KB Output is correct
27 Correct 342 ms 103532 KB Output is correct
28 Correct 256 ms 87248 KB Output is correct
29 Correct 296 ms 98864 KB Output is correct
30 Correct 553 ms 142416 KB Output is correct
31 Correct 67 ms 69244 KB Output is correct
32 Correct 466 ms 100852 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 69316 KB Output is correct
2 Correct 59 ms 69900 KB Output is correct
3 Correct 65 ms 69444 KB Output is correct
4 Correct 53 ms 69468 KB Output is correct
5 Correct 56 ms 70000 KB Output is correct
6 Correct 58 ms 69184 KB Output is correct
7 Correct 54 ms 69120 KB Output is correct
8 Correct 62 ms 69116 KB Output is correct
9 Correct 62 ms 69180 KB Output is correct
10 Correct 53 ms 69172 KB Output is correct
11 Correct 54 ms 69436 KB Output is correct
12 Correct 53 ms 69740 KB Output is correct
13 Correct 59 ms 70156 KB Output is correct
14 Correct 59 ms 70352 KB Output is correct
15 Correct 52 ms 69172 KB Output is correct
16 Correct 49 ms 69120 KB Output is correct
17 Correct 50 ms 69204 KB Output is correct
18 Correct 680 ms 129768 KB Output is correct
19 Correct 253 ms 74380 KB Output is correct
20 Correct 226 ms 73084 KB Output is correct
21 Correct 222 ms 73788 KB Output is correct
22 Correct 240 ms 74324 KB Output is correct
23 Correct 273 ms 74268 KB Output is correct
24 Correct 205 ms 73264 KB Output is correct
25 Correct 278 ms 73916 KB Output is correct
26 Correct 227 ms 74452 KB Output is correct
27 Correct 342 ms 103532 KB Output is correct
28 Correct 256 ms 87248 KB Output is correct
29 Correct 296 ms 98864 KB Output is correct
30 Correct 553 ms 142416 KB Output is correct
31 Correct 67 ms 69244 KB Output is correct
32 Correct 466 ms 100852 KB Output is correct
33 Correct 430 ms 135252 KB Output is correct
34 Correct 379 ms 329364 KB Output is correct
35 Correct 383 ms 233392 KB Output is correct
36 Correct 292 ms 215716 KB Output is correct
37 Correct 136 ms 83220 KB Output is correct
38 Correct 188 ms 95676 KB Output is correct
39 Correct 329 ms 131584 KB Output is correct
40 Correct 308 ms 128220 KB Output is correct
41 Correct 130 ms 83752 KB Output is correct
42 Correct 236 ms 125304 KB Output is correct
43 Correct 378 ms 135124 KB Output is correct
44 Correct 437 ms 329212 KB Output is correct
45 Correct 334 ms 233356 KB Output is correct
46 Correct 317 ms 215744 KB Output is correct
47 Correct 116 ms 80316 KB Output is correct
48 Correct 184 ms 96296 KB Output is correct
49 Correct 295 ms 138960 KB Output is correct
50 Correct 405 ms 232136 KB Output is correct
51 Correct 376 ms 232008 KB Output is correct
52 Correct 341 ms 131468 KB Output is correct
53 Correct 354 ms 128188 KB Output is correct
54 Correct 134 ms 83784 KB Output is correct
55 Correct 236 ms 125272 KB Output is correct
56 Correct 399 ms 135084 KB Output is correct
57 Correct 398 ms 329336 KB Output is correct
58 Correct 355 ms 233412 KB Output is correct
59 Correct 298 ms 215712 KB Output is correct
60 Correct 127 ms 80356 KB Output is correct
61 Correct 178 ms 96248 KB Output is correct
62 Correct 300 ms 139004 KB Output is correct
63 Correct 376 ms 232188 KB Output is correct
64 Correct 398 ms 232180 KB Output is correct
65 Correct 419 ms 111984 KB Output is correct
66 Correct 605 ms 139828 KB Output is correct
67 Correct 634 ms 140960 KB Output is correct
68 Correct 543 ms 124196 KB Output is correct
69 Correct 650 ms 123904 KB Output is correct
70 Correct 122 ms 72764 KB Output is correct
71 Correct 644 ms 139800 KB Output is correct
72 Correct 648 ms 141024 KB Output is correct
73 Correct 561 ms 124136 KB Output is correct
74 Correct 422 ms 133996 KB Output is correct
75 Correct 434 ms 139708 KB Output is correct
76 Correct 441 ms 140980 KB Output is correct
77 Correct 432 ms 124120 KB Output is correct
78 Correct 471 ms 119236 KB Output is correct
79 Correct 915 ms 135016 KB Output is correct
80 Correct 913 ms 131652 KB Output is correct
81 Correct 353 ms 87228 KB Output is correct
82 Correct 400 ms 128700 KB Output is correct
83 Correct 654 ms 138624 KB Output is correct
84 Correct 568 ms 332776 KB Output is correct
85 Correct 527 ms 236848 KB Output is correct
86 Correct 460 ms 219412 KB Output is correct
87 Correct 222 ms 83780 KB Output is correct
88 Correct 302 ms 99768 KB Output is correct
89 Correct 434 ms 142428 KB Output is correct
90 Correct 627 ms 235556 KB Output is correct
91 Correct 628 ms 235428 KB Output is correct