oj.uz

Submission #538803

# Submission time Handle Problem Language Result Execution time Memory
538803 2022-03-17T18:41:02 Z beaconmc Quality Of Living (IOI10_quality) C++14
80 / 100
 5000 ms 141184 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){
            if (pref[i][j-1] > (h*w)/2){
                return true;
            }
            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 1061 ms 35668 KB Output is correct
2 Correct 988 ms 35680 KB Output is correct
3 Correct 1100 ms 35668 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1061 ms 35668 KB Output is correct
2 Correct 988 ms 35680 KB Output is correct
3 Correct 1100 ms 35668 KB Output is correct
4 Correct 1507 ms 36060 KB Output is correct
5 Correct 1404 ms 36048 KB Output is correct
6 Correct 1427 ms 36056 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1061 ms 35668 KB Output is correct
2 Correct 988 ms 35680 KB Output is correct
3 Correct 1100 ms 35668 KB Output is correct
4 Correct 1507 ms 36060 KB Output is correct
5 Correct 1404 ms 36048 KB Output is correct
6 Correct 1427 ms 36056 KB Output is correct
7 Correct 1898 ms 37792 KB Output is correct
8 Correct 1803 ms 37792 KB Output is correct
9 Correct 1884 ms 37692 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1061 ms 35668 KB Output is correct
2 Correct 988 ms 35680 KB Output is correct
3 Correct 1100 ms 35668 KB Output is correct
4 Correct 1507 ms 36060 KB Output is correct
5 Correct 1404 ms 36048 KB Output is correct
6 Correct 1427 ms 36056 KB Output is correct
7 Correct 1898 ms 37792 KB Output is correct
8 Correct 1803 ms 37792 KB Output is correct
9 Correct 1884 ms 37692 KB Output is correct
10 Correct 2510 ms 51288 KB Output is correct
11 Correct 2429 ms 51284 KB Output is correct
12 Correct 2226 ms 45408 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1061 ms 35668 KB Output is correct
2 Correct 988 ms 35680 KB Output is correct
3 Correct 1100 ms 35668 KB Output is correct
4 Correct 1507 ms 36060 KB Output is correct
5 Correct 1404 ms 36048 KB Output is correct
6 Correct 1427 ms 36056 KB Output is correct
7 Correct 1898 ms 37792 KB Output is correct
8 Correct 1803 ms 37792 KB Output is correct
9 Correct 1884 ms 37692 KB Output is correct
10 Correct 2510 ms 51288 KB Output is correct
11 Correct 2429 ms 51284 KB Output is correct
12 Correct 2226 ms 45408 KB Output is correct
13 Execution timed out 5067 ms 141184 KB Time limit exceeded
14 Halted 0 ms 0 KB -