oj.uz

Submission #1118602

# Submission time Handle Problem Language Result Execution time Memory
1118602 2024-11-25T18:20:09 Z PagodePaiva Toy (CEOI24_toy) C++17
0 / 100
 97 ms 31304 KB 
#include<bits/stdc++.h>

using namespace std;

const int N = 1510;
const int LOGN = 12;
int n, m;

struct SparseTable{
    int bin[N][LOGN];
    int lg[N];
    void build(vector <int> v){
        lg[1] = 0;
        for(int i = 2;i <= v.size();i++){
            lg[i] = lg[i/2]+1;
        }
        for(int i = 1;i <= v.size();i++){
            bin[i][0] = v[i-1];
        }
        for(int bit = 1;bit < LOGN;bit++){
            for(int i = 1;i <= v.size();i++){
                bin[i][bit] = min(bin[i][bit-1], bin[min((int)v.size(),i+(1<<(bit-1)))][bit-1]);
            }
        }
    }
    int query(int l, int r){
        l++;
        r++;
        int t = (r-l+1);
        return min(bin[l][lg[t]], bin[r-(1<<(lg[t]))+1][lg[t]]);
    }
} linha[N], coluna[N];

struct SparseTable2{
    int bin[N][LOGN];
    int lg[N];
    void build(vector <int> v){
        lg[1] = 0;
        for(int i = 2;i <= v.size();i++){
            lg[i] = lg[i/2]+1;
        }
        for(int i = 1;i <= v.size();i++){
            bin[i][0] = v[i-1];
        }
        for(int bit = 1;bit < LOGN;bit++){
            for(int i = 1;i <= v.size();i++){
                bin[i][bit] = max(bin[i][bit-1], bin[min((int)v.size(),i+(1<<(bit-1)))][bit-1]);
            }
        }
    }
    int query(int l, int r){
        l++;
        r++;
        int t = (r-l+1);
        return max(bin[l][lg[t]], bin[r-(1<<(lg[t]))+1][lg[t]]);
    }
} linhatrue[N], colunatrue[N];

int mat[N][N];
int mark[N][N];

int main(){
    int k , l;
    cin >> m >> n >> l >> k;
    int stx, sty, bunda;
    int edx, edy;
    cin >> bunda >> sty >> stx >> bunda;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            char c;
            cin >> c;
            if(c == '.') mat[i][j] = 0;
            if(c == 'X') mat[i][j] = 1;
            if(c == '*'){
                edx = i;
                edy = j;
                mat[i][j] = 0;
            }
        }
    }
    for(int i = 0;i < n;i++){
        int sum = 0;
        vector <int> vv;
        for(int j = 0;j < k;j++){
            sum += mat[i][j];
            vv.push_back(mat[i][j]);
        }
        vector <int> v;
        v.push_back(sum);
        for(int j = k;j < m;j++){
            sum -= mat[i][j-k];
            sum += mat[i][j];
            v.push_back(sum);
            vv.push_back(mat[i][j]);
        }
        linha[i].build(v);
        linhatrue[i].build(v);
    }
    for(int j = 0;j < m;j++){
        int sum = 0;
        vector <int> vv;
        for(int i = 0;i < l;i++){
            sum += mat[i][j];
            vv.push_back(mat[i][j]);
        }
        vector <int> v;
        v.push_back(sum);
        for(int i = l;i < n;i++){
            sum -= mat[i-l][j];
            sum += mat[i][j];
            v.push_back(sum);
            vv.push_back(mat[i][j]);
        }
        coluna[j].build(v);
        colunatrue[j].build(v);
    }
    /*for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cout << linhatrue[j].query(i, i);
        }
        cout << '\n';
    }*/
    queue <pair <int, int>> q;
    q.push({stx, sty});
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop();
        if(mark[x][y] == 1) continue;
        //cout << x << ' ' << y << '\n';
        mark[x][y] = 1;
        int ll = 0, rr = y;
        int up = 0;
        while(ll <= rr){
            int mid = (ll+rr)/2;
            if(colunatrue[x].query(mid, y) == 0){
                up = mid;
                rr = mid-1;
            }
            else{
                ll = mid+1;
            }
        }
        if(up <= y-l) up = y-l+1;

        ll = y, rr = m-1;
        int down = m-1;
        while(ll <= rr){
            int mid = (ll+rr)/2;
            if(colunatrue[x].query(y, mid) == 0){
                down = mid;
                ll = mid+1;
            }
            else{
                rr = mid-1;
            }
        }
        if(down >= y+l) down = y+l-1;
        ll = 0, rr = x;
        int left = 0;
        while(ll <= rr){
            int mid = (ll+rr)/2;
            if(linhatrue[y].query(mid, x) == 0){
                left = mid;
                rr = mid-1;
            }
            else{
                ll = mid+1;
            }
        }
        if(left <= x-k) left = x+k-1;
        ll = x, rr = n-1;
        int right = x;
        while(ll <= rr){
            int mid = (ll+rr)/2;
            if(linhatrue[x].query(x, mid) == 0){
                right = mid;
                ll = mid+1;
            }
            else{
                rr = mid-1;
            }
        }
        if(right <= x+k) right = x+k-1;
        // (x-1, y)
        //cout << up << ' ' << down << ' ' << left << ' ' << right << '\n';
        if(x > 0){
            if(coluna[x-1].query(up, down-l+1) == 0){
                q.push({x-1, y});
            }
        }
        // (x+1, y)
        if(x<n-1){
            if(coluna[x+1].query(up, down-l+1) == 0){
                q.push({x+1, y});
            }
        }
        //
        if(y > 0){
            if(linha[y-1].query(left, right-k+1) == 0){
                q.push({x, y-1});
            }
        }
        //
        if(y < m-1){
            if(linha[y+1].query(left, right-k+1) == 0){
                q.push({x, y+1});
            }
        }
    }
    /*for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cout << mark[i][j] << ' ';
        }
        cout << '\n';
    }*/
    if(mark[edx][edy] == 1){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }
    return 0;
}

Compilation message

Main.cpp: In member function 'void SparseTable::build(std::vector<int>)':
Main.cpp:14:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |         for(int i = 2;i <= v.size();i++){
      |                       ~~^~~~~~~~~~~
Main.cpp:17:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for(int i = 1;i <= v.size();i++){
      |                       ~~^~~~~~~~~~~
Main.cpp:21:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |             for(int i = 1;i <= v.size();i++){
      |                           ~~^~~~~~~~~~~
Main.cpp: In member function 'void SparseTable2::build(std::vector<int>)':
Main.cpp:39:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i = 2;i <= v.size();i++){
      |                       ~~^~~~~~~~~~~
Main.cpp:42:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i = 1;i <= v.size();i++){
      |                       ~~^~~~~~~~~~~
Main.cpp:46:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |             for(int i = 1;i <= v.size();i++){
      |                           ~~^~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:216:21: warning: 'edy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  216 |     if(mark[edx][edy] == 1){
      |        ~~~~~~~~~~~~~^
Main.cpp:216:21: warning: 'edx' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 1528 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Incorrect 3 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 1528 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Incorrect 3 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 5 ms 3664 KB Output is correct
4 Correct 75 ms 31256 KB Output is correct
5 Correct 92 ms 31304 KB Output is correct
6 Correct 17 ms 6992 KB Output is correct
7 Correct 97 ms 31036 KB Output is correct
8 Correct 96 ms 31060 KB Output is correct
9 Correct 11 ms 13404 KB Output is correct
10 Correct 66 ms 31172 KB Output is correct
11 Correct 34 ms 29532 KB Output is correct
12 Correct 14 ms 13404 KB Output is correct
13 Correct 27 ms 29836 KB Output is correct
14 Correct 31 ms 29532 KB Output is correct
15 Incorrect 71 ms 29780 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 1528 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Incorrect 3 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 1528 KB Output is correct
4 Correct 4 ms 2764 KB Output is correct
5 Incorrect 3 ms 2396 KB Output isn't correct
6 Halted 0 ms 0 KB -