Round C 2019 - Kick Start 2019 Circuit Board

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <list>
#include <limits.h>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>

using namespace std;

int R,C,K;

void update_max_struct(list<pair<int,int>>& l,int i,int val) {
	if(l.empty())
		l.push_back(make_pair(i,val));
	else {
		if(val<=l.back().second) {
			l.push_back(make_pair(i,val));
		}
		else {
			while(!l.empty()&&val>l.back().second) {
				l.pop_back();
			}
			l.push_back(make_pair(i,val));
		}
	}
}
void update_min_struct(list<pair<int,int>>& l,int i,int val) {
	if(l.empty())
		l.push_back(make_pair(i,val));
	else {
		if(val>=l.back().second) {
			l.push_back(make_pair(i,val));
		}
		else {
			while(!l.empty()&&val<l.back().second) {
				l.pop_back();
			}
			l.push_back(make_pair(i,val));
		}
	}
}

void make_h(vector<vector<int>>& grid,vector<vector<int>>& h) {
	for(int i=0;i<R;++i) {
		list<pair<int,int>> l1;
		list<pair<int,int>> l2;
		int count = 0;
		int l = 0,r = 0;
		while(l<C) {
			if(r>=C) {
				h[i][l] = count;
				--count;++l;
				continue;
			}
			if(l1.size()==0 || l2.size()==0) {
				update_max_struct(l1,r,grid[i][r]);
				update_min_struct(l2,r,grid[i][r]);
				++count;++r;
				continue;
			}

			int max_h = max(l1.front().second,grid[i][r]);
			int min_h = min(l2.front().second,grid[i][r]);
			
			if(abs(max_h-min_h)<=K) {
				update_max_struct(l1,r,grid[i][r]);
				update_min_struct(l2,r,grid[i][r]);
				++r; ++count;
			}
			else {
				h[i][l] = count;
				count--;
				if(l1.front().first==l)
					l1.pop_front();
				if(l2.front().first==l)
					l2.pop_front();
				++l;
			}
		}
	}
}

void make_h1(vector<vector<int>>& grid,vector<vector<int>>& h) {
	for(int i=0;i<R;++i) {
		for(int j=0;j<C;++j) {
			int min_h = grid[i][j],max_h = grid[i][j],count = 1;
			for(int k=j+1;k<C;++k) {
				min_h = min(grid[i][k],min_h);
				max_h = max(grid[i][k],max_h);
				if(abs(min_h-max_h)<=K)
					++count;
				else break;
			}
			h[i][j] = count;
		}
	}
}

int largestRectangleArea(vector<int> &height) {
	int r = 0;
	stack<int> st;
	height.push_back(0);
	for (int i = 0; i < height.size(); ++i) {
		if (st.empty() || height[st.top()] < height[i]) {
			st.push(i);
		} else {
			int cur = st.top(); 
			st.pop();
			r = max(r, height[cur] * (st.empty() ? i : (i - st.top() - 1)));
			--i;
		}     
	}
	return r;
}

void helper(vector<vector<int>>& h,int& res) {
	for(int j=0;j<C;++j) {
		vector<int> temp(R,0);
		for(int i=0;i<R;++i)
			temp[i] = h[i][j];
		int cur = largestRectangleArea(temp);
		res = max(res,cur);
	}
}

int main() {
	int T;
	cin >> T;
	for(int t=0;t<T;++t) {
        int res = 0;
		cin >> R >> C >> K;
		vector<vector<int>> grid(R,vector<int>(C,0));
		for(int i=0;i<R;++i) {
			for(int j=0;j<C;++j)
				cin >> grid[i][j];
		}
		vector<vector<int>> h(R,vector<int>(C,0));
		make_h(grid,h);
		helper(h,res);
		cout << "Case #" << t+1 << ":" << " " << res << endl; 
	}
    return 0;
}