Submission #581209

#	Time	Username	Problem	Language	Result	Execution time	Memory
581209		FatihSolak	UFO (IZhO14_ufo)	C++17	100 / 100	1129 ms	106568 KiB

ufo

#include <bits/stdc++.h>
#define N 200005
using namespace std;
struct SegTree{
    vector<int> t;
    int n;
    SegTree(int size){
        n = size;
        t.assign(4*n,0);
    }
    void upd(int v,int tl,int tr,int pos,int val){
        if(tl == tr){
            t[v] = val;
            return;
        }
        int tm = (tl + tr)/2;
        if(pos <= tm)
            upd(v*2,tl,tm,pos,val);
        else upd(v*2+1,tm+1,tr,pos,val);
        t[v] = max(t[v*2],t[v*2+1]);
    }
    int get1(int v,int tl,int tr,int l,int r,int val){
        if(tr < l || r < tl)
            return -1;
        if(t[v] < val)
            return -1;
        if(tl == tr)
            return tl;
        int tm = (tl + tr)/2;
        int tmp = get1(v*2,tl,tm,l,r,val); 
        if(tmp == -1)
            return get1(v*2+1,tm+1,tr,l,r,val);
        return tmp;
    }
    int get2(int v,int tl,int tr,int l,int r,int val){
        if(tr < l || r < tl)
            return -1;
        if(t[v] < val)
            return -1;
        if(tl == tr)
            return tl;
        int tm = (tl + tr)/2;
        int tmp = get2(v*2+1,tm+1,tr,l,r,val); 
        if(tmp == -1)
            return get2(v*2,tl,tm,l,r,val);
        return tmp;
    }
    void upd(int pos,int val){
        upd(1,1,n,pos,val);
    }
    int get1(int l,int r,int val){
        return get1(1,1,n,l,r,val);
    }
    int get2(int l,int r,int val){
        return get2(1,1,n,l,r,val);
    }
};
vector<vector<int>> v;
vector<SegTree> row,col;
void upd(int i,int j){
    row[i].upd(j,v[i][j]);
    col[j].upd(i,v[i][j]);
}
void solve(){
    int n,m,r,k,p;
    cin >> n >> m >> r >> k >> p;
    v = vector<vector<int>>(n+1,vector<int>(m+1,0));
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            cin >> v[i][j];
        }
    }
    for(int i = 0;i<=n;i++){
        row.push_back(SegTree(m));
    }
    for(int i = 0;i<=m;i++){
        col.push_back(SegTree(n));
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            upd(i,j);
        }
    }
    for(int i = 1;i<=k;i++){
        char type;
        int x,h;
        cin >> type >> x >> h; 
        if(type == 'W'){
            vector<int> pts;
            int last = 0;
            while(row[x].get1(last+1,m,h) != -1 && pts.size() != r){
                pts.push_back(row[x].get1(last+1,m,h));
                last = pts.back();
            }
            for(auto u:pts){
                v[x][u]--;
                upd(x,u);
            }
        }
        if(type == 'E'){
            vector<int> pts;
            int last = m+1;
            while(row[x].get2(1,last-1,h) != -1 && pts.size() != r){
                pts.push_back(row[x].get2(1,last-1,h));
                last = pts.back();
            }
            for(auto u:pts){
                v[x][u]--;
                upd(x,u);
            }
        }
        if(type == 'N'){
            vector<int> pts;
            int last = 0;
            while(col[x].get1(last+1,n,h) != -1 && pts.size() != r){
                pts.push_back(col[x].get1(last+1,n,h));
                last = pts.back();
            }
            for(auto u:pts){
                v[u][x]--;
                upd(u,x);
            }
        }
        if(type == 'S'){
            vector<int> pts;
            int last = n+1;
            while(col[x].get2(1,last-1,h) != -1 && pts.size() != r){
                pts.push_back(col[x].get2(1,last-1,h));
                last = pts.back();
            }
            for(auto u:pts){
                v[u][x]--;
                upd(u,x);
            }
        }
    }
    // for(int i = 1;i<=n;i++){
    //     for(int j = 1;j<=m;j++){
    //         cout << v[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    int ans = 0;
    for(int i = 1;i+p-1<=n;i++){
        for(int j = 1;j+p-1<=m;j++){
            int sum = 0;
            for(int c = i;c<=i+p-1;c++){
                for(int d = j;d<=j+p-1;d++){
                    sum += v[c][d];
                }
            }
            ans = max(ans,sum);
        }
    }
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    #ifdef Local
        cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds.";
    #endif
}

Compilation message (stderr)

ufo.cpp: In function 'void solve()':
ufo.cpp:91:63: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |             while(row[x].get1(last+1,m,h) != -1 && pts.size() != r){
      |                                                    ~~~~~~~~~~~^~~~
ufo.cpp:103:63: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  103 |             while(row[x].get2(1,last-1,h) != -1 && pts.size() != r){
      |                                                    ~~~~~~~~~~~^~~~
ufo.cpp:115:63: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  115 |             while(col[x].get1(last+1,n,h) != -1 && pts.size() != r){
      |                                                    ~~~~~~~~~~~^~~~
ufo.cpp:127:63: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  127 |             while(col[x].get2(1,last-1,h) != -1 && pts.size() != r){
      |                                                    ~~~~~~~~~~~^~~~

• Subtask 1: 100 / 100