Submission #406938

#	Time	Username	Problem	Language	Result	Execution time	Memory
406938		pliam	Quality Of Living (IOI10_quality)	C++14	40 / 100	5049 ms	145284 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXR 3005
#define MAXC 3005
#define INF (int)1e9

int st[4*MAXR*MAXC];
int min_med=INF;
int h,w,r,c,q[3005][3005];

void update(int pos,int val,int v=1,int start=1,int end=r*c){
	if(start==end){
		st[v]+=val;
		return;
	}
	int mid=(start+end)/2;
	if(pos<=mid){
		update(pos,val,2*v,start,mid);
	}else{
		update(pos,val,2*v+1,mid+1,end);
	}
	st[v]=st[2*v]+st[2*v+1];
}

int find_k(int k,int v=1,int start=1,int end=r*c){
	if(start==end){
		return start;
	}
	int mid=(start+end)/2;
	if(st[2*v]>=k){
		return find_k(k,2*v,start,mid);
	}else{
		return find_k(k-st[2*v],2*v+1,mid+1,end);
	}
}

int median(){
	return find_k((h*w+1)/2);
}

void brute_force(int x){
	memset(st,0,sizeof(st));
	for(int y=0;y<w;y++){
		for(int x_=x-h+1;x_<=x;x_++){
			update(q[x_][y],1);
		}
	}
	min_med=min(min_med,median());
	for(int y=w;y<c;y++){
		for(int x_=x-h+1;x_<=x;x_++){
			update(q[x_][y],1);
			update(q[x_][y-w],-1);
		}
		min_med=min(min_med,median());
	}
}

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	memset(st,0,sizeof(st));
	r=R;
	c=C;
	h=H;
	w=W;
	for(int a=0;a<r;a++){
		for(int b=0;b<c;b++){
			q[a][b]=Q[a][b];
		}
	}
	for(int a=h-1;a<r;a++){
		brute_force(a);
	}
	
	return min_med;
}

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20