oj.uz

Submission #1093703

# Submission time Handle Problem Language Result Execution time Memory
1093703 2024-09-27T10:07:59 Z RiverFlow Land of the Rainbow Gold (APIO17_rainbow) C++14
0 / 100
 34 ms 4428 KB 
#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 int 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];
int fl[N][N], fu[N][N];
int get(int a[N][N], int x, int y, int u, int v) {
    if (x > u or y > v) return 0;
//    FOR(i, 1, n) FOR(j, 1, m) cerr << a[i][j] << " \n"[j == m];
    return a[u][v] - a[u][y - 1] - a[x - 1][v] + a[x - 1][y - 1];
}
void build() {
    FOR(i, 1, n)
    FOR(j, 1, m) a[i][j] = 1;
    for(auto [x, y] : rivers)
        a[x][y] = 0;
    FOR(i, 1, n) {
        FOR(j, 2, m) {
            fl[i][j] = fl[i][j - 1] + fl[i - 1][j] - fl[i - 1][j - 1];
            fl[i][j] += (a[i][j] and a[i][j - 1]);
        }
    }
    FOR(i, 2, n) {
        FOR(j, 1, m) {
            fu[i][j] = fu[i][j - 1] + fu[i - 1][j] - fu[i - 1][j - 1];
            fu[i][j] += (a[i][j] and a[i - 1][j]);
        }
    }
    FOR(i, 1, n) FOR(j, 1, m) a[i][j] += a[i-1][j] + a[i][j-1] - a[i-1][j-1];
}
int get(int x, int y, int u, int v) {
    int V = get(a, x, y, u, v);
    int E = get(fl, x, y + 1, u, v) + get(fu, x + 1, y, u, v);
    if (E == 1LL * (u - x + 1) * (v - y + 1))
        return 1;
    return V - E;
}
};

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     */

Compilation message

rainbow.cpp: In function 'void SUB1::build()':
rainbow.cpp:54:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     for(auto [x, y] : rivers)
      |              ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 34 ms 4428 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 4 ms 1748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -