Submission #1233038

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233038		simplemind_31	Quality Of Living (IOI10_quality)	C++20	60 / 100	5093 ms	19916 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> intset;
int mini=1e9;
int rectangle(int R, int C, int H, int W, int Q[3001][3001]){
	int med=H*W/2;
	intset help;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			help.insert(Q[i][j]);
		}
	}
	mini=min(mini,*help.find_by_order(med));
	int nowr=H-1,nowc=W-1;
	while(nowr<R){
		if(nowc==C-1){
			//ir a izquierda;
			for(;nowc>C-nowc;nowc--){
				for(int i=nowr-H+1;i<=nowr;i++){
					help.erase(Q[i][nowc]);
				}
				for(int i=nowr-H+1;i<=nowr;i++){
					help.insert(Q[i][nowc-W]);
				}
				mini=min(mini,*help.find_by_order(med));
			}
		}else{
			//ir a derecha;
			for(;nowc<C-1;nowc++){
				for(int i=nowr-H+1;i<=nowr;i++){
					help.erase(Q[i][nowc-W+1]);
				}
				for(int i=nowr-H+1;i<=nowr;i++){
					help.insert(Q[i][nowc+1]);
				}
				mini=min(mini,*help.find_by_order(med));
			}
		}
		if(nowr==R-1){
			break;
		}
		for(int i=nowc-W+1;i<=nowc;i++){
		    help.erase(Q[nowr-H+1][i]);
		}
		for(int i=nowc-W+1;i<=nowc;i++){
			help.insert(Q[nowr+1][i]);
		}
		mini=min(mini,*help.find_by_order(med));
		nowr++;
	}
	return mini;
}

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