Submission #583818

#	Time	Username	Problem	Language	Result	Execution time	Memory
583818		Lucpp	Rectangles (IOI19_rect)	C++17	100 / 100	3262 ms	654716 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
typedef long long ll;
 
vector<vector<int>> fen;
void add(bool b, int i, int x){
	for(i++; i < sz(fen[0]); i+=i&-i) fen[b][i] += x;
}
int qry(bool b, int i){
	int ans = 0;
	for(i++; i > 0; i-=i&-i) ans += fen[b][i];
	return ans;
}
int qry(bool b, int i, int j){
	if(i > 0) return qry(b, j)-qry(b, i-1);
	else return qry(b, j);
}

long long count_rectangles(vector<vector<int>> a) {
	int n = sz(a), m = sz(a[0]);
	vector<vector<short>> r1(n, vector<short>(m, -1)), r2(n, vector<short>(m, -1));
	for(int i = 1; i < n-1; i++){
		stack<pair<int, int>> st({{a[i][0], 0}});
		for(int j = 1; j < m; j++){
			while(!st.empty() && a[i][j] > st.top().first){
				auto [h, k] = st.top();
				st.pop();
				r2[i][k] = j-1;
			}
			if(!st.empty()) {
				if(st.top().first > a[i][j]) r1[i][j] = st.top().second+1;
				else r1[i][j] = r1[i][st.top().second];
			}
			st.emplace(a[i][j], j);
		}
	}
	vector<vector<short>> c1(n, vector<short>(m, -1)), c2(n, vector<short>(m, -1));
	for(int j = 1; j < m-1; j++){
		stack<pair<int, int>> st({{a[0][j], 0}});
		for(int i = 1; i < n; i++){
			while(!st.empty() && a[i][j] > st.top().first){
				auto [h, k] = st.top(); st.pop();
				c2[k][j] = i-1;
			}
			if(!st.empty()){
				if(st.top().first > a[i][j]) c1[i][j] = st.top().second+1;
				else c1[i][j] = c1[st.top().second][j];
			}
			st.emplace(a[i][j], i);
		}
	}
	a.clear();
	a.shrink_to_fit();
	int mx = max(n, m);
	fen.resize(2, vector<int>(mx+1));
	vector<bool> valid;
	vector<vector<tuple<bool, short, short, int>>> queries(mx*mx);
	int q = 0, ans = 0;
	for(int i = 1; i < n-1; i++){
		for(int j = 1; j < m-1; j++){
			// cerr << "\n" << i << " " << j << " " << r1[i][j] << " " << r2[i][j] << " " << c1[i][j] << " " << c2[i][j] << "\n";
			if(r1[i][j] != -1 && r2[i][j] != -1 && c1[i][j] != -1 && c2[i][j] != -1){
				int x = c1[i][j]*mx + c2[i][j], y = r1[i][j]*mx + r2[i][j];
				queries[x].emplace_back(0, j, 0, -1);
				queries[y].emplace_back(1, i, 0, -1);
				valid.push_back(true);
				queries[x].emplace_back(0, r1[i][j], r2[i][j], q);
				queries[y].emplace_back(1, c1[i][j], c2[i][j], q);
				q++;
			}
		}
	}
	vector<vector<bool>> used(2, vector<bool>(mx));
	vector<vector<bool>> usedQ(2, vector<bool>(mx*mx));
	vector<pair<bool, short>> undo;
	vector<tuple<bool, short, short, int>> qries;
	for(int id = 1; id < mx*mx; id++){
		for(auto [b, i, j, ind] : queries[id]){
			if(ind == -1){
				if(!used[b][i]) add(b, i, 1), undo.emplace_back(b, i);
				used[b][i] = true;
			}
			else qries.emplace_back(b, i, j, ind);
		}
		for(auto [b, i, j, ind] : qries){
			if(usedQ[b][i*mx+j] || qry(b, i, j) != j-i+1) valid[ind] = false;
			usedQ[b][i*mx+j] = true;
		}
		for(auto [b, i, j, ind] : qries) usedQ[b][i*mx+j] = false;
		for(auto [b, i] : undo){
			add(b, i, -1);
			used[b][i] = false;
		}
		qries.clear();
		undo.clear();
	}

	for(bool b : valid) ans += b;
	return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 13 / 13
• Subtask 7: 28 / 28