oj.uz

Submission #522248

# Submission time Handle Problem Language Result Execution time Memory
522248 2022-02-04T09:46:01 Z ddy888 Quality Of Living (IOI10_quality) C++17
100 / 100
 1723 ms 119252 KB 
#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#include "quality.h"

int N, M, blockh, blockw;
int A[3010][3010], ss[3010][3010];

int query(int x1, int y1, int x2, int y2) {
    return ss[x2][y2] - ss[x1 - 1][y2] - ss[x2][y1 - 1] + ss[x1 - 1][y1 - 1];
}

int good(int x) {
    memset(ss, 0, sizeof ss);
    for (int i = 1; i <= N; ++i) for (int j = 1; j <= M; ++j) {
        ss[i][j] = ss[i - 1][j] + ss[i][j - 1] - ss[i - 1][j - 1] + (A[i][j] > x);
    }
    for (int i = blockh; i <= N; ++i) for (int j = blockw; j <= M; ++j) {
        int val = query(i - blockh + 1, j - blockw + 1, i, j);
        if (val <= blockh * blockw / 2) return 1;
    }
    return 0;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    N = R, M = C, blockh = H, blockw = W;
    int lo = 0, hi = R * C + 1;
    for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) A[i + 1][j + 1] = Q[i][j];
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (good(mid)) hi = mid;
        else lo = mid;
    }   
    return hi;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 36004 KB Output is correct
2 Correct 48 ms 36000 KB Output is correct
3 Correct 45 ms 36000 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 36004 KB Output is correct
2 Correct 48 ms 36000 KB Output is correct
3 Correct 45 ms 36000 KB Output is correct
4 Correct 64 ms 36692 KB Output is correct
5 Correct 59 ms 36668 KB Output is correct
6 Correct 63 ms 36676 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 36004 KB Output is correct
2 Correct 48 ms 36000 KB Output is correct
3 Correct 45 ms 36000 KB Output is correct
4 Correct 64 ms 36692 KB Output is correct
5 Correct 59 ms 36668 KB Output is correct
6 Correct 63 ms 36676 KB Output is correct
7 Correct 90 ms 39264 KB Output is correct
8 Correct 88 ms 39380 KB Output is correct
9 Correct 79 ms 39240 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 36004 KB Output is correct
2 Correct 48 ms 36000 KB Output is correct
3 Correct 45 ms 36000 KB Output is correct
4 Correct 64 ms 36692 KB Output is correct
5 Correct 59 ms 36668 KB Output is correct
6 Correct 63 ms 36676 KB Output is correct
7 Correct 90 ms 39264 KB Output is correct
8 Correct 88 ms 39380 KB Output is correct
9 Correct 79 ms 39240 KB Output is correct
10 Correct 276 ms 58360 KB Output is correct
11 Correct 245 ms 58332 KB Output is correct
12 Correct 180 ms 51016 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 36004 KB Output is correct
2 Correct 48 ms 36000 KB Output is correct
3 Correct 45 ms 36000 KB Output is correct
4 Correct 64 ms 36692 KB Output is correct
5 Correct 59 ms 36668 KB Output is correct
6 Correct 63 ms 36676 KB Output is correct
7 Correct 90 ms 39264 KB Output is correct
8 Correct 88 ms 39380 KB Output is correct
9 Correct 79 ms 39240 KB Output is correct
10 Correct 276 ms 58360 KB Output is correct
11 Correct 245 ms 58332 KB Output is correct
12 Correct 180 ms 51016 KB Output is correct
13 Correct 1723 ms 119252 KB Output is correct
14 Correct 1707 ms 118872 KB Output is correct
15 Correct 1572 ms 117436 KB Output is correct