oj.uz

Submission #367385

# Submission time Handle Problem Language Result Execution time Memory
367385 2021-02-17T05:18:47 Z ijxjdjd Quality Of Living (IOI10_quality) C++14
100 / 100
 4187 ms 156988 KB 
using namespace std;
#include <bits/stdc++.h>
#include "quality.h"

#pragma GCC optimize ("Ofast")
#pragma GCC target("avx2")

#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)
int pref[3001][3001];
pair<int, int> coords[3001*3001];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    int low = 0;
    int high = R*C-1;
    FR(i, R){
        FR(j, C){
            coords[Q[i][j]-1] = {i, j};
        }
    }
    auto sum = [&] (int i, int j) {
        return pref[i][j] - (i >= H ? pref[i-H][j] : 0) - (j >= W ? pref[i][j-W] : 0) + (j >= W && i >= H ? pref[i-H][j-W] : 0);
    };
    int base = H*W/2;
    while (low < high) {
        int mid = (low + high)/2;
        memset(pref, 0, sizeof(pref));
        FR(i, mid+1) {
            pref[coords[i].first][coords[i].second]++;
        }
        FR(i, R) {
            FR(j, C) {
                pref[i][j] += (i > 0 ? pref[i-1][j] : 0) + (j > 0 ? pref[i][j-1] : 0) - (i > 0 && j > 0 ? pref[i-1][j-1] : 0);
                if (sum(i, j) > base) {
                    high = mid;
                }
            }
        }
        if (high != mid) {
            low = mid+1;
        }
    }
    return high+1;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 35692 KB Output is correct
2 Correct 63 ms 35760 KB Output is correct
3 Correct 60 ms 35820 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 35692 KB Output is correct
2 Correct 63 ms 35760 KB Output is correct
3 Correct 60 ms 35820 KB Output is correct
4 Correct 79 ms 36076 KB Output is correct
5 Correct 79 ms 36076 KB Output is correct
6 Correct 80 ms 36076 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 35692 KB Output is correct
2 Correct 63 ms 35760 KB Output is correct
3 Correct 60 ms 35820 KB Output is correct
4 Correct 79 ms 36076 KB Output is correct
5 Correct 79 ms 36076 KB Output is correct
6 Correct 80 ms 36076 KB Output is correct
7 Correct 117 ms 37868 KB Output is correct
8 Correct 117 ms 37868 KB Output is correct
9 Correct 110 ms 37740 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 35692 KB Output is correct
2 Correct 63 ms 35760 KB Output is correct
3 Correct 60 ms 35820 KB Output is correct
4 Correct 79 ms 36076 KB Output is correct
5 Correct 79 ms 36076 KB Output is correct
6 Correct 80 ms 36076 KB Output is correct
7 Correct 117 ms 37868 KB Output is correct
8 Correct 117 ms 37868 KB Output is correct
9 Correct 110 ms 37740 KB Output is correct
10 Correct 451 ms 51308 KB Output is correct
11 Correct 421 ms 51436 KB Output is correct
12 Correct 260 ms 45520 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 35692 KB Output is correct
2 Correct 63 ms 35760 KB Output is correct
3 Correct 60 ms 35820 KB Output is correct
4 Correct 79 ms 36076 KB Output is correct
5 Correct 79 ms 36076 KB Output is correct
6 Correct 80 ms 36076 KB Output is correct
7 Correct 117 ms 37868 KB Output is correct
8 Correct 117 ms 37868 KB Output is correct
9 Correct 110 ms 37740 KB Output is correct
10 Correct 451 ms 51308 KB Output is correct
11 Correct 421 ms 51436 KB Output is correct
12 Correct 260 ms 45520 KB Output is correct
13 Correct 4187 ms 141316 KB Output is correct
14 Correct 4145 ms 156988 KB Output is correct
15 Correct 3755 ms 148124 KB Output is correct