Submission #1140656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140656		Rafiullah	Toy (CEOI24_toy)	C++20	100 / 100	136 ms	90920 KiB

Main

#include<bits/stdc++.h>
// #include <ext/pb_ds/tree_policy.hpp>
// #include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
#define int long long
const int N = 1501;
const int mod = 1e9 + 7;
const int mod1 = 998244353;
const int LG = 20;
// #define s(i) (*s.find_by_order(i)) // Warning : Read this line.

int power(int b,int e){
    if(e<=0)return 1;
    int o = power(b,e>>1);
    o *= o, o %= mod1;
    if(e % 2)o *= b, o %= mod1;
    return o;
}
int up[N][N], le[N][N], ri[N][N],d[N][N], is[N][N];
void solve(){
    int m,n,hor,ver;cin >> m >> n >> hor >> ver;
    int h[2],v[2];cin >> h[0] >> h[1] >> v[0] >> v[1];
    vector<string> grid(n + 1);
    for(int i = 1 ; i <= n ; i ++)
        cin >> grid[i], grid[i] = 'X' + grid[i];
    h[0] ++, h[1] ++, v[0] ++, v[1] ++;
    swap(h[0],h[1]);swap(v[0],v[1]);
    int R = h[0], C = v[1];
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= m ; j ++){
            up[i][j] = le[i][j] = 1;
            if(grid[i][j] == 'X')
                up[i][j] = le[i][j] = 0;
            else
                up[i][j] += up[i-1][j], le[i][j] += le[i][j-1];
        }
    for(int i = n ; i >= 1 ; i --)
        for(int j = m ; j >= 1 ; j --){
            ri[i][j] = d[i][j] = 1;
            if(grid[i][j] == 'X')ri[i][j] = d[i][j] = 0;
            else ri[i][j] += ri[i][j+1], d[i][j] += d[i+1][j];
        }
    queue<pair<int,int>> q;
    q.push({R,C});is[R][C] = 1;
    while(q.size()){
        int r = q.front().first;int c = q.front().second; q.pop();
        if(r+1<=n and !is[r+1][c] and ri[r+1][c]+le[r+1][c]-1>=hor and d[r+1][c]+up[r+1][c]-1>=ver){
            int right = min(ri[r+1][c],ri[r][c]);
            int left = min(le[r+1][c],le[r][c]);
            if(left+right-1>=hor){
                is[r+1][c] = 1, q.push({r+1,c});
            }
        }
        if(r-1>=1 and !is[r-1][c] and ri[r-1][c]+le[r-1][c]-1>=hor and d[r-1][c]+up[r-1][c]-1>=ver){
            int right = min(ri[r-1][c],ri[r][c]);
            int left= min(le[r-1][c],le[r][c]);
            if(left+right-1>=hor)
                is[r-1][c]=1,q.push({r-1,c});
        }
        if(c+1<=m and !is[r][c+1] and ri[r][c+1]+le[r][c+1]-1>=hor and d[r][c+1]+up[r][c+1]-1>=ver){
            int upp = min(up[r][c+1],up[r][c]);
            int dow = min(d[r][c+1],d[r][c]);
            if(upp+dow-1>=ver)
                is[r][c+1]=1,q.push({r,c+1});
        }
        if(c-1>=1 and !is[r][c-1] and ri[r][c-1]+le[r][c-1]-1>=hor and d[r][c-1]+up[r][c-1]-1>=ver){
            int upp = min(up[r][c-1],up[r][c]);
            int dow = min(d[r][c-1],d[r][c]);
            if(upp+dow-1>=ver)
                is[r][c-1]=1,q.push({r,c-1});
        }
    }
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= m ; j ++)
            if(grid[i][j] == '*' and is[i][j]){
                cout <<"YES" << '\n';return;
            }
    cout << "NO" << '\n';
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t --){
        solve();
    }
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27