Submission #536297

#	Time	Username	Problem	Language	Result	Execution time	Memory
536297		Leo121	Quality Of Living (IOI10_quality)	C++14	60 / 100	5012 ms	18520 KiB

quality

#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#include "grader.h"
///#include "quality.h"
using namespace std;
const int lim = 36e4;
int st[lim + 2];
void update(int nodo, int l, int r, int pos, int x){
    if(l > pos || r < pos){
        return;
    }
    if(l == r){
        st[nodo] += x;
        return;
    }
    int mitad = (l + r) / 2;
    update(nodo * 2, l, mitad, pos, x);
    update(nodo * 2 + 1, mitad + 1, r, pos, x);
    st[nodo] = st[nodo * 2] + st[nodo * 2 + 1];
}
int query(int nodo, int l, int r, int buscado, int acu){
    if(l == r){
        return l;
    }
    int mitad = (l + r) / 2;
    return (st[nodo * 2] + acu < buscado) ? query(nodo * 2 + 1, mitad + 1, r, buscado, acu + st[nodo * 2]) : query(nodo * 2, l, mitad, buscado, acu);
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int res = INT_MAX;
    int buscado = (H * W) / 2;
    buscado ++;
    forn(i, 0, R - H){
        forn(j, i, i + H - 1){
            forn(k, 0, W - 1){
                update(1, 1, R * C, Q[j][k], 1);
            }
        }
        res = min(res, query(1, 1, R * C, buscado, 0));
        forn(j, 1, C - W){
            forn(k, i, i + H - 1){
                update(1, 1, R * C, Q[k][j - 1], -1);
            }
            forn(k, i, i + H - 1){
                update(1, 1, R * C, Q[k][j + W - 1], 1);
            }
            res = min(res, query(1, 1, R * C, buscado, 0));
        }
        forn(j, i, i + H - 1){
            forn(k, C - W, C - 1){
                update(1, 1, R * C, Q[j][k], -1);
            }
        }
    }
    return res;
}

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