Submission #288822

#	Time	Username	Problem	Language	Result	Execution time	Memory
288822		amiratou	Rectangles (IOI19_rect)	C++14	13 / 100	356 ms	123000 KiB

rect

#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]);
	for (int j = 0; j < m; ++j)
	{
		int last=-1;
		for (int i = n-1; i >= 0; i--){
			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;
		}
	}
	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: 0 / 8
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 22
• Subtask 5: 0 / 10
• Subtask 6: 13 / 13
• Subtask 7: 0 / 28