Submission #583542

#	Time	Username	Problem	Language	Result	Execution time	Memory
583542		Lucpp	Rectangles (IOI19_rect)	C++17	72 / 100	5127 ms	710776 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int)(x).size())
 
long long count_rectangles(vector<vector<int>> a) {
	int n = sz(a), m = sz(a[0]);
	vector<vector<int>> r1(n, vector<int>(m, -1)), r2(n, vector<int>(m, -1));
	stack<pair<int, int>> st;
	for(int i = 1; i < n-1; i++){
		while(!st.empty()) st.pop();
		st.emplace(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<int>> c1(n, vector<int>(m, -1)), c2(n, vector<int>(m, -1));
	for(int j = 1; j < m-1; j++){
		while(!st.empty()) st.pop();
		st.emplace(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);
		}
	}
	int mx = max(n, m);
	vector<bool> valid;
	vector<tuple<int, int, int>> byI, byJ;
	unordered_set<long long> noDupl;
	vector<pair<int, int>> goodI, goodJ;
	int q = 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];
				goodJ.emplace_back(x, j);
				goodI.emplace_back(y, i);
				long long t = (long long)x*(mx*mx)+y;
				if(noDupl.count(t)) continue;
				noDupl.insert(t);
				valid.push_back(true);
				byI.emplace_back(x, y, q);
				byJ.emplace_back(y, x, q);
				q++;
			}
		}
	}
	sort(byI.begin(), byI.end());
	sort(byJ.begin(), byJ.end());
	sort(goodI.begin(), goodI.end());
	sort(goodJ.begin(), goodJ.end());
	int g = 0, p = 0;
	vector<int> v;
	for(int id = 1; id < mx*mx; id++){
		int last = -1;
		v.clear();
		for(; g < sz(goodI); g++){
			auto [id2, j] = goodJ[g];
			if(id != id2) break;
			if(j != last) v.push_back(j);
			last = j;
		}
		int k = 0;
		for(;p < sz(byI); p++){
			auto [id2, id3, ind] = byI[p];
			if(id != id2) break;
			int L = id3/mx, R = id3%mx;
			while(k < sz(v) && v[k] < L) k++;
			if(k == sz(v) || v[k] != L) valid[ind] = false;
			else if(k+R-L >= sz(v) || v[k+R-L] != R) valid[ind] = false;
		}
	}
	g = 0, p = 0;
	for(int id = 1; id < mx*mx; id++){
		int last = -1;
		v.clear();
		for(; g < sz(goodI); g++){
			auto [id2, j] = goodI[g];
			if(id != id2) break;
			if(j != last) v.push_back(j);
			last = j;
		}
		int k = 0;
		for(;p < sz(byI); p++){
			auto [id2, id3, ind] = byJ[p];
			if(id != id2) break;
			int L = id3/mx, R = id3%mx;
			while(k < sz(v) && v[k] < L) k++;
			if(k == sz(v) || v[k] != L) valid[ind] = false;
			else if(k+R-L >= sz(v) || v[k+R-L] != R) valid[ind] = false;
		}
	}
	int ans = 0;
	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: 0 / 28