Submission #1134623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134623		byunjaewoo	Land of the Rainbow Gold (APIO17_rainbow)	C++20	35 / 100	3103 ms	377784 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

const int S=(1<<18);
class PST {
public:
    PST() {root.push_back(new Node());}
    void init(vector<pair<int, int>> v) {
        for(auto i:v) {
            x.push_back(i.first);
            root.push_back(update(root.back(), 1, S, i.second));
        }
    }
    int query(int sx, int sy, int ex, int ey) {
        auto p=lower_bound(x.begin(), x.end(), sx), q=upper_bound(x.begin(), x.end(), ex);
        Node *a=NULL, *b=NULL;
        if(p!=x.begin()) a=root[p-x.begin()];
        if(q!=x.begin()) b=root[q-x.begin()];
        return max(0, query(b, 1, S, sy, ey)-query(a, 1, S, sy, ey));
    }
private:
    struct Node {
        int x; Node *l, *r;
    };
    vector<int> x;
    vector<Node*> root;
    Node* update(Node *prev, int s, int e, int k) {
        Node *node=new Node();
        if(prev) node->x=prev->x, node->l=prev->l, node->r=prev->r;
        node->x++;
        if(s==e) return node;
        int m=(s+e)/2;
        if(k<=m) {
            if(prev) node->l=update(prev->l, s, m, k);
            else node->l=update(NULL, s, m, k);
        }
        else {
            if(prev) node->r=update(prev->r, m+1, e, k);
            else node->r=update(NULL, m+1, e, k);
        }
        return node;
    }
    int query(Node *node, int s, int e, int l, int r) {
        if(!node || s>e || l>r) return 0;
        if(l<=s && e<=r) return (node==NULL)?0:(node->x);
        int m=(s+e)/2;
        return query(node->l, s, m, l, r)+query(node->r, m+1, e, l, r);
    }
}V, E1, E2, F;

void init(int R, int C, int sr, int sc, int M, char *S) {
    vector<pair<int, int>> v, e1, e2, f;
    v.push_back({sr, sc}), v.push_back({sr+1, sc}), v.push_back({sr, sc+1}), v.push_back({sr+1, sc+1});
    e1.push_back({sr, sc}), e1.push_back({sr, sc+1}), e2.push_back({sr, sc}), e2.push_back({sr+1, sc}), f.push_back({sr, sc});
    for(int i=0; i<M; i++) {
        if(S[i]=='E') sc++;
        else if(S[i]=='W') sc--;
        else if(S[i]=='N') sr--;
        else sr++;
        v.push_back({sr, sc}), v.push_back({sr+1, sc}), v.push_back({sr, sc+1}), v.push_back({sr+1, sc+1});
        e1.push_back({sr, sc}), e1.push_back({sr, sc+1}), e2.push_back({sr, sc}), e2.push_back({sr+1, sc}), f.push_back({sr, sc});
    }
    sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end());
    sort(e1.begin(), e1.end()), e1.erase(unique(e1.begin(), e1.end()), e1.end());
    sort(e2.begin(), e2.end()), e2.erase(unique(e2.begin(), e2.end()), e2.end());
    sort(f.begin(), f.end()), f.erase(unique(f.begin(), f.end()), f.end());
    V.init(v), E1.init(e1), E2.init(e2), F.init(f);
}

int colour(int ar, int ac, int br, int bc) {
    int v=V.query(ar+1, ac+1, br, bc)+2*(br-ar+1+bc-ac+1);
    int e=E1.query(ar, ac+1, br, bc)+E2.query(ar+1, ac, br, bc)+2*(br-ar+1+bc-ac+1);
    int f=F.query(ar, ac, br, bc);
    int c=1+((F.query(ar, ac, ar, bc)+F.query(ar, ac, br, ac)+F.query(br, ac, br, bc)+F.query(ar, bc, br, bc)==0) && (F.query(ar, ac, br, bc)>0));
    return -v+e-f+c;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 12
• Subtask 3: 24 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26