Submission #1021118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021118		Malix	Rectangles (IOI19_rect)	C++14	50 / 100	5020 ms	61728 KiB

rect

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

long long count_rectangles(std::vector<std::vector<int> > a) {
	bool flag=1;
	int n=a.size();
	int m=a[0].size();
	REP(i,0,n)REP(j,0,m)if(a[i][j]>1)flag=0;
if(flag){
	ll ans=0;
	queue<pi> pq;
	REP(i,1,n-1)REP(j,1,m-1){
		if(a[i][j]==1)continue;
		int c=0,d=0;
		while(j+c<m-1&&a[i][j+c]==0)c++;
		while(i+d<n-1&&a[i+d][j]==0)d++;
		bool g=1;
		REP(x,i,i+d){
			if(a[x][j-1]==0||a[x][j+c]==0)g=0;
		}
		REP(x,j,j+c){
			if(a[i-1][x]==0||a[i+d][x]==0)g=0;
		}
		pq.push({i,j});int k=0;
		while(!pq.empty()){
			int x=pq.front().F;
			int y=pq.front().S;
			pq.pop();
			if(a[x][y]==1)continue;
			a[x][y]=1;k++;
			if(x+1<n-1&&a[x+1][y]==0)pq.push({x+1,y});
			if(x-1>0&&a[x-1][y]==0)pq.push({x-1,y});
			if(y-1>0&&a[x][y-1]==0)pq.push({x,y-1});
			if(y+1<m-1&&a[x][y+1]==0)pq.push({x,y+1});
		}
		if(k==c*d&&g)ans++;
	}
	return ans;
}
	vii b(n,vi(m,0)),c(n,vi(m,0));
	ll ans=0;
	REP(i,1,n-1)REP(j,1,m-1){
		vii top(n,vi(m,0)),left(n,vi(m,0)),d(n,vi(m,0));
		REP(x,i,n-1)REP(y,j,m-1){
			top[x][y]=max(top[x-1][y],a[x][y]);
			left[x][y]=max(left[x][y-1],a[x][y]);
		}
		REP(y,j,m-1)d[i-1][y]=1;
		REP(x,i,n-1)REP(y,j,m-1)if(left[x][y]<a[x][j-1]&&left[x][y]<a[x][y+1]&&d[x-1][y])d[x][y]=1;
		REP(x,i,n-1){
			REP(y,j,m-1){
				if(top[x][y]>=a[i-1][y]||top[x][y]>=a[x+1][y])break;
				if(d[x][y]){
					ans++;//cerr<<i<<" "<<j<<" "<<x<<" "<<y<<"\n";
				}
			}
		}
		// if(i==n-2&&j==m-2){cout<<"\n";
		// 	REP(x,i,n-1){
		// 		REP(y,j,m-1)cout<<d[x][y]<<" ";
		// 	cout<<"\n";
		// 	}
		// }
	}
	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