Submission #1094785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094785		RiverFlow	Land of the Rainbow Gold (APIO17_rainbow)	C++14	Compilation error	0 ms	0 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};

#define int long long

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

struct node {
    int v = 0, l = 0, r = 0;
};
const int L = (int)2e5 + 7;
const int MAX = (int)1e7 + 7;
struct segment_tree {

node t[MAX];
int ver[L + 7];

    segment_tree () {};

    int cnt = 0;
    int build(int l, int r) {
        int cur = cnt++;
        if (l == r) return cur;
        int m = (l + r) >> 1;
        t[cur].l = build(l, m);
        t[cur].r = build(m + 1, r);
        return cur;
    }
    int lver = 0;
    void build() {
        ver[0] = build(1, L);
    }
    int update(int od, int l, int r, int p) {
        int cur = cnt++;
        t[cur].v = t[od].v + 1;
        if (l == r) return cur;
        int m = (l + r) >> 1;
        if (p <= m) {
            t[cur].r = t[od].r;
            t[cur].l = update(t[od].l, l, m, p);
        } else {
            t[cur].l = t[od].l;
            t[cur].r = update(t[od].r, m + 1, r, p);
        }
        return cur;
    }
    void upd(int vx, int p) {
        if (p == -1) {
            ver[vx] = ver[vx - 1];
            lver = vx;
            return ;
        }
        ver[vx] = update(ver[lver], 1, L, p);
        lver = vx;
    }
    int get(int id, int l, int r, int u, int v) {
        if (l > v or r < u) return 0;
        if (l >= u and r <= v) return t[id].v;
        int m = (l + r) >> 1;
        return get(t[id].l, l, m, u, v) + get(t[id].r, m + 1, r, u, v);
    }
    int get(int x, int y, int u, int v) {
        return get(ver[u], 1, L, y, v) - get(ver[x - 1], 1, L, y, v);
    }

};

struct CTDL {
    const int L = (int)2e5 + 3;
    vec<vec<int>> row;
    CTDL () {
        row.resize(L + 7);
    }
    segment_tree IT;
    void add(int x, int y) {
        row[x].push_back(y);
    }
    void init() {
        IT.build();
        FOR(i, 1, L) {
            if (sz(row[i])) {
                unq(row[i]);
            }
            if (sz(row[i]) == 0) {
                IT.upd(i, -1);
            } else {
                for(int j : row[i]) {
                    IT.upd(i, j);
                }
            }
        }
    }
    int get(int x, int y, int u, int v, bool rev) {
        if (x > u or y > v) return 0;
        int j = IT.get(x, y, u, v);
        return rev ? (u - x + 1) * (v - y + 1) - j : j;
    }
};

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) {
        int x = cell.first, y = cell.second;

        mini(minX, x);
        mini(minY, y);
        maxi(maxX, x);
        maxi(maxY, y);

        orincells.add(x, y);

        FOR(a, 0, 1)
        FOR(b, 0, 1) {
            cells.add(x + a, y + b);
        }

        hori.add(x, y + 1);
        hori.add(x + 1, y + 1);
        vert.add(x + 1, y + 1);
        vert.add(x + 1, y);
    }

    orincells.init();
    cells.init();
    hori.init();
    vert.init();
}

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);

    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;

    return F - (R + 2 * (h + 2) + 2 * (w + 2) - 4 + 1);
}

#ifdef LOCAL
int32_t 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

Compilation message (stderr)

/usr/bin/ld: /tmp/cc1BEMrC.o: in function `main':
grader.cpp:(.text.startup+0xed): undefined reference to `init(int, int, int, int, int, char*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x167): undefined reference to `colour(int, int, int, int)'
collect2: error: ld returned 1 exit status