oj.uz

Submission #356796

# Submission time Handle Problem Language Result Execution time Memory
356796 2021-01-23T17:02:39 Z Mefarnis Quality Of Living (IOI10_quality) C++14
60 / 100
 5000 ms 18540 KB 
#include <bits/stdc++.h>
#include "quality.h"
#include "grader.h"
#define maxn 90003
using namespace std;

int tree[4*maxn];

void update(int cx , int cy , int q , int val , int id) {
	if(cy < q || q < cx)
		return;
	tree[id] += val;
	if(cx == cy)
		return;
	int mid = (cx+cy) >> 1;
	update(cx,mid,q,val,2*id);
	update(mid+1,cy,q,val,2*id+1);
}

int query(int x , int y , int& rem , int id) {
	if(tree[id] < rem) {
		rem -= tree[id];
		return -1;
	}
	if(x == y)
		return x;
	int mid = (x+y) >> 1;
	int l = query(x,mid,rem,2*id);
	if(l != -1)
		return l;
	return query(mid+1,y,rem,2*id+1);
}

int rectangle(int n, int m, int h, int w, int ar[3001][3001]) {
	int mid = (h*w+1)/2 , ans = n*m+1 , N = n*m;
	for( int r1 = 0 ; r1 <= n-h ; r1++ ) {
		int r2 = r1+h-1;
		for( int i = r1 ; i <= r2 ; i++ )
			for( int j = 0 ; j < w ; j++ )
				update(1,N,ar[i][j],1,1);
		int rem = mid;
		ans = min(ans,query(1,N,rem,1));
		for( int c1 = 1 ; c1 <= m-w ; c1++ ) {
			int c2 = c1+w-1;
			for( int i = r1 ; i <= r2 ; i++ ) {
				update(1,N,ar[i][c1-1],-1,1);
				update(1,N,ar[i][c2],1,1);
			}
			rem = mid;
			ans = min(ans,query(1,N,rem,1));
		}
		for( int i = r1 ; i <= r2 ; i++ )
			for( int j = m-w ; j < m ; j++ )
				update(1,N,ar[i][j],-1,1);
	}
	return ans;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 70 ms 876 KB Output is correct
5 Correct 58 ms 876 KB Output is correct
6 Correct 59 ms 1004 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 70 ms 876 KB Output is correct
5 Correct 58 ms 876 KB Output is correct
6 Correct 59 ms 1004 KB Output is correct
7 Correct 2296 ms 3564 KB Output is correct
8 Correct 2339 ms 3508 KB Output is correct
9 Correct 2025 ms 3436 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 70 ms 876 KB Output is correct
5 Correct 58 ms 876 KB Output is correct
6 Correct 59 ms 1004 KB Output is correct
7 Correct 2296 ms 3564 KB Output is correct
8 Correct 2339 ms 3508 KB Output is correct
9 Correct 2025 ms 3436 KB Output is correct
10 Execution timed out 5056 ms 18540 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 70 ms 876 KB Output is correct
5 Correct 58 ms 876 KB Output is correct
6 Correct 59 ms 1004 KB Output is correct
7 Correct 2296 ms 3564 KB Output is correct
8 Correct 2339 ms 3508 KB Output is correct
9 Correct 2025 ms 3436 KB Output is correct
10 Execution timed out 5056 ms 18540 KB Time limit exceeded
11 Halted 0 ms 0 KB -