Submission #1094778

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094778		RiverFlow	Land of the Rainbow Gold (APIO17_rainbow)	C++14	11 / 100	3087 ms	35024 KiB

rainbow

#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

const char ch[4] = {'N', 'E', 'W', 'S'};
const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, 1, -1, 0};

void mini(int &a, int b) {
    if (a > b) a = b;
}
void maxi(int &a, int b) {
    if (a < b) a = b;
}

vector<pair<int, int>> points;

struct CTDL {
    const int L = (int)1e3 + 7;
    vec<vec<int>> cnt;
    CTDL () {
        cnt.resize(L);
        for(int i = 0; i < L; ++i)
            cnt[i].resize(L);
    }
    void add(int x, int y) {
        assert(x > 0 and y > 0);
        cnt[x][y] = 1;
    }
    int get(int x, int y, int u, int v, bool rev) {
        if (x > u or y > v) return 0;
        int j = (u - x + 1) * (v - y + 1);
        int res = 0;
        FOR(i, x, u) FOR(j, y, v)
            res += cnt[i][j];
        return rev ? (j - res) : res;
    }
};

const int N = (int)2e5 + 7;

int n, m;
CTDL orincells, cells, hori, vert; // hori = hang, vert = cot

int minX = INT_MAX, maxX = 0, minY = INT_MAX, maxY = 0;

void init(int R, int C, int sr, int sc, int M, char *S) {
    n = R, m = C;
    vector<pair<int, int>> rivers;
    rivers.push_back(_mp(sr, sc));
    for(int i = 0; i < M; ++i) {
        for(int j = 0; j < 4; ++j) if (ch[j] == S[i]) {
            sr += dx[j], sc += dy[j];
        }
        rivers.push_back(_mp(sr, sc));
    }
    unq(rivers);
    for(auto cell : rivers) {
        orincells.add(cell.fi, cell.se);
        mini(minX, cell.first);
        mini(minY, cell.second);
        maxi(maxX, cell.first);
        maxi(maxY, cell.second);

        FOR(a, 0, 1)
        FOR(b, 0, 1) {
            cells.add(cell.first + a, cell.second + b);
        }
        hori.add(cell.fi, cell.se + 1);
        hori.add(cell.fi + 1, cell.se + 1);
        vert.add(cell.fi + 1, cell.se + 1);
        vert.add(cell.fi + 1, cell.se);
    }
}

int colour(int x, int y, int u, int v) {
    int R = orincells.get(x, y, u, v, 0);
    if (R == 0) return 1;
    if (R == (u - x + 1) * (v - y + 1)) return 0;

    int h = u - x + 1, w = v - y + 1;

    int V = (h + 3) * (w + 3) - cells.get(x + 1, y + 1, u, v, 1);
    int E = 4 * (w + 2) + 4 * (h + 2) + 2 * (w - 1) + 2 * (h - 1);
//    cerr << "\n\n";
//    cerr << "border: " << E << nl;
//    cerr << "h, w: " << h << ' ' << w << nl;
    E += hori.get(x + 1, y + 1, u, v + 1, 0) + vert.get(x + 1, y + 1, u + 1, v, 0);

    int C = (minX > x and maxX < u and minY > y and maxY < v) ? 2 : 1;

    int F = 1 + C - V + E;
//    cerr << V << ' ' << E << ' ' << C << ' ' << F << ' ' << R << nl;
    return F - (R + 2 * (h + 2) + 2 * (w + 2) - 4 + 1);
}

#ifdef LOCAL
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    freopen("main.inp", "r", stdin);
    freopen("main.out", "w", stdout);
    int r, c, m, q, x, y;
    cin >> r >> c >> m >> q >> x >> y;
//    string s; cin >> s;
    char s[m];
    for(int i = 0; i < m; ++i) cin >> s[i];
    init(r, c, x, y, m, s);
    while (q--) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        cout << colour(x, y, u, v) << nl;
    }
}
#endif

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