Submission #416165

#	Time	Username	Problem	Language	Result	Execution time	Memory
416165		cfalas	Rectangles (IOI19_rect)	C++14	0 / 100	144 ms	89624 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<ll, ll> 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())

long long count_rectangles(std::vector<std::vector<int> > a) {
	long long ans=0;
	// vert pairs
	vector<ii> vert[2500], hor[2500];
	FORi(i,1,len(a[0])-1){
		// i-th column
		FOR(j, len(a)-2){
			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]);
			}
			//check i..i+2
		}
	}
	// horizontal pairs
	FORi(i,1,len(a)-1){
		// i-th column
		FOR(j,len(a[0])-2){
			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[k][i]);
			}
			//check i..i+2
		}
	}
#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

	// find sides
	vector<pair<ii, ii> > horside;
	FOR(i, len(a)){
		FOA(v, hor[i]){
			FORi(j, i, len(a)){
				if(binary_search(hor[j].begin(), hor[j].end(), v))
					horside.push_back({{v.F+1, v.S-1}, {i, j}});
				else break;
			}
		}
	}

	vector<pair<ii, ii> > verside;
	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))
					verside.push_back({{i, j}, {v.F+1, v.S-1}});
				else break;
			}
		}
	}
	sort(horside.begin(), horside.end());

	FOA(v, verside){
		if(binary_search(horside.begin(), horside.end(), v)) ans++;
	}

#ifdef LOCAL
	FOA(v, horside) cout<<v.F.F<<" "<<v.F.S<<" "<<v.S.F<<" "<<v.S.S<<endl;
	cout<<endl;
	FOA(v, verside) cout<<v.F.F<<" "<<v.F.S<<" "<<v.S.F<<" "<<v.S.S<<endl;
#endif

	// consider each starting point
	return ans;
}

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