Submission #587352

#	Time	Username	Problem	Language	Result	Execution time	Memory
587352		Do_you_copy	Land of the Rainbow Gold (APIO17_rainbow)	C++14	100 / 100	1242 ms	136600 KiB

rainbow

#include <bits/stdc++.h>
#include <rainbow.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;

using ll = long long;
using pii = pair <int, int>;

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

const ll Mod = 1000000007;
const int maxR = 2e5 + 1;
int n;

struct bit2d{
    vector <vector <int>> node, bit;
    int sizee;
    void set_size(int n){
        node.resize(n + 1);
        bit.resize(n + 1);
        sizee = n;
    }
    void fakeUpdate(int x, int y){
        for (; x <= sizee; x += x & -x){
            node[x].pb(y);
        }
    }
    void build(){
        for (int x = 1; x <= sizee; ++x){
            sort(node[x].begin(), node[x].end());
            node[x].resize(unique(node[x].begin(), node[x].end()) - node[x].begin());
            bit[x].resize(node[x].size() + 1);
        }
    }
    void update(int x, int yy){
        for (int i = x; i <= sizee; i += i & -i){
            int y = upper_bound(node[i].begin(), node[i].end(), yy) - node[i].begin();
            for (int j = y; j < bit[i].size(); j += j & -j){
                ++bit[i][j];
            }
        }
    }
    int get(int x, int yy){
        int sum = 0;
        for (int i = x; i > 0; i -= i & -i){
            int y = upper_bound(node[i].begin(), node[i].end(), yy) - node[i].begin();
            for (int j = y; j > 0; j -= j & -j){
                sum += bit[i][j];
            }
        }
        return sum;
    }
    int get(int x1, int y1, int x2, int y2){
        if (x1 > x2 || y1 > y2) return 0;
        return get(x2, y2) + get(x1 - 1, y1 - 1) - get(x2, y1 - 1) - get(x1 - 1, y2);
    }
};

bit2d vertices, horizontal_edges, vertical_edges, rivers; //unique
set <pii> r, c, b, v;

void add(int i, int j){
    b.insert({i, j});
    r.insert({i, j});
    r.insert({i + 1, j});
    c.insert({i, j});
    c.insert({i, j + 1});
    v.insert({i, j});
    v.insert({i + 1, j});
    v.insert({i, j + 1});
    v.insert({i + 1, j + 1});
}

int minr, maxr, minc, maxc;
void init(int R, int C, int sr, int sc, int M, char *s) {
    rivers.set_size(R + 1);
    horizontal_edges.set_size(R + 1);
    vertical_edges.set_size(R + 1);
    vertices.set_size(R + 1);
    minr = maxr = sr; minc = maxc = sc;
    add(sr, sc);
    for (int i = 0; i < M; ++i){
        if (s[i] == 'W') --sc;
        if (s[i] == 'E') ++sc;
        if (s[i] == 'N') --sr;
        if (s[i] == 'S') ++sr;
        add(sr, sc);
        minr = min(minr, sr);
        minc = min(minc, sc);
        maxr = max(maxr, sr);
        maxc = max(maxc, sc);
    }
    //get space to allocate and update
    for (const auto &i: b){
        rivers.fakeUpdate(i.fi, i.se);
    }
    for (const auto &i: r){
        horizontal_edges.fakeUpdate(i.fi, i.se);
    }
    for (const auto &i: c){
        vertical_edges.fakeUpdate(i.fi, i.se);
    }
    for (const auto &i: v){
        vertices.fakeUpdate(i.fi, i.se);
    }
    rivers.build();
    horizontal_edges.build();
    vertical_edges.build();
    vertices.build();
    for (const auto &i: b){
        rivers.update(i.fi, i.se);
    }
    for (const auto &i: r){
        horizontal_edges.update(i.fi, i.se);
    }
    for (const auto &i: c){
        vertical_edges.update(i.fi, i.se);
    }
    for (const auto &i: v){
        vertices.update(i.fi, i.se);
    }
}

//statement??? "colour" is supposed to be plural
int colour(int ar, int ac, int br, int bc){
    int C = 1 + (ar < minr && br > maxr && ac < minc && bc > maxc);
    int E = horizontal_edges.get(ar + 1, ac, br, bc) + vertical_edges.get(ar, ac + 1, br, bc);
    int V = vertices.get(ar + 1, ac + 1, br, bc);
    int R = rivers.get(ar, ac, br, bc);
    return E + C - R - V;
}

Compilation message (stderr)

rainbow.cpp: In member function 'void bit2d::update(int, int)':
rainbow.cpp:48:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             for (int j = y; j < bit[i].size(); j += j & -j){
      |                             ~~^~~~~~~~~~~~~~~

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