Submission #1021540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021540		vjudge1	Rectangles (IOI19_rect)	C++17	50 / 100	1359 ms	61704 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define pii pair<int,int>
#define fi first
#define se second
#define rep(a,b,c) for(int a=b; a<c; a++)
#define pb push_back

using namespace std;

const int moves[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

ll count_rectangles(vector<vector<int>> a) {
	ll ans=0, n=a.size(), m=a[0].size();
	if(max(n,m)>200 && (n>3)){
	int x, y, z, b[4];
	queue<int> q;
	rep(i,0,n){
		rep(j,0,m){
			if(a[i][j]) continue;
			q.push(i);
			q.push(j);
			z=0;
			b[1]=0;
			b[0]=1e9;
			b[3]=0;
			b[2]=1e9;
			while(q.size()){
				x=q.front();q.pop();
				y=q.front();q.pop();
				if(a[x][y]) continue;
				a[x][y]=1;
				if(!x || !y || x+1==n || y+1==m) z=-1e9;
				b[1]=max(b[1],x);
				b[0]=min(b[0],x);
				b[3]=max(b[3],y);
				b[2]=min(b[2],y);
				z++;
				rep(k,0,4){
					x+=moves[k][0];
					y+=moves[k][1];
					if(0<=x && x<n && 0<=y && y<m && !a[x][y]){
						q.push(x);
						q.push(y);
					}
					x-=moves[k][0];
					y-=moves[k][1];
				}
			}
			if((b[1]-b[0]+1)*(b[3]-b[2]+1)==z) ans++; 
		}
	}
	return ans;

	}
	rep(ri,1,n-1){
		rep(ci,1,m-1){
			rep(rf,ri,n-1){
				rep(cf,ci,m-1){
					bool rect=1;
					rep(i,ri,rf+1){
						rep(j,ci,cf+1){
					if(a[i][j]>=a[ri-1][j] || a[i][j]>=a[rf+1][j] || a[i][j]>=a[i][ci-1] || a[i][j]>=a[i][cf+1]){
								rect=false;
								break;
							}
						}
						if(!rect) break;
					}
					ans+=rect;
				}
			}
		}
	}
	return 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