제출 #297939

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
297939		erd1	Rectangles (IOI19_rect)	C++14	23 / 100	823 ms	159480 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
typedef int64_t lld;
typedef pair<int, int> pii;

/*
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<typename T, typename comp = greater<T>>
using OST = tree<T, null_type, comp, rb_tree_tag, tree_order_statistics_node_update>;
*/

template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
	return out << "(" << p.ff << ", " << p.ss << ")";
}

vector<pii> tmp;
vector<vector<int>> U, D, L, R;

long long count_rectangles(vector<vector<int>> a) {
	int n = a.size(), m = a[0].size();
	U = D = L = R = a;
	for(int i = 1; i < n; i++){
		tmp.resize(0); tmp.pb({INT_MAX, -1});
		for(int j = 0; j < m; j++){
			while(tmp.back().ff <= a[i][j])tmp.pop_back();
			L[i][j] = tmp.back().ss;
			tmp.pb({a[i][j], j});
		}
		tmp.resize(0); tmp.pb({INT_MAX, m});
		for(int j = m-1; j > 0; j--){
			while(tmp.back().ff <= a[i][j])tmp.pop_back();
			R[i][j] = tmp.back().ss;
			tmp.pb({a[i][j], j});
		}
	}
	for(int j = 1; j < m; j++){
		tmp.resize(0); tmp.pb({INT_MAX, -1});
		for(int i = 0; i < n; i++){
			while(tmp.back().ff <= a[i][j])tmp.pop_back();
			U[i][j] = tmp.back().ss;
			tmp.pb({a[i][j], i});
		}
		tmp.resize(0); tmp.pb({INT_MAX, n});
		for(int i = n-1; i > 0; i--){
			while(tmp.back().ff <= a[i][j])tmp.pop_back();
			D[i][j] = tmp.back().ss;
			tmp.pb({a[i][j], i});
		}
	}
	int ans = 0;
	for(int i = 1; i <= n-2; i++)
		for(int j = 1; j <= m-2; j++){
			if(U[i][j] < 0 || D[i][j] >= n || L[i][j] < 0 || R[i][j] >= m)goto next;
			//cout << i << " " << j << " " << U[i][j] << D[i][j] << L[i][j] << R[i][j] << endl;
			for(int x = U[i][j]+1; x < D[i][j]; x++)
				for(int y = L[i][j]+1; y < R[i][j]; y++){
					//cout << " " << x << " " << y << endl;
					if(!(U[i][j] <= U[x][y] && D[i][j] >= D[x][y] && L[i][j] <= L[x][y] && R[i][j] >= R[x][y]))goto next;
					if(a[i][j] == a[x][y] && (x > i || x == i && y > j))goto next;
				}
			//cout << i << " " << j << endl;
			ans++;
			next:;
		}
	return ans;
}

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

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:66:48: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   66 |      if(a[i][j] == a[x][y] && (x > i || x == i && y > j))goto next;
      |                                         ~~~~~~~^~~~~~~~

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