Submission #734716

#	Time	Username	Problem	Language	Result	Execution time	Memory
734716		Marceantasy	Land of the Rainbow Gold (APIO17_rainbow)	C++17	100 / 100	907 ms	85052 KiB

rainbow

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

#define ll long long

struct BIT2D{
    set<pair<int, int>> S;
    vector<vector<int>> bit;
    int R, C;
    void init(int _R, int _C){
        R = _R; 
        C = _C;
        bit.resize(R+1);
    }
    void upd(int x, int y){ // updatea la posicion {x, y} con += 1
        if(x < 1 || x > R || y < 1 || y > C || S.find({x, y}) != S.end()) return;
        S.insert({x, y});
        for(int i = x; i<=R; i+= i&(-i)){
            bit[i].emplace_back(y);
        }
    }
    void build(){
        for(int i = 1; i<=R; ++i){
            sort(bit[i].begin(), bit[i].end());
        }
    }
    int qry(int x, int y){
        int res = 0;
        for(int i = x; i>0; i -= i&(-i)){
            res += upper_bound(bit[i].begin(), bit[i].end(), y) - bit[i].begin();
        }
        return res;
    }

    ll qry(int lx, int ly, int rx, int ry){
        return 1LL * (rx-lx+1) * (ry-ly+1) - qry(rx, ry) + qry(rx, ly-1) + qry(lx-1, ry) - qry(lx-1, ly-1);
    }
}V, rowE, colE, F;

int max_X, min_X, max_Y, min_Y;

void add(int cx, int cy){
    max_X = max(max_X, cx);
    min_X = min(min_X, cx);
    max_Y = max(max_Y, cy);
    min_Y = min(min_Y, cy);
    V.upd(cx, cy);
    rowE.upd(cx-1, cy);
    rowE.upd(cx, cy);
    colE.upd(cx, cy-1);
    colE.upd(cx, cy);
    F.upd(cx-1, cy-1);
    F.upd(cx-1, cy);
    F.upd(cx, cy-1);
    F.upd(cx, cy);

}

void init(int R, int C, int cx, int cy, int M, char *S){
    V.init(R, C);
    rowE.init(R, C);
    colE.init(R, C);
    F.init(R, C);
    max_X = min_X = cx;
    max_Y = min_Y = cy;
    add(cx, cy);
    for(int i = 0; i<M; ++i){
        if(S[i] == 'N'){
            cx--;
        }else if(S[i] == 'E'){
            cy++;
        }else if(S[i] == 'W'){
            cy--;
        }else{
            cx++;
        }
        add(cx, cy);
    }
    V.build();
    rowE.build();
    colE.build();
    F.build();
}

int colour(int lx, int ly, int rx, int ry){
    return V.qry(lx, ly, rx, ry) - rowE.qry(lx, ly, rx-1, ry) - colE.qry(lx, ly, rx, ry-1) + F.qry(lx, ly, rx-1, ry-1) +  (lx < min_X && max_X < rx && ly < min_Y && max_Y < ry);
}
/*
int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
 
    
    init(6, 4, 3, 3, 9, "NWESSWEWS");
    cout << colours(2, 3, 2, 3) << "\n";
    cout << colours(3, 2, 4, 4) << "\n";
    cout << colours(5, 3, 6, 4) << "\n";
    cout << colours(1, 2, 5, 3) << "\n";

    
}

*/

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