Submission #1118985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118985		PagodePaiva	Toy (CEOI24_toy)	C++17	73 / 100	1600 ms	430828 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int N = 1510;
const int LOGN = 11;
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++;
        //cout << l << ' ' << r << ' ';
        int t = (r-l+1);
        if(l == 1 and r == 1){
            //cout << bin[l][lg[t]] << ' ' << bin[r-(1<<(lg[t]))+1][lg[t]] << '\n';
        }
        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(){
    ios::sync_with_stdio(false); cin.tie(0);
    int k , l;
    cin >> m >> n >> k >> l;
    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(vv);
        /*for(auto x : vv){
            cout << x;
        }
        cout << '\n';*/
    }
    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(vv);
      //for(auto x : v){
        //    cout << x;
        //}
        //cout << '\n';
    }
   /* for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cout << linhatrue[i].query(j, j);
        }
        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 = max(0, y-l+1), 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;
            }
        }
        ll = y, rr = min(n-1, y+l-1);
        int down = n-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;
            }
        }
        ll = max(0, x-k+1), 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;
            }
        }
        ll = x, rr = min(m-1, x+k-1);
        int right = x;
        while(ll <= rr){
            int mid = (ll+rr)/2;
            if(linhatrue[y].query(x, mid) == 0){
                right = mid;
                ll = mid+1;
            }
            else{
                rr = mid-1;
            }
        }
        //cout << right << ' ';
        //cout << x << ' ' << k << ' ' << right << '\n';
        // (x-1, y)
        //cout << up << ' ' << down << ' ' << left << ' ' << right << '\n';
        //cout << "(" << x << "," << y << ") vai para:";
        if(y > 0){
            if(linha[y-1].query(left, right-k+1) == 0){
               // cout << "(" << x << "," << y-1 << ") ";
                q.push({x, y-1});
            }
        }
        // (x+1, y)
        if(y<n-1){
            if(linha[y+1].query(left, right-k+1) == 0){
               // cout << "(" << x << "," << y+1 << ") ";
                q.push({x, y+1});
            }
        }
        //
        if(x > 0){
            if(coluna[x-1].query(up, down-l+1) == 0){
              //  cout << "(" << x-1 << "," << y << ") ";
                q.push({x-1, y});
            }
        }
        //
        if(x < m-1){
            //if(x == 1 and y == 0) cout << 'a' << coluna[y+1].query(0, 0) << ' ' << coluna[y+1].query(1, 1) << '\n';
            if(coluna[x+1].query(up, down-l+1) == 0){
               // cout << "(" << x+1 << "," << y << ") ";
                q.push({x+1, y});
            }
        }
        //cout << '\n';
    }
    /*for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cout << mark[i][j] << ' ';
        }
        cout << '\n';
    }*/
    if(mark[edy][edx] == 1){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }
    return 0;
}

Compilation message (stderr)

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:233:21: warning: 'edy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  233 |     if(mark[edy][edx] == 1){
      |        ~~~~~~~~~~~~~^
Main.cpp:233:21: warning: 'edx' may be used uninitialized in this function [-Wmaybe-uninitialized]

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