Submission #1017320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017320		NintsiChkhaidze	Quality Of Living (IOI10_quality)	C++17	100 / 100	2479 ms	212008 KiB

quality

#include "quality.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;

int a[3001][3001],pr[3001][3001];

int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	vector <int> values;
	for (int i=0;i<R;i++)
		for (int j=0;j<C;j++)
			values.pb(Q[i][j]);
			
	sort(values.begin(),values.end());
	int l = 0,r = (int)values.size() - 1,ans = -1;
	
//	for (int y: values) cout<<y<<" ";
//	cout<<endl;
//	l = r = 19;
	while (l <= r){
		int mid = (l + r) >> 1;
		int mdn = values[mid],X,Y;
		
		for (int i=0;i<R;i++){
			for (int j=0;j<C;j++){
				if (Q[i][j] > mdn) a[i][j] = +1;
				else if (Q[i][j] < mdn) a[i][j] = -1; 
				else a[i][j] = 0,X=i,Y=j;
//				cout<<a[i][j]<<" ";
			}
//			cout<<endl;
		}
		
		bool check = 0;
		for (int i =0; i <R; i++){
			for (int j=0;j<C;j++){
				pr[i][j] = pr[i-1][j] + pr[i][j - 1] - pr[i - 1][j - 1] + a[i][j];
 			}
		}
		
//		cout<<"! "<<X <<" "<<Y<<endl;
		for (int i = 0 ;i + H - 1 < R; i++){
			for (int j = 0; j + W - 1 < C; j++){
				//if (!(X >= i && X <= i + H - 1 && Y >= j && Y <= j + W - 1)) continue;
				int sum = pr[i+H-1][j+W-1] - pr[i+H-1][j-1] - pr[i-1][j+W-1] + pr[i-1][j-1];
				if (sum<=0) {
//					cout<<"&&& "<<i<<" "<<j<<endl;
				check=1;break;}
			}
		}
		
		if (check){
			ans = mdn;
			r = mid - 1;
		}else{
			l = mid + 1;
		}
	}
	return ans;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:22:25: warning: variable 'X' set but not used [-Wunused-but-set-variable]
   22 |   int mdn = values[mid],X,Y;
      |                         ^
quality.cpp:22:27: warning: variable 'Y' set but not used [-Wunused-but-set-variable]
   22 |   int mdn = values[mid],X,Y;
      |                           ^

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