Submission #737897

#	Time	Username	Problem	Language	Result	Execution time	Memory
737897		boyliguanhan	Quality Of Living (IOI10_quality)	C++17	100 / 100	1472 ms	70972 KiB

quality

#include "quality.h"
#include<bits/stdc++.h>
#include<bits/extc++.h>
#pragma GCC optimize(2)
using namespace std;
using namespace __gnu_pbds;
#define P(x) pair<x,x>
#define TP(x) tuple<x,x,x>
#define V vector
#define F first
#define S second
#define TT get<2>
#define TS get<1>
#define TF get<0>
#define LE less_equal
#define GE greater_equal
#define all(x) x.begin(), x.end()
#define For(i,s,n) for(int i = s; i < n; i++)
#define Rfor(i,s,n) for(int i = n; i>=s; i--)
#define ForR(i,v) for(auto i:v)
//#define int long long // might cause errors if problem is ioi style
#define ll long long // replacement for above if problem is ioi style
#define PB push_back
#define bll __int128_t //warning: not possible to IO a bll
#define ubll __uint128_t // IO doesn't work for ubll too
#define US unsigned
#define rbt tb_tree_tag
#define splt splay_tree_tag
#define avlt ov_tree_tag
#define Tree(t, cp, tg) tree<t, null_type, cp<i>, tg, tree_order_statistics_node_update>
#define PQ priority_queue
#define GR greater
#define rch(x) x = getchar_unlocked()
#define inf ((ll)(1e18))
#define mod ((int)(1e9+7))
#define db double
#define ldb long double
#define MXN 200100 //change this value according to problem
#define MXM 200100 //change this too
int p[3001][3001];
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
	int l = 1, r = R*C;
	while(l<r) {
		int mid = l + r >> 1;
		bool ans = 0;
		For(i,1,R+1)For(j,1,C+1)p[i][j] = p[i][j-1]+p[i-1][j]-p[i-1][j-1]+(Q[i-1][j-1]>mid);
		For(i,H,R+1)For(j,W,C+1)ans|=(p[i][j]-p[i-H][j]-p[i][j-W]+p[i-H][j-W] <= H*W/2);
		if(ans) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	return l;
}

Compilation message (stderr)

quality.cpp: In function 'int rectangle(int, int, int, int, int (*)[3001])':
quality.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int mid = l + r >> 1;
      |             ~~^~~

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