Submission #1068159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068159		pcc	Rectangles (IOI19_rect)	C++17	37 / 100	5072 ms	62208 KiB

rect

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

#define ll long long

int N,M;

vector<vector<int>> row,col,arr;

ll calc(int sr,int sc){
	//cerr<<sr<<','<<sc<<endl;
	for(int i = 0;i<N;i++)for(int j = 0;j<M;j++)col[i][j] = row[i][j] = 0;
	ll re = 0;

	for(int i = 0;i<N;i++)row[i][sc] = col[i][sc] = -1;
	for(int i = 0;i<M;i++)col[sr][i] = row[sr][i] = -1;

	for(int i = sr+1;i+1<N;i++){
		for(int j = sc+1;j+1<M;j++){
			row[i][j] = max(row[i][j-1],arr[i][j]);
			col[i][j] = max(col[i-1][j],arr[i][j]);
		}
	}

	/*
	cerr<<sr+1<<' '<<sc+1<<":"<<endl;
	for(int i = sr;i+1<N;i++){
		for(int j = sc;j+1<M;j++)cerr<<row[i][j];cerr<<endl;
	}cerr<<endl;
	for(int i = sr;i+1<N;i++){
		for(int j = sc;j+1<M;j++)cerr<<col[i][j];cerr<<endl;
	}
	*/

	for(int i = sr+1;i+1<N;i++){
		for(int j = sc+1;j+1<M;j++){
			if(!row[i-1][j]||row[i][j]>=min(arr[i][sc],arr[i][j+1]))row[i][j] = 0;
			else row[i][j] = -1;
			if(!col[i][j-1]||col[i][j]>=min(arr[sr][j],arr[i+1][j]))col[i][j] = 0;
			else col[i][j] =- 1;
			if(row[i][j] == -1&&col[i][j] == -1){
				//cerr<<"FOUND: "<<sr+1<<' '<<sc+1<<' '<<i<<' '<<j<<endl;
				re++;
			}
		}
	}

	/*
	cerr<<sr+1<<' '<<sc+1<<":"<<endl;
	for(int i = sr;i+1<N;i++){
		for(int j = sc;j+1<M;j++)cerr<<row[i][j];cerr<<endl;
	}cerr<<endl;
	for(int i = sr;i+1<N;i++){
		for(int j = sc;j+1<M;j++)cerr<<col[i][j];cerr<<endl;
	}
	*/

	return re;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	N = a.size(),M = a[0].size();
	row = col = vector<vector<int>>(N,vector<int>(M,0));
	arr = a;
	ll ans = 0;
	for(int i = 0;i+1<N;i++){
		for(int j = 0;j+1<M;j++){
			ans += calc(i,j);
		}
	}
	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