Submission #289124

#	Time	Username	Problem	Language	Result	Execution time	Memory
289124		amiratou	Rectangles (IOI19_rect)	C++14	50 / 100	5085 ms	123000 KiB

rect

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target ("avx2")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
typedef long long ll;
const int MX = 2505;

int cl[MX][MX]; // smallest row>i on same column containing one
int nxt[MX][MX]; // furthest col on same row tel que same close 
int cum[MX][MX]; // normal cum on columns
int gimme(int col,int a,int b){
	return cum[b][col] - (a?cum[a-1][col]:0);
}

ll count_rectangles(vector<vector<int> > a) {
	ll ans=0;
	int n=sz(a),m=sz(a[0]);
	if(n<=3){
		if(n<=2)return 0;
		for (int i = 1; i < m-1; ++i)
		{
			if(a[1][i]>=a[1][i-1])continue;
			int g=0;
			for (int j = i; j < m-1; ++j){
				if(a[1][j]>=a[0][j] || a[1][j]>=a[2][j])break;
				g=max(g,a[1][j]);
				ans+=((g<a[1][j+1]) && (g<a[1][i-1]));
			}
		}
		return ans;
	}
	bool f=1;
	for (int j = 0; j < m; ++j)
	{
		int last=-1;
		for (int i = n-1; i >= 0; i--){
			if(a[i][j]>1)f=0;
			if(a[i][j]){
				cl[i][j]=last,last=i;
				if((i+1) == cl[i][j])cl[i][j]=-1;
			}
			else cl[i][j]=-1;
		}
	}
	if(!f){
		for (int r1 = 1; r1 <= n-2; ++r1)
			for (int r2 = r1; r2 <= n-2; ++r2)
				for (int c1 = 1; c1 <= m-2; ++c1)
					for (int c2 = c1; c2 <= m-2; ++c2)
					{
						bool ok=1;
						for (int i = r1; i <= r2; ++i){
							for (int j = c1; j <= c2; ++j)
								if(a[i][j]>=a[i][c1-1] || a[i][j]>=a[i][c2+1] || a[i][j]>=a[r1-1][j] || a[i][j]>=a[r2+1][j]){ok=0;break;}
							if(!ok)break;
						}
						ans+=ok;
					}
		return ans;
	}
	for (int i = 0; i < n; ++i){
		for (int j = 0; j < m; )
		{
			if(cl[i][j]==-1){
				nxt[i][j]=-1,j++;
				continue;
			}
			int z=j;
			while(z<m && cl[i][z]==cl[i][j])
				z++;
			for (int A = j; A < z; ++A)
				nxt[i][A]=z;
			j=z;
		}
		for (int j = 0; j < m; ++j){
			cum[i][j]=(!a[i][j]);
			if(i)cum[i][j]+=cum[i-1][j];
		}
	}
	for (int i = 0; i < n-2; ++i)
		for (int j = 1; j < m-1; ++j)
			if(a[i][j] && cl[i][j]!=-1 && !gimme(j-1,i+1,cl[i][j]-1) && nxt[i][j]!=m && !gimme(nxt[i][j],i+1,cl[i][j]-1))
				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: 13 / 13
• Subtask 7: 0 / 28