Submission #156797

#	Time	Username	Problem	Language	Result	Execution time	Memory
156797		guangxuan	Rectangles (IOI19_rect)	C++14	100 / 100	3455 ms	650644 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define SZ(X) (int)X.size()
#define PB push_back
#define ALL(X) X.begin(),X.end()
#define RI(X) scanf("%d",&X)
#define RII(X,Y) scanf("%d%d",&X,&Y)
#define RIII(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z)
#define DRI(X) int X;scanf("%d",&X)
#define DRII(X,Y) int X,Y;scanf("%d%d",&X,&Y)
#define DRIII(X,Y,Z) int X,Y,Z;scanf("%d%d%d",&X,&Y,&Z)
#define MS0(X) memset(X,0,sizeof(X));
#define MS1(X) memset(X,-1,sizeof(X));
#define REP(I,N) for(int I=0;I<N;++I)
#define REPP(I,A,B) for(int I=A;I<B;++I)

using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
typedef pair<LL,LL> PLL;

int R,C;
int d[2509][2509];
vector<PII> LU[2509][2509];
vector<PII> UL[2509][2509];

long long count_rectangles(std::vector<std::vector<int> > a) {
	R=SZ(a);C=SZ(a[0]);
	REP(i,R)REP(j,C)d[i][j]=a[i][j];
	REP(i,R){
		stack<int> st;
		REP(j,C){
			while(st.size()&&(d[i][st.top()]<d[i][j])){//look for first left value >=!
				st.pop();
			}
			if(st.size()){
				int k = st.top();
				if(j-k>=2){
					if(i){
						auto it = lower_bound(ALL(LU[i-1][j]),MP(k,0));
						if(it!=LU[i-1][j].end()&&it->F==k) LU[i][j].PB(MP(k,it->S));
						else LU[i][j].PB(MP(k,i));
					}
					else LU[i][j].PB(MP(k,i));
				}
			}
			st.push(j);
		}
		while(SZ(st))st.pop();
		for(int j=C-1;j>=0;j--){
			while(st.size()&&d[i][st.top()]<d[i][j]){//look for first right value >=!
				st.pop();
			}
			if(st.size()){
				int k = st.top();
				if(d[i][k]!=d[i][j] && k-j>=2){
					if(i){
						auto it = lower_bound(ALL(LU[i-1][k]),MP(j,0));
						if(it!=LU[i-1][k].end()&&it->F==j) LU[i][k].PB(MP(j,it->S));
						else LU[i][k].PB(MP(j,i));
					}
					else LU[i][k].PB(MP(j,i));
				}
			}
			st.push(j);
		}
		REP(j,C)sort(ALL(LU[i][j]));
		/*REP(j,C){
			printf ("PRINTING square: %d, %d\n",i,j);
			for(PII v:LU[i][j]){
				printf("%d %d  ",v.F,v.S);
			}puts("");
		}puts("");*/
	}
	REP(j,C){
		stack<int> st;
		REP(i,R){
			while(st.size()&&d[st.top()][j]<d[i][j]){//look for first left value >=!
				st.pop();
			}
			if(st.size()){
				int k = st.top();
				if(i-k>=2){
					if(j){
						auto it = lower_bound(ALL(UL[i][j-1]),MP(k,0));
						if(it!=UL[i][j-1].end()&&it->F==k) UL[i][j].PB(MP(k,it->S));
						else UL[i][j].PB(MP(k,j));
					}
					else UL[i][j].PB(MP(k,j));
				}
			}
			st.push(i);
		}
		while(SZ(st))st.pop();
		for(int i=R-1;i>=0;i--){
			while(st.size()&&d[st.top()][j]<d[i][j]){//look for first right value >=!
				st.pop();
			}
			if(st.size()){
				int k = st.top();
				if(d[k][j]!=d[i][j] && k-i>=2){
					if(j){
						auto it = lower_bound(ALL(UL[k][j-1]),MP(i,0));
						if(it!=UL[k][j-1].end()&&it->F==i) UL[k][j].PB(MP(i,it->S));
						else UL[k][j].PB(MP(i,j));
					}
					else UL[k][j].PB(MP(i,j));
				}
			}
			st.push(i);
		}
		REP(i,R)sort(ALL(UL[i][j]));
	}
	int ans = 0;
	REPP(i,1,R-1){
		REPP(j,2,C){
			for(PII luv:LU[i][j]){
				for(int uli=UL[i+1][j-1].size()-1;uli>=0;uli--){
					PII ulv=UL[i+1][j-1][uli];
					if(ulv.F<luv.S-1)break;
					ans += (ulv.S <= luv.F+1);
				}
			}
		}
	}
	return ans;
}

• 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: 28 / 28