Submission #596327

#	Time	Username	Problem	Language	Result	Execution time	Memory
596327		alireza_kaviani	Rectangles (IOI19_rect)	C++17	100 / 100	4153 ms	736340 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

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

#define X 		first
#define Y 		second
#define all(x)	(x).begin(), (x).end()
#define SZ(x)	int((x).size())
#define sep		' '

const int MAXN = 2510;
const int MOD = 1e9 + 7;

int n , m;
vector<pii> R[MAXN][MAXN] , D[MAXN][MAXN];

ll count_rectangles(vector<vector<int>> A) {
	n = SZ(A); m = SZ(A[0]);

	for(int i = 0 ; i < n ; i++){
		vector<int> stk;
		for(int j = 0 ; j < m ; j++){
			int flag = 1;
			while(SZ(stk) && A[i][j] >= A[i][stk.back()]){
				if(A[i][j] == A[i][stk.back()]) flag = 0;
				if(j - stk.back() > 1){
					R[i][stk.back() + 1].push_back({j - 1 , i});
				}
				stk.pop_back();
			}
			if(flag && SZ(stk) && j - stk.back() > 1){
				R[i][stk.back() + 1].push_back({j - 1 , i});
			}
			stk.push_back(j);
		}
	}

	for(int i = 0 ; i < m ; i++){
		vector<int> stk;
		for(int j = 0 ; j < n ; j++){
			int flag = 1;
			while(SZ(stk) && A[j][i] >= A[stk.back()][i]){
				if(A[j][i] == A[stk.back()][i])	flag = 0;
				if(j - stk.back() > 1){
					D[stk.back() + 1][i].push_back({j - 1 , i});
				}
				stk.pop_back();
			}
			if(flag && SZ(stk) && j - stk.back() > 1){
				D[stk.back() + 1][i].push_back({j - 1 , i});
			}
			stk.push_back(j);
		}
	}

	for(int i = n - 1 ; i >= 0 ; i--){
		for(int j = m - 1 ; j >= 0 ; j--){
			sort(all(R[i][j]));
			sort(all(D[i][j]));
			for(int k = 0 ; k < SZ(R[i][j]) ; k++){
				int ind = lower_bound(all(R[i + 1][j]) , R[i][j][k]) - R[i + 1][j].begin();
				if(ind == SZ(R[i + 1][j]) || R[i + 1][j][ind].X != R[i][j][k].X)	continue;
				R[i][j][k] = R[i + 1][j][ind];
			}
			for(int k = 0 ; k < SZ(D[i][j]) ; k++){
				int ind = lower_bound(all(D[i][j + 1]) , D[i][j][k]) - D[i][j + 1].begin();
				if(ind == SZ(D[i][j + 1]) || D[i][j + 1][ind].X != D[i][j][k].X)	continue;
				D[i][j][k] = D[i][j + 1][ind];
			}
		}
	}

	ll ans = 0;
	for(int i = 1 ; i + 1 < n ; i++){
		for(int j = 1 ; j + 1 < m ; j++){
			for(pii k : R[i][j]){
				for(pii l : D[i][j]){
					if(k.X <= l.Y && l.X <= k.Y){
						ans++;
					}
				}
			}
		}
	}

	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