oj.uz

Submission #262875

# Submission time Handle Problem Language Result Execution time Memory
262875 2020-08-13T10:22:50 Z SorahISA Land of the Rainbow Gold (APIO17_rainbow) C++11
12 / 100
 127 ms 4860 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 maxn = 1 << 18;

int arr[5][maxn];
vector<pii> vec[5];

void init(int R, int C, int sr, int sc, int M, char *S) {
    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);
}

int colour(int ar, int ac, int br, int bc) {
    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, maxn}) - 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, maxn}) - 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;
}

Compilation message

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

Subtask #1
0 / 11.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 83 ms 1672 KB Output is correct
4 Correct 110 ms 4856 KB Output is correct
5 Correct 120 ms 4856 KB Output is correct
6 Correct 127 ms 4596 KB Output is correct
7 Correct 103 ms 4724 KB Output is correct
8 Correct 72 ms 3960 KB Output is correct
9 Correct 107 ms 4728 KB Output is correct
10 Correct 117 ms 4860 KB Output is correct
11 Correct 120 ms 4656 KB Output is correct
12 Correct 68 ms 4344 KB Output is correct
13 Correct 76 ms 4728 KB Output is correct
14 Correct 83 ms 4856 KB Output is correct
15 Correct 82 ms 4548 KB Output is correct
16 Correct 72 ms 4216 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 Runtime error 1 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

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