oj.uz

Submission #536297

# Submission time Handle Problem Language Result Execution time Memory
536297 2022-03-12T18:18:24 Z Leo121 Quality Of Living (IOI10_quality) C++14
60 / 100
 5000 ms 18520 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 85 ms 852 KB Output is correct
5 Correct 70 ms 860 KB Output is correct
6 Correct 73 ms 852 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 85 ms 852 KB Output is correct
5 Correct 70 ms 860 KB Output is correct
6 Correct 73 ms 852 KB Output is correct
7 Correct 2622 ms 2872 KB Output is correct
8 Correct 2431 ms 3412 KB Output is correct
9 Correct 2178 ms 3312 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 85 ms 852 KB Output is correct
5 Correct 70 ms 860 KB Output is correct
6 Correct 73 ms 852 KB Output is correct
7 Correct 2622 ms 2872 KB Output is correct
8 Correct 2431 ms 3412 KB Output is correct
9 Correct 2178 ms 3312 KB Output is correct
10 Execution timed out 5012 ms 18520 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 85 ms 852 KB Output is correct
5 Correct 70 ms 860 KB Output is correct
6 Correct 73 ms 852 KB Output is correct
7 Correct 2622 ms 2872 KB Output is correct
8 Correct 2431 ms 3412 KB Output is correct
9 Correct 2178 ms 3312 KB Output is correct
10 Execution timed out 5012 ms 18520 KB Time limit exceeded
11 Halted 0 ms 0 KB -