Submission #680675

#	Time	Username	Problem	Language	Result	Execution time	Memory
680675		79brue	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	1300 ms	468740 KiB

rainbow

#include "rainbow.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct PST{
    struct Node{
        Node *lc, *rc;
        int sum;

        Node(int l, int r){
            sum = 0;
            if(l==r) lc = rc = nullptr;
            else{
                int m = (l+r)/2;
                lc = new Node(l, m);
                rc = new Node(m+1, r);
            }
        }

        Node(Node *lc, Node *rc, int sum): lc(lc), rc(rc), sum(sum){}

        ~Node(){
            if(lc) delete lc;
            if(rc) delete rc;
        }

        int query(int l, int r, int s, int e){
            if(r<s || e<l) return 0;
            if(s<=l && r<=e) return sum;
            int m = (l+r)>>1;
            return lc->query(l, m, s, e) + rc->query(m+1, r, s, e);
        }

        Node* update(int l, int r, int x, int v){
            if(l==r){
                Node* tmp = new Node(lc, rc, sum + v);
                return tmp;
            }
            int m = (l+r)>>1;
            Node* tmp = new Node(lc, rc, sum+v);
            if(x<=m) tmp->lc = lc->update(l, m, x, v);
            else     tmp->rc = rc->update(m+1, r, x, v);
            return tmp;
        }
    } *root = nullptr;
    int n;

    PST(){}
    Node *yHistory[200002];
    int yMaximum;

    void init(int _n){
        n = _n;
        root = new Node(0, n);
        for(int i=0; i<=200001; i++) yHistory[i] = nullptr;
        yMaximum = 0;
    }

    void update(int x, int y){
        while(yMaximum < y) yHistory[yMaximum++] = root;
        root = root->update(0, n, x, 1);
    }

    void finish(){
        while(yMaximum < 200001) yHistory[yMaximum++] = root;
    }

    int query(int xl, int xr, int yl, int yr){
//        printf("(%d - %d) = %d\n", yHistory[yr]->query(0, n, xl, xr), (yl == 0 ? 0 : yHistory[yl-1]->query(0, n, xl, xr)));
        return yHistory[yr]->query(0, n, xl, xr) - (yl == 0 ? 0 : yHistory[yl-1]->query(0, n, xl, xr));
    }
} vpst, ehpst, evpst, fpst;

struct Point{
    int x, y;
    Point(){}
    Point(int x, int y): x(x), y(y){}
    bool operator<(const Point &r)const{
        if(y!=r.y) return y<r.y;
        return x<r.x;
    }
    bool operator==(const Point &r)const{
        return x==r.x && y==r.y;
    }
};

int N, M;
int xMin = 1e9, xMax = -1e9, yMin = 1e9, yMax = -1e9;
vector<Point> vvec, ehvec, evvec, fvec;

void check(int X, int Y){
    xMin = min(xMin, X), yMin = min(yMin, Y);
    xMax = max(xMax, X), yMax = max(yMax, Y);

    vvec.push_back(Point(X, Y));

    if(Y!=1) ehvec.push_back(Point(X, Y-1));
    if(Y!=M) ehvec.push_back(Point(X, Y));

    if(X!=1) evvec.push_back(Point(X-1, Y));
    if(X!=N) evvec.push_back(Point(X, Y));

    if(Y!=1 && X!=1) fvec.push_back(Point(X-1, Y-1));
    if(Y!=M && X!=1) fvec.push_back(Point(X-1, Y));
    if(Y!=1 && X!=N) fvec.push_back(Point(X, Y-1));
    if(Y!=M && X!=N) fvec.push_back(Point(X, Y));
}

void update(PST &pst, vector<Point> &vec){
    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    pst.init(N);
    for(Point p: vec){
        pst.update(p.x, p.y);
    }
    pst.finish();
}

void init(int R, int C, int sr, int sc, int K, char *S){
    N = R, M = C;
    vpst.init(N);
    ehpst.init(N);
    evpst.init(N);
    fpst.init(N);

    int x = sr, y = sc;
    check(x, y);
    for(int i=0; i<K; i++){
        if(S[i] == 'N') x--;
        else if(S[i] == 'E') y++;
        else if(S[i] == 'W') y--;
        else x++;
        check(x, y);
    }

    update(vpst, vvec);
    update(ehpst, ehvec);
    update(evpst, evvec);
    update(fpst, fvec);
}

int colour(int x1, int y1, int x2, int y2){
    ll V = ll(x2-x1+1) * ll(y2-y1+1) - vpst.query(x1, x2, y1, y2);
    ll EH = ll(x2-x1+1) * ll(y2-y1) - ehpst.query(x1, x2, y1, y2-1);
    ll EV = ll(x2-x1) * ll(y2-y1+1) - evpst.query(x1, x2-1, y1, y2);
    ll F = ll(x2-x1) * ll(y2-y1) - fpst.query(x1, x2-1, y1, y2-1);

    if(x1 < xMin && xMax < x2 && y1 < yMin && yMax < y2) F++;

//    printf("%lld %lld %lld %lld\n", V, EH, EV, F);

    return V-(EH+EV)+F;
}

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