Submission #356796

#	Time	Username	Problem	Language	Result	Execution time	Memory
356796		Mefarnis	Quality Of Living (IOI10_quality)	C++14	60 / 100	5056 ms	18540 KiB

quality

#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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20