oj.uz

Submission #234933

# Submission time Handle Problem Language Result Execution time Memory
234933 2020-05-26T11:10:34 Z anubhavdhar Quality Of Living (IOI10_quality) C++14
100 / 100
 2332 ms 216116 KB 
#include<bits/stdc++.h>
#include "quality.h"
 
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define F0R(i,n) for(int i=0;i<(n);++i)
#define F0Re(i,n) for(int i=1;i<=(n);++i)
#define F0Rr(i,a,b) for(ll i=(a);i<(b);++i)
#define F0Rrev(i,n) for(int i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first 
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cout<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()
 
using namespace std;
 
const short int __PRECISION = 10;
/*
const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 2e5+5;
const ll ROOTN = 320;
 
const ldd PI = acos(-1);
const ldd EPS = 1e-7;
*/
int rect[3000][3000], pre[3000][3000];
pair<int, int> Lookup[9000000];
 
#define in(t) (Lookup[t].ff > i-H && Lookup[t].ff <= i && Lookup[t].ss > j-W && Lookup[t].ss <= j)
 
inline bool bs(int R, int C, int H, int W, int target)
{
	if(target < (H*W)/2)
		return false;
	F0R(i, R)
		F0R(j ,C)
		{
			pre[i][j] = (rect[i][j] == target ? 0 : (rect[i][j] < target ? -1 : 1)) + (i==0 ? 0 : pre[i-1][j]) + (j==0 ? 0 : pre[i][j-1])
						- ((i==0||j==0) ? 0 : pre[i-1][j-1]);
	// 	}
	// cout<<"target = "<<target<<'\n';
	// F0R(i, R)
	// {
	// 	F0R(j, C)
	// 		cout<<pre[i][j]<<' ';
	// 	cout<<endl;
	// }
	// F0R(i, R)
	// 	F0R(j, C)
	// 	{
			if(i >= H-1 && j >= W-1)
			{
				int tmp = pre[i][j] - (i==H-1 ? 0 : pre[i-H][j]) - (j==W-1 ? 0 : pre[i][j-W]) + ((i==H-1||j==W-1) ? 0 : pre[i-H][j-W]);
				if((tmp < 0) || (tmp == 0 && in(target)))
				{
					// cout<<"found target = "<<target<<" at "<<i<<","<<j<<endl;
					return true;
				}
			}
		}
	return false;
}
 
int rectangle(int R, int C, int H, int W, int(* Q)[3001])
{
	F0R(i, R)
		F0R(j, C)
			rect[i][j] = Q[i][j]-1;
	F0R(i, R)
		F0R(j, C)
			Lookup[rect[i][j]] = mp(i, j);
	int lo = 0, hi = R*C - 1, mid;
	while(hi > lo + 1)
	{
		// cout<<"lo = "<<lo<<", hi = "<<hi<<endl;
		mid = (hi + lo)/2;
		if(bs(R, C, H, W, mid))
			hi = mid;
		else
			lo = mid;
	}
	return hi+1;
}
/*
int main()
{
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int R, C, H, W;
	cin>>R>>C>>H>>W;
	vector<vector<int>> Q(R, vector<int> (C));
	F0R(i, R)
		F0R(j, C)	
			cin>>Q[i][j];
	cout<<rectangle(R, C, H, W, Q);
	return 0;
}
5 5 3 3
5 11 12 16 25
17 18 2 7 10
4 23 20 3 1
24 21 19 14 9
6 22 8 13 15
*/

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 788 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 788 KB Output is correct
4 Correct 7 ms 1792 KB Output is correct
5 Correct 7 ms 1792 KB Output is correct
6 Correct 7 ms 1792 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 788 KB Output is correct
4 Correct 7 ms 1792 KB Output is correct
5 Correct 7 ms 1792 KB Output is correct
6 Correct 7 ms 1792 KB Output is correct
7 Correct 24 ms 6272 KB Output is correct
8 Correct 25 ms 6176 KB Output is correct
9 Correct 23 ms 6016 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 788 KB Output is correct
4 Correct 7 ms 1792 KB Output is correct
5 Correct 7 ms 1792 KB Output is correct
6 Correct 7 ms 1792 KB Output is correct
7 Correct 24 ms 6272 KB Output is correct
8 Correct 25 ms 6176 KB Output is correct
9 Correct 23 ms 6016 KB Output is correct
10 Correct 242 ms 38724 KB Output is correct
11 Correct 240 ms 38648 KB Output is correct
12 Correct 116 ms 25464 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 788 KB Output is correct
4 Correct 7 ms 1792 KB Output is correct
5 Correct 7 ms 1792 KB Output is correct
6 Correct 7 ms 1792 KB Output is correct
7 Correct 24 ms 6272 KB Output is correct
8 Correct 25 ms 6176 KB Output is correct
9 Correct 23 ms 6016 KB Output is correct
10 Correct 242 ms 38724 KB Output is correct
11 Correct 240 ms 38648 KB Output is correct
12 Correct 116 ms 25464 KB Output is correct
13 Correct 2332 ms 216116 KB Output is correct
14 Correct 2313 ms 215920 KB Output is correct
15 Correct 2090 ms 204160 KB Output is correct