Submission #1094585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094585		RiverFlow	Land of the Rainbow Gold (APIO17_rainbow)	C++14	0 / 100	35 ms	4556 KiB

rainbow

#include "rainbow.h"
#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;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

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

bool smallG = 0;

int n, m;

vector<ii> rivers;

namespace SUB1 {
const int N = (int)1e3 + 7;

int a[N][N], b[N][N];

int get(int a[N][N], int x, int y, int u, int v) {
    if (x > u or y > v) return 0;
    return a[u][v] - a[u][y - 1] - a[x - 1][v] + a[x - 1][y - 1];
}

int s1[N][N], s2[N][N], s3[N][N];

void build() {
    FOR(i, 1, n)
    FOR(j, 1, m) a[i][j] = 0;
    for(auto x : rivers)
        a[x.fi][x.se] = 1;
//    FOR(i, 1, n) FOR(j, 1, m) cerr << a[i][j] << " \n"[j == m];
    FOR(i, 1, n) FOR(j, 1, m) {
        b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + (a[i][j]);
    }
    FOR(i, 1, n) {
        FOR(j, 2, m) s1[i][j]
            = s1[i - 1][j] + s1[i][j - 1] - s1[i - 1][j - 1] + (a[i][j] and a[i][j - 1]);
    }
    FOR(i, 2, n) {
        FOR(j, 1, m) s2[i][j]
            = s2[i - 1][j] + s2[i][j - 1] - s2[i - 1][j - 1] + (a[i][j] and a[i - 1][j]);
    }
    FOR(i, 2, n) FOR(j, 2, m) {
        s3[i][j] = s3[i - 1][j] + s3[i][j - 1] - s3[i - 1][j - 1]
            + (a[i][j] and a[i][j-1] and a[i-1][j] and a[i-1][j-1]);
    }
}
int get(int x, int y, int u, int v) {
    int w = y - v + 1, h = u - x + 1;
    int V = get(b, x, y, u, v) + 2 * (w + h) + 4;
    int E = get(s1, x, y + 1, u, v) + get(s2, x + 1, y, u, v);
//    cerr << "E: " << E << nl;
    E += get(b, x, y, x, v) + get(b, u, y, u, v);
    E += get(b, x, y, u, y) + get(b, x, v, u, v);
    E += 2 * (w + 1) + 2 * (h + 1);
    int F = 2 + E - V;
//    cerr << E << ' ' << V << ' ' << F << nl;
    F -= get(s2, x + 1, y, u, y);
    F -= get(s2, x + 1, v, u, v);
    F -= get(s1, x, y + 1, x, v);
    F -= get(s1, u, y + 1, u, v);
    F -= (a[x][y]) + (a[x][v]) + (a[u][y]) + (a[u][v]);
    F -= get(s3, x + 1, y + 1, u, v);
    return F - 1;
}
};

void init(int R, int C, int sx, int sy, int M, char *S) {
    n = R, m = C;
    rivers.push_back(_mp(sx, sy));
    for(int i = 0; i < M; ++i) {
        FOR(d, 0, 3) if (ch[d] == S[i]) {
            sx += dx[d],
            sy += dy[d];
        }
        rivers.push_back(_mp(sx, sy));
    }
    unq(rivers);
    if (n <= 1000 and m <= 1000) {
        smallG = 1;
    }
    if (smallG) {
        SUB1::build();
    }
}

int colour(int ar, int ac, int br, int bc) {
    if (smallG) {
        return SUB1::get(ar, ac, br, bc);
    }
    return 0;
}


/*     Let the river flows naturally     */

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