Submission #825360

#	Time	Username	Problem	Language	Result	Execution time	Memory
825360		FEDIKUS	Rectangles (IOI19_rect)	C++17	49 / 100	804 ms	252956 KiB

rect

#include "rect.h"
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<algorithm>

using namespace std;
using ll = long long;
using pii = pair<int,int>;

const int maxn=710;

int n,m;
vector<vector<int> > a;
int ul[maxn][maxn],ud[maxn][maxn];
set<pii> ver[maxn];
vector<int> sl[maxn][4*maxn],sr[maxn][4*maxn]; // -1 = nema, -2 = ima suvise, else = vrednost
int tmp[maxn];

void build(vector<int>* segt,int *a,int ind=1,int l=0,int r=n-1){
	if(l==r){segt[ind]={a[l]}; return;}
	int mid=l+(r-l)/2;
	build(segt,a,2*ind,l,mid);
	build(segt,a,2*ind+1,mid+1,r);
	merge(segt[2*ind].begin(),segt[2*ind].end(),segt[2*ind+1].begin(),segt[2*ind+1].end(),back_inserter(segt[ind]));
}
int query(vector<int> *segt,int tl,int tr,int t,int ind=1,int l=0,int r=n-1){
	if(tl<=l && r<=tr){
		return upper_bound(segt[ind].begin(),segt[ind].end(),t)-lower_bound(segt[ind].begin(),segt[ind].end(),t);
	}
	int mid=l+(r-l)/2;
	int ret=0;
	if(tl<=mid) ret+=query(segt,tl,tr,t,2*ind,l,mid);
	if(tr>mid) ret+=query(segt,tl,tr,t,2*ind+1,mid+1,r);
	return ret;
}

int res=0;

ll count_rectangles(vector<vector<int> > _a){
	swap(a,_a); n=a.size(); m=a[0].size();

	for(int i=0;i<n;i++){
		stack<int> stek;
		for(int j=0;j<m;j++){
			while(!stek.empty() && a[i][stek.top()]<a[i][j]) stek.pop();
			if(stek.empty()) ul[i][j]=-1;
			else ul[i][j]=stek.top();
			stek.push(j);
		} while(!stek.empty()) stek.pop();
		for(int j=m-1;j>=0;j--){
			while(!stek.empty() && a[i][stek.top()]<a[i][j]) stek.pop();
			if(stek.empty()) ud[i][j]=-1;
			else ud[i][j]=stek.top();
			stek.push(j);
		} while(!stek.empty()) stek.pop();
	}
	for(int i=0;i<m;i++){
		stack<int> stek;
		for(int j=0;j<n;j++){
			while(!stek.empty() && a[stek.top()][i]<a[j][i]) stek.pop();
			if(!stek.empty()){ver[i].emplace(pii(stek.top(),j));}
			stek.push(j);
		} while(!stek.empty()) stek.pop();
		for(int j=n-1;j>=0;j--){
			while(!stek.empty() && a[stek.top()][i]<a[j][i]) stek.pop();
			if(!stek.empty()){ver[i].emplace(pii(j,stek.top()));}
			stek.push(j);
		} while(!stek.empty()) stek.pop();
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(ud[i][j]==j+1) ud[i][j]=-1;
			if(ul[i][j]==j-1) ul[i][j]=-1;
			if(ud[i][j]==-1) continue;
			if(a[i][j]!=a[i][ud[i][j]]) continue;
			ud[i][j]=-1;
		}
	}
	
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++) tmp[j]=ul[j][i];
		build(sl[i],tmp);
		for(int j=0;j<n;j++) tmp[j]=ud[j][i];
		build(sr[i],tmp);
	}

	// desni cosak
	map<pii,int> tren;
	for(int j=1;j<m;j++){
		map<pii,int> novi;
		for(pii x:ver[j]){
			if(x.second-x.first==1) continue;
			if(tren.find(x)==tren.end()) novi[x]=j;
			else novi[x]=tren[x];
		}
		for(auto x:tren){
			int u,d,r,l;
			u=x.first.first; d=x.first.second; r=j; l=x.second-1;
			if(ul[u+1][r]==-1) continue;
			if(ul[u+1][r]<l) continue;
			l=ul[u+1][r];

			if(query(sr[l],u+1,d-1,r)+query(sl[r],u+1,d-1,l)!=d-u-1) continue;

			#ifdef DEBUG
			cout<<u<<" "<<d<<" "<<l<<" "<<r<<"\n";
			#endif

			res++;
		}
		swap(tren,novi);
	} tren.clear();
	// levi cosak
	for(int j=m-2;j>=0;j--){
		map<pii,int> novi;
		for(pii x:ver[j]){
			if(x.second-x.first==1) continue;
			if(tren.find(x)==tren.end()) novi[x]=j;
			else novi[x]=tren[x];
		}
		for(auto x:tren){
			int u,d,r,l;
			u=x.first.first; d=x.first.second; l=j; r=x.second+1;
			if(ud[u+1][l]==-1) continue;
			if(ud[u+1][l]>r) continue;
			r=ud[u+1][l];

			if(query(sr[l],u+1,d-1,r)+query(sl[r],u+1,d-1,l)!=d-u-1) continue;

			#ifdef DEBUG
			cout<<u<<" "<<d<<" "<<l<<" "<<r<<"\n";
			#endif

			res++;
		}
		swap(tren,novi);
	} tren.clear();
	return res;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 0 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28