제출 #734778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
734778		That_Salamander	삶의 질 (IOI10_quality)	C++14	60 / 100	5046 ms	49664 KiB

quality

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

const int SIZE = 1000;
int t[25000000], lazy[25000000];

void push(int v, int tlx, int trx, int tly, int try_) {
    if (v >= 25000000) exit(0);
    if (lazy[v] == 0 || tlx == trx) return;

    t[4 * v + 0] += lazy[v];
    t[4 * v + 1] += lazy[v];
    t[4 * v + 2] += lazy[v];
    t[4 * v + 3] += lazy[v];

    lazy[4 * v + 0] += lazy[v];
    lazy[4 * v + 1] += lazy[v];
    lazy[4 * v + 2] += lazy[v];
    lazy[4 * v + 3] += lazy[v];

    lazy[v] = 0;
}

int max(int a, int b, int c, int d) {
    return max(max(a, b), max(c, d));
}

void update(int v, int qlx, int qrx, int qly, int qry, int tlx = 0, int trx = SIZE - 1, int tly = 0, int try_ = SIZE - 1) {
    push(v, tlx, trx, tly, try_);

    if (qlx > trx || qrx < tlx || qly > try_ || qry < tly) return;

    if (qlx <= tlx && trx <= qrx && qly <= tly && try_ <= qry) {
        t[v] += 1;
        lazy[v] += 1;
        return;
    }

    int tmx = (tlx + trx) / 2;
    int tmy = (tly + try_) / 2;

    update(4 * v + 0, qlx, qrx, qly, qry, tlx, tmx, tly, tmy);
    update(4 * v + 1, qlx, qrx, qly, qry, tlx, tmx, tmy + 1, try_);
    update(4 * v + 2, qlx, qrx, qly, qry, tmx + 1, trx, tly, tmy);
    update(4 * v + 3, qlx, qrx, qly, qry, tmx + 1, trx, tmy + 1, try_);

    t[v] = max(t[4 * v + 0], t[4 * v + 1], t[4 * v + 2], t[4 * v + 3]);
}

int query(int v, int qlx, int qrx, int qly, int qry, int tlx = 0, int trx = SIZE - 1, int tly = 0, int try_ = SIZE - 1) {
    push(v, tlx, trx, tly, try_);

    if (qlx > trx || qrx < tlx || qly > try_ || qry < tly) return 0;

    if (qlx <= tlx && trx <= qrx && qly <= tly && try_ <= qry) {
        return t[v];
    }

    int tmx = (tlx + trx) / 2;
    int tmy = (tly + try_) / 2;

    return max(
        query(4 * v + 0, qlx, qrx, qly, qry, tlx, tmx, tly, tmy),
        query(4 * v + 1, qlx, qrx, qly, qry, tlx, tmx, tmy + 1, try_),
        query(4 * v + 2, qlx, qrx, qly, qry, tmx + 1, trx, tly, tmy),
        query(4 * v + 3, qlx, qrx, qly, qry, tmx + 1, trx, tmy + 1, try_)
    );
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    vector<pair<int, pii>> ord;

    FOR(i, R) {
        FOR(j, C) {
            ord.push_back({ Q[i][j], {i, j} });
        }
    }

    sort(ord.begin(), ord.end());

    for (auto p: ord) {
        int x = p.second.first;
        int y = p.second.second;

        update(1, max(0, x - H + 1), x, max(0, y - W + 1), y);

        //cout << query(0, 0, R - 1, 0, C - 1) << endl;
        if (query(1, 0, R - H, 0, C - W) == (H * W + 1) / 2) {
            return p.first;
        }
    }

    //cout << "ERROR" << endl;
    return -1;
}

#ifdef LOCAL_TEST
int grid[3001][3001];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    freopen("quality.in", "r", stdin);
    
    int r, c, h, w;
    cin >> r >> c >> h >> w;


    FOR(i, r) {
        FOR(j, c) {
            cin >> grid[i][j];
        }
    }

    cout << rectangle(r, c, h, w, grid) << endl;
}
#endif

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20