Submission #549673

#	Time	Username	Problem	Language	Result	Execution time	Memory
549673		Zanite	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	915 ms	332776 KiB

rainbow

#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 / 11
• Subtask 2: 12 / 12
• Subtask 3: 24 / 24
• Subtask 4: 27 / 27
• Subtask 5: 26 / 26