Submission #416377

#	Time	Username	Problem	Language	Result	Execution time	Memory
416377		cfalas	Rectangles (IOI19_rect)	C++14	50 / 100	5082 ms	149916 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)
#define len(x) ((int)x.size())

vector<ii> vert[2500], hor[2500];
vector<vi> a;
vector<pair<ii, ii> > horside;

void find_pairs(){
	// vert pairs
	FORi(i,1,len(a[0])-1){
		// i-th column
		FOR(j, len(a)-1){
			int maxa = a[j+1][i];
			FORi(k,j+2, len(a)){
				if(maxa>=a[j][i]) break;
				if(maxa>=a[k][i]) continue;
				vert[i].push_back({j,k});
				maxa = max(maxa, a[k][i]);
			}
		}
	}
	// horizontal pairs
	FORi(i,1,len(a)-1){
		// i-th column
		FOR(j,len(a[0])-1){
			int maxa = a[i][j+1];
			FORi(k,j+2, len(a[0])){
				if(maxa>=a[i][j]) break;
				if(maxa>=a[i][k]) continue;
				hor[i].push_back({j,k});
				maxa = max(maxa, a[i][k]);
			}
		}
	}
}

void hor_sides(){
	// find sides
	FOR(i, len(a)){
		FOA(v, hor[i]){
			int last_ok = i;
			FORi(j, i, len(a)){
				if(binary_search(hor[j].begin(), hor[j].end(), v)) last_ok = j;
				else break;
			}
			horside.push_back({{v.F+1, v.S-1}, {i, last_ok}});
		}
	}
	sort(horside.begin(), horside.end());

}

ll find_ans(){
	int ans=0;
	FOR(i, len(a[0])){
		FOA(v, vert[i]){
			FORi(j, i, len(a[0])){
				if(binary_search(vert[j].begin(), vert[j].end(), v)){
					auto targ = mp(mp(i,j), mp(v.F+1,v.S-1));
					auto it = lower_bound(horside.begin(), horside.end(), targ);
					if(it==horside.end()) break;
					if((*it).F.F!=targ.F.F) break;
					if((*it).F==targ.F && (*it).S.F==targ.S.F) ans++;
					/*
					else if((*it).F!=targ.F){
						j = (*it).F.S-1;
					}*/
				}
				else break;
			}
		}
	}
	return ans;
}

long long count_rectangles(std::vector<std::vector<int> > b) {
	a = b;

	find_pairs();
#ifdef LOCAL
	FOR(i,len(a[0])) FOA(v, vert[i]) cout<<i<<" "<<v.F<<" "<<v.S<<endl;
	cout<<endl;
	FOR(i,len(a)) FOA(v, hor[i]) cout<<i<<" "<<v.F<<" "<<v.S<<endl;
	cout<<endl;
#endif

	hor_sides();

	cerr<<len(horside)<<endl;


	return find_ans();
}

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