Submission #110672

#	Time	Username	Problem	Language	Result	Execution time	Memory
110672		ioilolcom	Bob (COCI14_bob)	C++14	24 / 120	1082 ms	2624 KiB

bob

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define pii pair<int,int>
typedef long long int ll;
int n,m;
const int N=507+7;
int g[N][N];
set<int> st;
bool check(int x,int y,int xx,int yy){
	st.clear();
	for(int i=x; i<=xx; i++) {
		for(int j=y; j<=yy; j++) {
			st.insert(g[i][j]);
		}
	}
	return ((int)st.size()==1);
}
int bs1(int i,int j,pii &lol){
	int l=i;
	int r=n;
	int ansx=i;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(i,j,mid,j)) {
			l=mid+1;
			ansx=mid;
		}
		else{
			r=mid-1;
		}
	}
	l=j;
	r=m;
	int ansy=j;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(i,j,ansx,mid)) {
			l=mid+1;
			ansy=mid;
		}
		else{
			r=mid-1;
		}
	}
	lol={ansx,ansy};
	return (ansx-i+1)*(ansy-j+1);
}
int bs2(int i,int j,pii &lol){
	int l=j;
	int r=m;
	int ansy=j;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(i,j,i,mid)) {
			l=mid+1;
			ansy=mid;
		}
		else{
			r=mid-1;
		}
	}
	l=i;
	r=n;
	int ansx=i;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(check(i,j,mid,ansy)) {
			l=mid+1;
			ansx=mid;
		}
		else{
			r=mid-1;
		}
	}
	lol={ansx,ansy};
	return (ansx-i+1)*(ansy-j+1);
}
int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	cin>>n>>m;
	int cnt=0;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin>>g[i][j];
		}
	}
	// i will to binary search for the largest point
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {

			pii one={i,j};
			pii two={i,j};
			cnt=cnt+bs1(i,j,one)+bs2(i,j,two);
			int lol=(min(one.first,two.first)-i+1)*(min(one.second,two.second)-j+1);
			//	cout<<lol<<endl;
			cnt-=lol;

/*
                        cout<<"a point"<<endl;
                        cout<<i<<" "<<j<<endl;
                        cout<<"max for it"<<endl;
                        cout<<1<<endl;
                        cout<<one.first<<" "<<one.second<<endl;
                        cout<<2<<endl;
                        cout<<two.first<<" "<<two.second<<endl;
                        //cout<<lol<<endl;
 */
		}
	}
	cout<<cnt<<endl;
	return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 12
• Subtask 6: 0 / 12
• Subtask 7: 0 / 12
• Subtask 8: 0 / 12
• Subtask 9: 0 / 12
• Subtask 10: 0 / 12