제출 #297646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
297646		amoo_safar	Rectangles (IOI19_rect)	C++17	100 / 100	3479 ms	407520 KiB

rect

#include "rect.h"

#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int N = 2510;

int n, m;
vector< vector<int> > a;
vector<pii> segC[N];
vector<int> segR[N][N];
vector<int> eqr[N];

void PrepCol(int j){
	vector<int> A(n);
	for(int i = 0; i < n; i++) A[i] = a[i][j];
	stack<int> st;
	
	for(int i = 0; i < n; i++){
		while(!st.empty() && A[st.top()] < A[i]) st.pop();
		if(!st.empty() && i - st.top() > 1)
			segC[j].pb({st.top(), i});
		st.push(i);
	}
	while(!st.empty()) st.pop();
	for(int i = n - 1; i >= 0; i--){
		while(!st.empty() && A[st.top()] < A[i]) st.pop();
		if(!st.empty() && st.top() - i > 1)
			segC[j].pb({i, st.top()});
		st.push(i);
	}
	sort(all(segC[j]));
	segC[j].resize(unique(all(segC[j])) - segC[j].begin());
	for(int i = 0; i + 1 < (int) segC[j].size(); i++){
		if(segC[j][i].F < segC[j][i + 1].F && segC[j][i + 1].F < segC[j][i].S && segC[j][i].S < segC[j][i + 1].S)
			assert(0);
	}
	//	assert((segC[j][i].S <= segC[j][i + 1].S) || );
	/*
	cerr << "col : " << j << '\n';
	for(auto X : seg[j]) cerr << X.F << ' ' << X.S << '\n';
	cerr << '\n';
	*/
}

void PrepRow(int i){
	vector<int> A(m);
	for(int j = 0; j < m; j++) A[j] = a[i][j];
	stack<int> st;
	vector<pii> seg;

	for(int j = 0; j < m; j++){
		while(!st.empty() && A[st.top()] < A[j]) st.pop();
		if(!st.empty() && j - st.top() > 1)
			seg.pb({st.top(), j});
		st.push(j);
	}
	while(!st.empty()) st.pop();
	for(int j = m - 1; j >= 0; j--){
		while(!st.empty() && A[st.top()] < A[j]) st.pop();
		if(!st.empty() && st.top() - j > 1)
			seg.pb({j, st.top()});
		st.push(j);
	}
	sort(all(seg));
	seg.resize(unique(all(seg)) - seg.begin());
	/*
	for(int i = 0; i + 1 < (int) seg.size(); i++)
		assert(seg[i].S <= seg[i + 1].S);
	*/
	for(auto X : seg) segR[X.F][X.S].pb(i);
	/*
	cerr << "col : " << j << '\n';
	for(auto X : seg[j]) cerr << X.F << ' ' << X.S << '\n';
	cerr << '\n';
	*/
}

vector<int> ev[N];

vector<pii> Fen;
int fen[N][N];
void Add(int fn, int idx, int d){
	idx ++;
	for(; idx < N - 1; idx += idx & (-idx))
		fen[fn][idx] += d;
	fen[fn][N - 1] += d;
}
int Get(int fn, int idx){
	int res = fen[fn][N - 1];
	for(; idx; idx -= idx & (-idx))
		res -= fen[fn][idx];
	return res;
}
void Add(pii x){
	Add(x.S, x.F, +1);
	//Fen.pb(x);
}
void Rem(pii x){
	Add(x.S, x.F, -1);
	/*
	for(int i = 0; i + 1 < (int) Fen.size(); i++){
		if(Fen[i] == x) swap(Fen[i], Fen[i + 1]);
	}
	if(Fen.back() == x)
		Fen.pop_back();
	*/
}
int Get(pii x){
	return Get(x.S, x.F);

	int res = 0;
	for(auto &y : Fen){
		if(x.F <= y.F && y.S == x.S)
			res ++;
	}
	return res;
}

ll count_rectangles(vector<vector<int> > _a){
	a = _a;
	n = a.size();
	m = a[0].size();
	cerr << "! " << n << ' ' << m << '\n';
	for(int i = 1; i < m - 1; i++) PrepCol(i);
	for(int i = 1; i < n - 1; i++) PrepRow(i);

	//
	int cnt, idx;
	for(int j = m - 1; j >= 1; j--){
		cnt = segC[j].size();
		eqr[j].resize(cnt);
		for(int i = 0; i < cnt; i++){
			idx = lower_bound(all(segC[j + 1]), segC[j][i]) - segC[j + 1].begin();
			eqr[j][i] = (idx == (int)segC[j + 1].size() || segC[j + 1][idx] != segC[j][i] ? 1 : eqr[j + 1][idx] + 1);
			//cerr << segC[j][i].F << ", " << segC[j][i].S << " -> " << eqr[j][i] << '\n';
		}
	}
	ll ans = 0;
	for(int j1 = 1; j1 < m - 1; j1 ++){
		for(int j2 = j1; j2 < m - 1; j2 ++)
			ev[j2].clear();
		Fen.clear();
		cnt = segC[j1].size();
		for(int i = 0; i < cnt; i++){
			Add(segC[j1][i]);
			ev[j1 + eqr[j1][i] - 1].pb(i);
		}

		for(int j2 = j1; j2 < m - 1; j2 ++){
			vector<int> &R = segR[j1 - 1][j2 + 1];
			//R.pb(-1);
			int con = 1;
			for(int i = 0; i < (int) R.size(); i++){
				if(i == 0) con = 1;
				else if(R[i] == R[i - 1] + 1) con ++;
				else {
					//ans += Get({R[i - 1] - con, R[i - 1] + 1});
					con = 1;
				}
				ans += Get({R[i] - con, R[i] + 1});
			}

			for(auto id : ev[j2])
				Rem(segC[j1][id]);
		}
		assert(Fen.empty());
	}
	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