Submission #535963

#	Time	Username	Problem	Language	Result	Execution time	Memory
535963		jamezzz	Rectangles (IOI19_rect)	C++17	100 / 100	2406 ms	737872 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pf printf
#define pb push_back
#define INF 1023456789
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> ii;

#define maxn 2505

int n,m,ft[maxn+5];
vector<ii> h[maxn][maxn],v[maxn][maxn];

void up(int x,int v){
	++x;
	while(x<=maxn)ft[x]+=v,x+=x&-x;
}

int qry(int x,int y){
	++y;int res=0;
	while(y)res+=ft[y],y-=y&-y;
	while(x)res-=ft[x],x-=x&-x;
	return res;
}

ll count_rectangles(vector<vector<int>> a){
	n=sz(a);m=sz(a[0]);
	if(min(n,m)<=2)return 0;
	for(int i=0;i<n;++i){
		vector<ii> s;
		s.pb({INF,-1});
		for(int j=0;j<m;++j){
			while(s.back().fi<a[i][j]){
				if(j-s.back().se>1)h[i][s.back().se+1].pb({j-1,i});
				while(sz(s)>=2&&s[sz(s)-1].fi==s[sz(s)-2].fi)s.pop_back();
				s.pop_back();
			}
			if(j-s.back().se>1)h[i][s.back().se+1].pb({j-1,i});
			s.pb({a[i][j],j});
		}
	}
	for(int j=0;j<m;++j){
		vector<ii> s;
		s.pb({INF,-1});
		for(int i=0;i<n;++i){
			while(s.back().fi<a[i][j]){
				if(i-s.back().se>1)v[s.back().se+1][j].pb({i-1,j});
				while(sz(s)>=2&&s[sz(s)-1].fi==s[sz(s)-2].fi)s.pop_back();
				s.pop_back();
			}
			if(i-s.back().se>1)v[s.back().se+1][j].pb({i-1,j});
			s.pb({a[i][j],i});
		}
	}
	for(int i=n-2;i>0;--i){
		for(int j=m-2;j>0;--j){
			for(ii &p:h[i][j]){
				auto it=lower_bound(all(h[i+1][j]),p);
				if(it!=h[i+1][j].end()&&(*it).fi==p.fi){
					p.se=(*it).se;
				}
			}
			for(ii &p:v[i][j]){
				auto it=lower_bound(all(v[i][j+1]),p);
				if(it!=v[i][j+1].end()&&(*it).fi==p.fi){
					p.se=(*it).se;
				}
			}
		}
	}
	for(int i=0;i<n;++i)for(int j=0;j<m;++j)for(ii &p:h[i][j])swap(p.fi,p.se);
	ll ans=0;
	for(int i=1;i<n-1;++i){
		for(int j=1;j<m-1;++j){
			//pf("h[%d][%d]:\n",i,j);
			//for(ii pr:h[i][j])pf("%d %d %d %d\n",i,j,pr.fi,pr.se);
			//pf("v[%d][%d]:\n",i,j);
			//for(ii pr:v[i][j])pf("%d %d %d %d\n",i,j,pr.fi,pr.se);
			sort(all(h[i][j]),[](ii &a,ii &b){return a.se<b.se;});
			sort(all(v[i][j]),[](ii &a,ii &b){return a.se<b.se;});
			int curh=0,curv=0,mxh=sz(h[i][j]),mxv=sz(v[i][j]);
			while(curv!=mxv){
				while(curh!=mxh&&h[i][j][curh].se<=v[i][j][curv].se){
					up(h[i][j][curh++].fi,1);
				}
				ans+=qry(v[i][j][curv++].fi,maxn-1);
			}
			for(int k=0;k<curh;++k)up(h[i][j][k].fi,-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