Submission #1206327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206327		thelegendary08	Rectangles (IOI19_rect)	C++17	37 / 100	2488 ms	1114112 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define pb push_back
#define vi vector<int>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define dout(x) cout<<x<<' '<<#x<<'\n';
#define pii pair<int,int>
#define vpii vector<pii>
#define vb vector<bool>
#define mp make_pair
using namespace std;
int n,m;
vector<vector<signed>>grid;
vpii adj(pii a){
	int x = a.first; int y = a.second;
	vpii ret;
	if(x > 0 && grid[x-1][y] == 0){
		ret.pb(mp(x-1, y));
	}
	if(y > 0 && grid[x][y-1] == 0){
		ret.pb(mp(x, y-1));
	}
	if(x < n-1 && grid[x+1][y] == 0){
		ret.pb(mp(x+1, y));
	}
	if(y < m-1 && grid[x][y+1] == 0){
		ret.pb(mp(x, y+1));
	}
	return ret;
}
long long int count_rectangles(std::vector<std::vector<signed> > a) {
	grid = a;
	
	n = a.size(); m = a[0].size();
	//subtask 1
	//i * m + j
	vector<vector<bool>>mat(n*m, vb(n * m));
	f0r(i, n){
		f0r(j,m){
			for(int k = i+1; k < n; k++){
				if(a[i][j] <= a[k][j]){
					mat[i*m+j][k*m+j] = 1;
					mat[k*m+j][i*m+j] = 1;
					break;
				}
			}
			for(int k = i-1; k >= 0; k--){
				if(a[i][j] <= a[k][j]){
					mat[i*m+j][k*m+j] = 1;
					mat[k*m+j][i*m+j] = 1;
					break;
				}
			}
			for(int k = j + 1; k<m; k++){
				if(a[i][j] <= a[i][k]){
					mat[i*m+j][i*m+k] = 1;
					mat[i*m+k][i*m+j]=1;
					break;
				}
			}
			for(int k = j-1; k>=0; k--){
				if(a[i][j] <= a[i][k]){
					mat[i*m+j][i*m+k] = 1;
					mat[i*m+k][i*m+j]=1;
					break;
				}
			}
		}
	}
	//fixj[k][l][i], make prefix sum
	
	vector<vector<vector<int>>>fixj(m, vector<vi>(m, vi(n+1)));
	f0r(k,m){
		FOR(l, k+2, m){
			for(int z = 1; z <= n; z++){
				if(mat[(z-1)*m+k][(z-1)*m+l]){
					fixj[k][l][z] = fixj[k][l][z-1] + 1;
				}
				else fixj[k][l][z] = fixj[k][l][z-1];
			}
		}
	}
	
	vector<vector<vector<int>>>fixi(n, vector<vi>(n, vi(m+1)));
	f0r(i, n){
		FOR(j, i+2, n){
			for(int z = 1; z <= m; z++){
				if(mat[i*m+z-1][j*m+z-1])fixi[i][j][z] = fixi[i][j][z-1] + 1;
				else fixi[i][j][z] = fixi[i][j][z-1];
			}
		}
	}
	
	int ans = 0;
	
	f0r(i, n){
		FOR(j, i+2, n){
			f0r(k, m){
				FOR(l, k+2, m){
					bool ok = 1;
					/*
					for(int z = i+1; z < j; z++){
						if(!mat[z*m+k][z*m+l])ok = 0;
					}
					for(int z = k+1; z < l; z++){
						if(!mat[i*m+z][j*m+z])ok = 0;
					}
					*/
					//from i+1 to j-1
					if(fixj[k][l][j] - fixj[k][l][i+1] != j-i-1)ok = 0;
					//from k+1 to l-1
					if(fixi[i][j][l] - fixi[i][j][k+1] != l-k-1)ok = 0;
					if(ok)ans++;
				}
			}
		}
	}
	
	return ans;
	//subtask 5
	/*
	if(n < 3)return 0;
	else{
		int ans = 0;
		vi v;
		f0r(i,m){
			if(a[0][i] > a[1][i] && a[1][i] < a[2][i])v.pb(1);
			else v.pb(0);
		}
		vi ps(m+1);
		FOR(i, 1, m+1){
			ps[i] = ps[i-1] + v[i-1];
		}
		f0r(i, m){
			// dout(i);
			int run = -1;
			FOR(j, i+1, m){
				if(run < a[1][j]){
					run = a[1][j];
					// dout(run);
					if(j != i + 1 && ps[j] - ps[i+1] == (j - i - 1))ans++;
				}
				if(a[1][j] >= a[1][i]){
					break;
				}
			}
		}
		
		return ans;
	}
	*/
	//subtask 6
	/*
	vector<vector<bool>>vis(n, vector<bool>(m));
	int ans = 0;
	f0r(i,n){
		f0r(j,m){
			if(a[i][j] == 0 && !vis[i][j]){
				
				queue<pii>q;
				int tot = 1;
				q.push(mp(i,j));
				// cout<<i<<' '<<j<<'\n';
				vis[i][j] = 1;
				int mnx = i; int mxx = i; int mny = j; int mxy = j;
				while(!q.empty()){
					pii node = q.front(); q.pop();
					for(auto u : adj(node)){
						if(vis[u.first][u.second])continue;
						// cout<<u.first<<' '<<u.second<<'\n';
						mnx = min(mnx, u.first);
						mxx = max(mxx, u.first);
						mny = min(mny, u.second);
						mxy = max(mxy, u.second);
						tot++;
						vis[u.first][u.second] = 1;
						q.push(mp(u.first, u.second));
					}
				}
				int area = (mxx - mnx + 1) * (mxy - mny + 1);
				// cout<<"FINAL"<<' '<<area<<' '<<tot<<'\n';
				if(mnx > 0 && mxx < n-1 && mny > 0 && mxy < m-1 && area == tot)ans++;
				
			}
		}
	}
	return ans;
	*/
}

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