oj.uz

Submission #529462

# Submission time Handle Problem Language Result Execution time Memory
529462 2022-02-23T03:43:28 Z wiwiho Sandcastle 2 (JOI22_ho_t5) C++14
0 / 100
 1395 ms 1048580 KB 
#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define mp make_pair
#define F first
#define S second
#define eb emplace_back
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())

using namespace std;

typedef long long ll;
typedef long double ld;

using pii = pair<int, int>;

ll iceil(ll a, ll b){
    return (a + b - 1) / b;
}

struct rect{
    int u, d, l, r;
    int cnt = 1;
    int area(){
        return (r - l + 1) * (d - u + 1);
    }
};

rect merge(rect a, rect b){
    rect c;
    c.l = min(a.l, b.l);
    c.r = max(a.r, b.r);
    c.u = min(a.u, b.u);
    c.d = max(a.d, b.d);
    c.cnt = a.cnt + b.cnt;
    return c;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int h, w;
    cin >> h >> w;

    vector<vector<int>> a(h + 2, vector<int>(w + 2, INT_MAX));

    vector<pair<int, pii>> tmp;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            cin >> a[i][j];
            tmp.eb(mp(a[i][j], mp(i, j)));
        }
    }
    lsort(tmp);

    vector<vector<vector<rect>>> dp(h + 2, vector<vector<rect>>(w + 2));
    
    vector<pii> dir = {mp(1, 0), mp(0, 1), mp(-1, 0), mp(0, -1)};
    for(auto i : tmp){
        int x = i.S.F, y = i.S.S;
        rect r({x, x, y, y});
        dp[x][y].eb(r);
        for(auto d : dir){
            int nx = x + d.F, ny = y + d.S;
            if(a[nx][ny] >= a[x][y]) continue;
            for(rect& j : dp[nx][ny]){
                dp[x][y].eb(merge(r, j));
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            for(rect r : dp[i][j]){
                if(r.area() == r.cnt) ans++;
            }
        }
    }
    cout << ans << "\n";

    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Runtime error 931 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Runtime error 1395 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Runtime error 1395 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Runtime error 1395 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Runtime error 1395 ms 1048580 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -