oj.uz

Submission #110672

# Submission time Handle Problem Language Result Execution time Memory
110672 2019-05-11T21:18:34 Z ioilolcom Bob (COCI14_bob) C++14
24 / 120
 1000 ms 2624 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 384 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 1372 KB Time limit exceeded

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 1656 KB Time limit exceeded

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 1400 KB Time limit exceeded

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1061 ms 1420 KB Time limit exceeded

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 2524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 2532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 57 ms 2552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 59 ms 2624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -