제출 #1342676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1342676		Jawad_Akbar_JJ	Rectangles (IOI19_rect)	C++20	100 / 100	1610 ms	440120 KiB

rect

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;
const int N = 2505;
vector<array<short, 3>> vec[N][N];
short lst[2][N][N], fst[2][N][N], ft[N];

void Add(int i, int v){
	for (; i < N; i += i & -i)
		ft[i] += v;
}

int get(int i, int ans = 0){
	for (; i; i -= i & -i)
		ans += ft[i];
	return ans;
}

void upd(int t, int l, int r, int j){
	if (r - l <= 1)
		return;

	if (lst[t][l][r] != j)
		fst[t][l][r] = j;
	lst[t][l][r] = j + 1;

	if (t == 0)
		vec[r-1][j].push_back({lst[t][l][r] - fst[t][l][r], r - l - 1, 1});
	else
		vec[j][r-1].push_back({r - l - 1, lst[t][l][r] - fst[t][l][r], 0});
}

long long count_rectangles(vector<vector<int>> A){
	int n = A.size(), m = A[0].size();
	
	for (int j=1;j<m-1;j++){
		vector<int> v = {0};
		for (int i=1;i<n;i++){
			while (v.size() > 0 and A[v.back()][j] < A[i][j]){
				upd(0, v.back(), i, j);
				v.pop_back();
			}
			if (v.size() > 0 and A[v.back()][j] >= A[i][j])
				upd(0, v.back(), i, j);
			if (v.size() > 0 and A[v.back()][j] == A[i][j])
				v.pop_back();
			v.push_back(i);
		}
	}

	for (int i=1;i<n-1;i++){
		vector<int> v = {0};
		for (int j=1;j<m;j++){
			while (v.size() > 0 and A[i][v.back()] < A[i][j]){
				upd(1, v.back(), j, i);
				v.pop_back();
			}

			if (v.size() > 0 and A[i][v.back()] >= A[i][j])
				upd(1, v.back(), j, i);
			if (v.size() > 0 and A[i][v.back()] == A[i][j])
				v.pop_back();
			v.push_back(j);
		}
	}

	long long Ans = 0;
	for (int i=1;i<n;i++){
		for (int j=1;j<m;j++){
			for (int k=0;k<vec[i][j].size();k++)
				vec[i][j][k][1] *= -1;
			sort(rbegin(vec[i][j]), rend(vec[i][j]));
			for (int k=0;k<vec[i][j].size();k++)
				vec[i][j][k][1] *= -1;


			for (auto [a, b, t] : vec[i][j]){
				if (t == 1)
					Add(b, 1);
				else
					Ans += get(b);
			}
			for (auto [a, b, t] : vec[i][j]){
				if (t == 1)
					Add(b, -1);
			}
		}
	}
	return Ans;
}

컴파일 시 표준 에러 (stderr) 메시지

rect.cpp: In function 'void upd(int, int, int, int)':
rect.cpp:31:53: warning: narrowing conversion of '(((int)lst[t][l][r]) - ((int)fst[t][l][r]))' from 'int' to 'short int' [-Wnarrowing]
   31 |                 vec[r-1][j].push_back({lst[t][l][r] - fst[t][l][r], r - l - 1, 1});
      |                                        ~~~~~~~~~~~~~^~~~~~~~~~~~~~
rect.cpp:31:75: warning: narrowing conversion of '((r - l) - 1)' from 'int' to 'short int' [-Wnarrowing]
   31 |                 vec[r-1][j].push_back({lst[t][l][r] - fst[t][l][r], r - l - 1, 1});
      |                                                                     ~~~~~~^~~
rect.cpp:33:46: warning: narrowing conversion of '((r - l) - 1)' from 'int' to 'short int' [-Wnarrowing]
   33 |                 vec[j][r-1].push_back({r - l - 1, lst[t][l][r] - fst[t][l][r], 0});
      |                                        ~~~~~~^~~
rect.cpp:33:64: warning: narrowing conversion of '(((int)lst[t][l][r]) - ((int)fst[t][l][r]))' from 'int' to 'short int' [-Wnarrowing]
   33 |                 vec[j][r-1].push_back({r - l - 1, lst[t][l][r] - fst[t][l][r], 0});
      |                                                   ~~~~~~~~~~~~~^~~~~~~~~~~~~~

• 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