oj.uz

Submission #538807

# Submission time Handle Problem Language Result Execution time Memory
538807 2022-03-17T18:47:05 Z beaconmc Quality Of Living (IOI10_quality) C++14
100 / 100
 4490 ms 141272 KB 
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;

#define ll int

ll pos[10000000][2];
ll pref[3001][3001];
ll r, c, h, w;

bool check(ll x){
    FOR(i,0,3001){
        FOR(j,0,3001){
            pref[i][j] = 0;
        }
    }
    FOR(i,1,x+1){
        ll a = pos[i][0];
        ll b = pos[i][1];
        pref[a+1][b+1] += 1;
        pref[max(0, a+1-h)][b+1] -= 1;
        pref[a+1][max(0, b+1-w)] -= 1;
        pref[max(0, a+1-h)][max(0, b+1-w)] += 1;
    }

    FOR(i,0,c-w+1){
        FOR(j,1,r-h+1){
            pref[j][i] += pref[j-1][i];
        }
    }
    FOR(i,0,r-h+1){
        if (pref[i][0] > (h*w)/2){
            return true;
        }
        FOR(j,1,c-w+1){
            pref[i][j] += pref[i][j-1];
            if (pref[i][j] > (h*w)/2){
                return true;
            }
        }
    }
    return false;
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
    r = R; c = C; h = H; w = W;
    FOR(i,0,R){
        FOR(j,0,C){
            pos[Q[i][j]][0] = i;
            pos[Q[i][j]][1] = j;
        }
    }
 
    int lo = 0;
    int hi = int(R*C/2)+1;
    while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		if (check(mid)) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
	return lo;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 35668 KB Output is correct
2 Correct 45 ms 35668 KB Output is correct
3 Correct 49 ms 35668 KB Output is correct
4 Correct 77 ms 36036 KB Output is correct
5 Correct 61 ms 36096 KB Output is correct
6 Correct 58 ms 35960 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 35668 KB Output is correct
2 Correct 45 ms 35668 KB Output is correct
3 Correct 49 ms 35668 KB Output is correct
4 Correct 77 ms 36036 KB Output is correct
5 Correct 61 ms 36096 KB Output is correct
6 Correct 58 ms 35960 KB Output is correct
7 Correct 90 ms 37800 KB Output is correct
8 Correct 99 ms 37836 KB Output is correct
9 Correct 94 ms 37640 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 35668 KB Output is correct
2 Correct 45 ms 35668 KB Output is correct
3 Correct 49 ms 35668 KB Output is correct
4 Correct 77 ms 36036 KB Output is correct
5 Correct 61 ms 36096 KB Output is correct
6 Correct 58 ms 35960 KB Output is correct
7 Correct 90 ms 37800 KB Output is correct
8 Correct 99 ms 37836 KB Output is correct
9 Correct 94 ms 37640 KB Output is correct
10 Correct 369 ms 51284 KB Output is correct
11 Correct 328 ms 51460 KB Output is correct
12 Correct 203 ms 45484 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 35668 KB Output is correct
2 Correct 45 ms 35668 KB Output is correct
3 Correct 49 ms 35668 KB Output is correct
4 Correct 77 ms 36036 KB Output is correct
5 Correct 61 ms 36096 KB Output is correct
6 Correct 58 ms 35960 KB Output is correct
7 Correct 90 ms 37800 KB Output is correct
8 Correct 99 ms 37836 KB Output is correct
9 Correct 94 ms 37640 KB Output is correct
10 Correct 369 ms 51284 KB Output is correct
11 Correct 328 ms 51460 KB Output is correct
12 Correct 203 ms 45484 KB Output is correct
13 Correct 4490 ms 141220 KB Output is correct
14 Correct 4255 ms 141272 KB Output is correct
15 Correct 4263 ms 134152 KB Output is correct