답안 #581209

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
581209 2022-06-22T11:35:17 Z FatihSolak UFO (IZhO14_ufo) C++17
100 / 100
1129 ms 106568 KB
#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

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){
      |                                                    ~~~~~~~~~~~^~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 220 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 20 ms 724 KB Output is correct
5 Correct 106 ms 3036 KB Output is correct
6 Correct 220 ms 20948 KB Output is correct
7 Correct 291 ms 50176 KB Output is correct
8 Correct 226 ms 46580 KB Output is correct
9 Correct 531 ms 42432 KB Output is correct
10 Correct 646 ms 45680 KB Output is correct
11 Correct 449 ms 45228 KB Output is correct
12 Correct 663 ms 45688 KB Output is correct
13 Correct 771 ms 50880 KB Output is correct
14 Correct 555 ms 45480 KB Output is correct
15 Correct 707 ms 47224 KB Output is correct
16 Correct 247 ms 47528 KB Output is correct
17 Correct 1109 ms 55344 KB Output is correct
18 Correct 231 ms 48032 KB Output is correct
19 Correct 410 ms 53872 KB Output is correct
20 Correct 1129 ms 106568 KB Output is correct