제출 #340577

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340577		FlashGamezzz	Rectangles (IOI19_rect)	C++17	37 / 100	5100 ms	605064 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;
vector<vector<vector<short> > > bits;

short sum(short rs, short re, short c) {
	short sum = 0; c++;
	while (c > 0) {
		sum += bits[rs][re][c]; c -= c & (-c);
	}
	return sum;
}
void inc(short rs, short re, short 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> >());
	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<short> >());
	for (int rs = 1; rs < n-1; rs++){
		bits.push_back(vector<vector<short> >());
		for (int t = 0; t < rs; t++){
			bits[rs].push_back(vector<short>());
		}
		for (int re = rs; re < n-1; re++){
			bits[rs].push_back(vector<short>());
			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]){
						if (sum(rs, re, ce) - sum(rs, re, cs-1) >= ce-cs+1){
							ans++;
						}
					} else {
						break;
					}
				}
			}
		}
	}
	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