oj.uz

Submission #538801

# Submission time Handle Problem Language Result Execution time Memory
538801 2022-03-17T18:36:23 Z beaconmc Quality Of Living (IOI10_quality) C++14
80 / 100
 5000 ms 141208 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,3001){
        FOR(j,1,3001){
            pref[j][i] += pref[j-1][i];
        }
    }
    FOR(i,0,3001){
        FOR(j,1,3001){
            pref[i][j] += pref[i][j-1];
        }
    }
    FOR(i,0,3001){
        FOR(j,0,3001){
            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 1143 ms 35668 KB Output is correct
2 Correct 1012 ms 35668 KB Output is correct
3 Correct 1196 ms 35668 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1143 ms 35668 KB Output is correct
2 Correct 1012 ms 35668 KB Output is correct
3 Correct 1196 ms 35668 KB Output is correct
4 Correct 1628 ms 36060 KB Output is correct
5 Correct 1530 ms 35976 KB Output is correct
6 Correct 1570 ms 36052 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1143 ms 35668 KB Output is correct
2 Correct 1012 ms 35668 KB Output is correct
3 Correct 1196 ms 35668 KB Output is correct
4 Correct 1628 ms 36060 KB Output is correct
5 Correct 1530 ms 35976 KB Output is correct
6 Correct 1570 ms 36052 KB Output is correct
7 Correct 2033 ms 37792 KB Output is correct
8 Correct 1944 ms 37792 KB Output is correct
9 Correct 2070 ms 37688 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1143 ms 35668 KB Output is correct
2 Correct 1012 ms 35668 KB Output is correct
3 Correct 1196 ms 35668 KB Output is correct
4 Correct 1628 ms 36060 KB Output is correct
5 Correct 1530 ms 35976 KB Output is correct
6 Correct 1570 ms 36052 KB Output is correct
7 Correct 2033 ms 37792 KB Output is correct
8 Correct 1944 ms 37792 KB Output is correct
9 Correct 2070 ms 37688 KB Output is correct
10 Correct 2657 ms 51276 KB Output is correct
11 Correct 2599 ms 51284 KB Output is correct
12 Correct 2343 ms 45408 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1143 ms 35668 KB Output is correct
2 Correct 1012 ms 35668 KB Output is correct
3 Correct 1196 ms 35668 KB Output is correct
4 Correct 1628 ms 36060 KB Output is correct
5 Correct 1530 ms 35976 KB Output is correct
6 Correct 1570 ms 36052 KB Output is correct
7 Correct 2033 ms 37792 KB Output is correct
8 Correct 1944 ms 37792 KB Output is correct
9 Correct 2070 ms 37688 KB Output is correct
10 Correct 2657 ms 51276 KB Output is correct
11 Correct 2599 ms 51284 KB Output is correct
12 Correct 2343 ms 45408 KB Output is correct
13 Execution timed out 5048 ms 141208 KB Time limit exceeded
14 Halted 0 ms 0 KB -