oj.uz

Submission #501088

# Submission time Handle Problem Language Result Execution time Memory
501088 2022-01-02T10:52:25 Z beaconmc Quality Of Living (IOI10_quality) C++14
100 / 100
 3942 ms 210688 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;


int pos[9000001][2];
int pref[3001][3001];
int r,c,h,w;


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

    FOR(i,0,r-h+1){
        if (pref[i][0] > int(h*w/2)) return true;
        FOR(j,1,c-w+1){
            pref[i][j] += pref[i][j-1];
            if (pref[i][j]> int(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 35660 KB Output is correct
2 Correct 41 ms 35604 KB Output is correct
3 Correct 46 ms 35660 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 35660 KB Output is correct
2 Correct 41 ms 35604 KB Output is correct
3 Correct 46 ms 35660 KB Output is correct
4 Correct 62 ms 36044 KB Output is correct
5 Correct 57 ms 36044 KB Output is correct
6 Correct 65 ms 36040 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 35660 KB Output is correct
2 Correct 41 ms 35604 KB Output is correct
3 Correct 46 ms 35660 KB Output is correct
4 Correct 62 ms 36044 KB Output is correct
5 Correct 57 ms 36044 KB Output is correct
6 Correct 65 ms 36040 KB Output is correct
7 Correct 83 ms 37700 KB Output is correct
8 Correct 84 ms 37792 KB Output is correct
9 Correct 82 ms 37704 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 35660 KB Output is correct
2 Correct 41 ms 35604 KB Output is correct
3 Correct 46 ms 35660 KB Output is correct
4 Correct 62 ms 36044 KB Output is correct
5 Correct 57 ms 36044 KB Output is correct
6 Correct 65 ms 36040 KB Output is correct
7 Correct 83 ms 37700 KB Output is correct
8 Correct 84 ms 37792 KB Output is correct
9 Correct 82 ms 37704 KB Output is correct
10 Correct 308 ms 51408 KB Output is correct
11 Correct 275 ms 57924 KB Output is correct
12 Correct 171 ms 48688 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 35660 KB Output is correct
2 Correct 41 ms 35604 KB Output is correct
3 Correct 46 ms 35660 KB Output is correct
4 Correct 62 ms 36044 KB Output is correct
5 Correct 57 ms 36044 KB Output is correct
6 Correct 65 ms 36040 KB Output is correct
7 Correct 83 ms 37700 KB Output is correct
8 Correct 84 ms 37792 KB Output is correct
9 Correct 82 ms 37704 KB Output is correct
10 Correct 308 ms 51408 KB Output is correct
11 Correct 275 ms 57924 KB Output is correct
12 Correct 171 ms 48688 KB Output is correct
13 Correct 3942 ms 210656 KB Output is correct
14 Correct 3626 ms 210688 KB Output is correct
15 Correct 3527 ms 196452 KB Output is correct