Submission #825388

#	Time	Username	Problem	Language	Result	Execution time	Memory
825388		FEDIKUS	Rectangles (IOI19_rect)	C++17	72 / 100	5114 ms	861176 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=2510;

int n,m;
vector<vector<int> > a;
int ul[maxn][maxn],ud[maxn][maxn];
vector<pii> ver[maxn];
int bit[maxn];

void add(int x,int t=1){
	x++;
	for(;x<maxn;x+=x&-x) bit[x]+=t;
}
int qry(int x){
	int ret=0;
	x++;
	if(x==0) return 0;
	for(;x>0;x-=x&-x) ret+=bit[x];
	return ret;
}
int query(int l,int r){
	return qry(r)-qry(l-1);
}

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);
			if(ul[i][j]==j-1) ul[i][j]=-1;
		} 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);
			if(ud[i][j]==j+1) ud[i][j]=-1;
			if(ud[i][j]!=-1 && a[i][j]==a[i][ud[i][j]]) ud[i][j]=-1;
		} 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_back(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_back(pii(j,stek.top()));}
			stek.push(j);
		} while(!stek.empty()) stek.pop();
		sort(ver[i].begin(),ver[i].end());
	}

	bool prvi=true;
	map<tuple<int,int,int,int>,int> sr; // col, vr, u, d
	map<tuple<int,int,int,int>,int> sl;
	for(int _=0;_<2;_++){
		// 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(prvi){
					sr[{l,r,u+1,d-1}]=-1;
					sl[{r,l,u+1,d-1}]=-1;
					continue;
				}else if(sr[{l,r,u+1,d-1}]+sl[{r,l,u+1,d-1}]!=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(prvi){
					sr[{l,r,u+1,d-1}]=-1;
					sl[{r,l,u+1,d-1}]=-1;
					continue;
				}else if(sr[{l,r,u+1,d-1}]+sl[{r,l,u+1,d-1}]!=d-u-1) continue;

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

				res++;
			}
			swap(tren,novi);
		} tren.clear();
		if(!prvi) break;
		prvi=false;
		int pcol=-1;
		int pvr=-1;
		map<int,vector<int> > gde;
		for(auto &x:sr){
			auto [col,vr,u,d]=x.first;
			if(col!=pcol){
				gde.clear();
				for(int i=0;i<maxn;i++) bit[i]=0;
				for(int i=0;i<n;i++) gde[ud[i][col]].push_back(i);
				pvr=-1;
				pcol=col;
			}
			if(vr!=pvr){
				if(pvr!=-1) for(int i:gde[pvr]) add(i,-1);
				for(int i:gde[vr]) add(i,1);
				pvr=vr;
			}
			x.second=query(u,d);
		}
		pcol=-1;
		pvr=-1;
		gde.clear();
		for(auto &x:sl){
			auto [col,vr,u,d]=x.first;
			if(col!=pcol){
				gde.clear();
				for(int i=0;i<maxn;i++) bit[i]=0;
				for(int i=0;i<n;i++) gde[ul[i][col]].push_back(i);
				pvr=-1;
				pcol=col;
			}
			if(vr!=pvr){
				if(pvr!=-1) for(int i:gde[pvr]) add(i,-1);
				for(int i:gde[vr]) add(i,1);
				pvr=vr;
			}
			x.second=query(u,d);
		}
		
	}
	return res;
}

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