Submission #340574

#	Time	Username	Problem	Language	Result	Execution time	Memory
340574		FlashGamezzz	Rectangles (IOI19_rect)	C++17	37 / 100	5086 ms	1048580 KiB

rect

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <unordered_set>
#include <vector>
#include <utility>
#include "rect.h"

using namespace std;

int n, m;
vector<vector<vector<bool> > > val, val2;
vector<vector<vector<int> > > bits;

int sum(int rs, int re, int c) {
	int sum = 0; c++;
	while (c > 0) {
		sum += bits[rs][re][c]; c -= c & (-c);
	}
	return sum;
}
void inc(int rs, int re, int c) {
	c++;
	while (c <= m) {
		bits[rs][re][c]++;
		c += c & (-c);
	}
}

long long count_rectangles(vector<vector<int> > a) {
	n = a.size(); m = a[0].size(); long long ans = 0;
	val.push_back(vector<vector<bool> >()); val2.push_back(vector<vector<bool> >());
	for (int r = 1; r < n-1; r++){
		val.push_back(vector<vector<bool> >()); val[r].push_back(vector<bool>());
		for (int cs = 1; cs < m-1; cs++){
			val[r].push_back(vector<bool>()); int maxv = 0;
			for (int t = 0; t < cs; t++){
				val[r][cs].push_back(false);
			}
			for (int ce = cs; ce < m-1; ce++){
				maxv = max(maxv, a[r][ce]);
				if (maxv < a[r][cs-1] && maxv < a[r][ce+1]){
					val[r][cs].push_back(true);
				} else {
					val[r][cs].push_back(false);
				}
			}
		}
	}
	bits.push_back(vector<vector<int> >());
	for (int rs = 1; rs < n-1; rs++){
		bits.push_back(vector<vector<int> >());
		for (int t = 0; t < rs; t++){
			bits[rs].push_back(vector<int>());
		}
		for (int re = rs; re < n-1; re++){
			bits[rs].push_back(vector<int>());
			for (int t = 0; t < m; t++){
				bits[rs][re].push_back(0);
			}
		}
	}
	for (int c = 1; c < m-1; c++){
		for (int rs = 1; rs < n-1; rs++){
			int maxv = 0;
			for (int re = rs; re < n-1; re++){
				maxv = max(maxv, a[re][c]);
				if (maxv < a[rs-1][c] && maxv < a[re+1][c]){
					inc(rs, re, c);
				}
			}
		}
	}
	for (int rs = 1; rs < n-1; rs++){
		for (int cs = 1; cs < m-1; cs++){
			for (int ce = cs; ce < m-1; ce++){
				for (int re = rs; re < n-1; re++){
					if (val[re][cs][ce]){
						bool valid = true;
						for (int i = cs; i <= ce; i++){
							if (!val2[i][rs][re]){
								valid = false;
							}
						}
						if (sum(rs, re, ce) - sum(rs, re, cs-1) >= ce-cs+1){
							ans++;
						}
					} else {
						break;
					}
				}
			}
		}
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:81:12: warning: variable 'valid' set but not used [-Wunused-but-set-variable]
   81 |       bool valid = true;
      |            ^~~~~

• 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