oj.uz

Submission #262914

# Submission time Handle Problem Language Result Execution time Memory
262914 2020-08-13T11:00:12 Z SorahISA Land of the Rainbow Gold (APIO17_rainbow) C++11
23 / 100
 131 ms 2552 KB 
#include "rainbow.h"
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define double long double
using pii = pair<int, int>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = std::priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
#define fastIO() ios_base::sync_with_stdio(false), cin.tie(0)

const int maxn1 = 50 + 5;
const int maxn2 = 1 << 18;

int _R, _C;
int app[maxn1][maxn1], vis[maxn1][maxn1];
int arr[5][maxn2];
vector<pii> vec[5];

void dfs(int nr, int nc, int ar, int ac, int br, int bc) {
    if (nr < ar or br < nr) return;
    if (nc < ac or bc < nc) return;
    if (vis[nr][nc] or app[nr][nc]) return;
    vis[nr][nc] = 1;
    dfs(nr + 1, nc, ar, ac, br, bc);
    dfs(nr - 1, nc, ar, ac, br, bc);
    dfs(nr, nc + 1, ar, ac, br, bc);
    dfs(nr, nc - 1, ar, ac, br, bc);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    _R = R, _C = C;
    
    if (_R == 2) {
        arr[sr][sc] = 1;
        for (int i = 0; i < M; ++i) {
            if (S[i] == 'N') --sr;
            if (S[i] == 'S') ++sr;
            if (S[i] == 'W') --sc;
            if (S[i] == 'E') ++sc;
            arr[sr][sc] = 1;
        }
        
        int lst1 = 0, lst2 = 0;
        for (int i = 0; i <= C; ++i) {
            if ( arr[1][i] and !arr[1][i + 1]) lst1 = i + 1;
            if (!arr[1][i] and  arr[1][i + 1]) vec[1].eb(lst1, i);
            if ( arr[2][i] and !arr[2][i + 1]) lst2 = i + 1;
            if (!arr[2][i] and  arr[2][i + 1]) vec[2].eb(lst2, i);
        }
        vec[1].eb(lst1, C + 1);
        vec[2].eb(lst2, C + 1);
    }
    else {
        app[sr][sc] = 1;
        for (int i = 0; i < M; ++i) {
            if (S[i] == 'N') --sr;
            if (S[i] == 'S') ++sr;
            if (S[i] == 'W') --sc;
            if (S[i] == 'E') ++sc;
            app[sr][sc] = 1;
        }
    }
}

int colour(int ar, int ac, int br, int bc) {
    if (_R == 2) {
        int cnt1L, cnt1R, cnt2L, cnt2R;
        
        if (lower_bound(ALL(vec[1]), pii{ac, 0}) != vec[1].begin() and
            (*prev(lower_bound(ALL(vec[1]), pii{ac, 0}))).Y >= ac) {
            cnt1L = lower_bound(ALL(vec[1]), pii{ac, 0}) - vec[1].begin() - 1;
        }
        else {
            cnt1L = lower_bound(ALL(vec[1]), pii{ac, 0}) - vec[1].begin();
        }
        cnt1R = upper_bound(ALL(vec[1]), pii{bc, maxn2}) - vec[1].begin() - 1;
        
        if (lower_bound(ALL(vec[2]), pii{ac, 0}) != vec[2].begin() and
            (*prev(lower_bound(ALL(vec[2]), pii{ac, 0}))).Y >= ac) {
            cnt2L = lower_bound(ALL(vec[2]), pii{ac, 0}) - vec[2].begin() - 1;
        }
        else {
            cnt2L = lower_bound(ALL(vec[2]), pii{ac, 0}) - vec[2].begin();
        }
        cnt2R = upper_bound(ALL(vec[2]), pii{bc, maxn2}) - vec[2].begin() - 1;
        
        // cout << cnt1L << " " << cnt1R << " " << cnt2L << " " << cnt2R << " ";
        
        int ans = (ar == 1 ? cnt1R - cnt1L + 1 : 0LL) + (br == 2 ? cnt2R - cnt2L + 1 : 0LL);
        if (ar == 1 and br == 2) {
            ans -= cnt1L == 0 and cnt2L == 0;
            ans -= cnt1R == vec[1].size() - 1 and cnt2R == vec[2].size() - 1;
        }
        
        return ans;
    }
    else {
        int cnt = 0;
    
        memset(vis, 0x00, sizeof(vis));
        for (int i = ar; i <= br; ++i) {
            for (int j = ac; j <= bc; ++j) {
                if (!vis[i][j] and !app[i][j]) {
                    ++cnt, dfs(i, j, ar, ac, br, bc);
                }
            }
        }
        
        return cnt;
    }
}

Compilation message

rainbow.cpp: In function 'int colour(int, int, int, int)':
rainbow.cpp:101:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             ans -= cnt1R == vec[1].size() - 1 and cnt2R == vec[2].size() - 1;
      |                    ~~~~~~^~~~~~~~~~~~~~~~~~~~
rainbow.cpp:101:57: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |             ans -= cnt1R == vec[1].size() - 1 and cnt2R == vec[2].size() - 1;
      |                                                   ~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 23 ms 768 KB Output is correct
4 Correct 25 ms 512 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 17 ms 512 KB Output is correct
12 Correct 14 ms 512 KB Output is correct
13 Correct 10 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 73 ms 1912 KB Output is correct
4 Correct 107 ms 2424 KB Output is correct
5 Correct 131 ms 2552 KB Output is correct
6 Correct 103 ms 2168 KB Output is correct
7 Correct 106 ms 2420 KB Output is correct
8 Correct 72 ms 1656 KB Output is correct
9 Correct 109 ms 2552 KB Output is correct
10 Correct 120 ms 2552 KB Output is correct
11 Correct 125 ms 2168 KB Output is correct
12 Correct 68 ms 2040 KB Output is correct
13 Correct 85 ms 2424 KB Output is correct
14 Correct 81 ms 2552 KB Output is correct
15 Correct 91 ms 2216 KB Output is correct
16 Correct 78 ms 1912 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Runtime error 2 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 23 ms 768 KB Output is correct
4 Correct 25 ms 512 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 17 ms 512 KB Output is correct
12 Correct 14 ms 512 KB Output is correct
13 Correct 10 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Runtime error 2 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 23 ms 768 KB Output is correct
4 Correct 25 ms 512 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 17 ms 512 KB Output is correct
12 Correct 14 ms 512 KB Output is correct
13 Correct 10 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Runtime error 2 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -