Submission #522248

#	Time	Username	Problem	Language	Result	Execution time	Memory
522248		ddy888	Quality Of Living (IOI10_quality)	C++17	100 / 100	1723 ms	119252 KiB

quality

#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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20