oj.uz

Submission #567472

# Submission time Handle Problem Language Result Execution time Memory
567472 2022-05-23T14:46:17 Z ngpin04 Land of the Rainbow Gold (APIO17_rainbow) C++14
12 / 100
 471 ms 84088 KB 
#include <bits/stdc++.h>
#include "rainbow.h"
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

struct BIT2D {
    int n;
    vector <vector <int>> val;
    vector <vector <int>> bit;

    BIT2D(int _n = 0) {
        n = _n;
        bit.resize(n + 5);
        val.resize(n + 5);
    }

    void fakeupdate(int x, int y) {
        for (; x <= n; x += x & -x) 
            val[x].push_back(y);
    }

    void build() {
        for (int i = 1; i <= n; i++) {
            sort(ALL(val[i]));
            val[i].resize(unique(ALL(val[i])) - val[i].begin());
            bit[i].resize(val[i].size() + 1);
        }
    }

    void update(int x, int y) {
        for (; x <= n; x += x & -x) {
            int i = lower_bound(ALL(val[x]), y) - val[x].begin() + 1;
            for (; i < (int) bit[x].size(); i += i & -i)
                bit[x][i]++;
        }
    }

    int getsum(int x, int y) {
        int res = 0;
        for (; x; x -= x & -x) {
            int i = upper_bound(ALL(val[x]), y) - val[x].begin();
            for (; i; i -= i & -i)
                res += bit[x][i];
        }
        return res;
    }

    int getsum(int x, int y, int u, int v) {
        if (x > u || y > v)
            return 0;
        return (getsum(u, v) + getsum(x - 1, y - 1)) 
        -      (getsum(u, y - 1) + getsum(x - 1, v));
    }
};

int fix(char c) {
    if (c == 'W') 
        return 3;
    if (c == 'N') 
        return 2;
    if (c == 'E')
        return 1;
    return 0;
}

BIT2D row, col, cell,face;

set <pair <int, int>> s;

void init(int R, int C, int sr, int sc, int M, char *S) {
    row = col = cell = face = BIT2D(R);

    s.insert({sr, sc});
    for (int i = 0; i < M; i++) {
        int dir = fix(S[i]);
        sr += dx[dir];
        sc += dy[dir];
        s.insert({sr, sc});
        // cerr << sr << " " << sc << "\n";
    }

    for (const auto &[x, y] : s) {
        int a = false, b = false;
        if (s.find({x + 1, y}) != s.end()) {
            col.fakeupdate(x + 1, y);
            a = true;
        }
        
        if (s.find({x, y + 1}) != s.end()) {
            row.fakeupdate(x, y + 1);
            b = true;
        }

        if (a && b) {
            if (s.find({x + 1, y + 1}) != s.end()) 
                face.fakeupdate(x + 1, y + 1);
        }

        cell.fakeupdate(x, y);
    }

    cell.build();
    row.build();
    col.build();
    face.build();

    for (const auto &[x, y] : s) {
        int a = false, b = false;
        if (s.find({x + 1, y}) != s.end()) {
            col.update(x + 1, y);
            a = true;
        }
        
        if (s.find({x, y + 1}) != s.end()) {
            row.update(x, y + 1);
            b = true;
        }

        if (a && b) {
            if (s.find({x + 1, y + 1}) != s.end()) 
                face.update(x + 1, y + 1);
        }

        cell.update(x, y);
    }
}

int colour(int x, int y, int u, int v) {
    int res = 0;
    int V = cell.getsum(x, y, u, v);

    if (V == 0) 
        return 1;

    int E = col.getsum(x + 1, y, u, v) + row.getsum(x, y + 1, u, v);
    int S = 0;
    S += cell.getsum(x, y, x, v);
    S += cell.getsum(x, y, u, y);
    S += cell.getsum(u, y, u, v);
    S += cell.getsum(x, v, u, v);
    maxi(S, 1);
    E += S;

    int F = 0;
    F += face.getsum(x + 1, y + 1, u, v);
    F += row.getsum(x, y + 1, x, v);
    F += row.getsum(u, y + 1, u, v);
    F += col.getsum(x + 1, y, u, y);
    F += col.getsum(x + 1, v, u, v);
    F += s.count({x, y}) + s.count({x, v}) + s.count({u, y}) + s.count({u, v});
    // cerr << V << " " << E << " " << F << "\n";
    return 1 + (E - V - F);
}

//#include "grader.cpp"

Compilation message

rainbow.cpp: In function 'void init(int, int, int, int, int, char*)':
rainbow.cpp:105:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |     for (const auto &[x, y] : s) {
      |                      ^
rainbow.cpp:130:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  130 |     for (const auto &[x, y] : s) {
      |                      ^
rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:152:9: warning: unused variable 'res' [-Wunused-variable]
  152 |     int res = 0;
      |         ^~~

Subtask #1
0 / 11.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 282 ms 5240 KB Output is correct
4 Correct 471 ms 8012 KB Output is correct
5 Correct 468 ms 8024 KB Output is correct
6 Correct 304 ms 7248 KB Output is correct
7 Correct 416 ms 6488 KB Output is correct
8 Correct 62 ms 972 KB Output is correct
9 Correct 451 ms 8144 KB Output is correct
10 Correct 444 ms 8048 KB Output is correct
11 Correct 394 ms 7060 KB Output is correct
12 Correct 195 ms 7432 KB Output is correct
13 Correct 209 ms 8068 KB Output is correct
14 Correct 210 ms 8020 KB Output is correct
15 Correct 207 ms 7132 KB Output is correct
16 Correct 298 ms 6232 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 310 ms 80304 KB Output is correct
3 Correct 220 ms 79596 KB Output is correct
4 Correct 366 ms 84088 KB Output is correct
5 Correct 219 ms 76332 KB Output is correct
6 Correct 180 ms 68696 KB Output is correct
7 Incorrect 271 ms 72168 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

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

Subtask #5
0 / 26.0

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