답안 #156313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
156313	2019-10-05T02:28:16 Z	wilwxk	Rectangles (IOI19_rect)	C++14	컴파일 오류	0 ms	0 KB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MAXN=2503;
int v[MAXN][MAXN];
short limite[MAXN][MAXN][4];
short qv[MAXN][MAXN][4];
short seg[4][MAXN][4*MAXN];
unordered_set<tuple<int, int, int, int> > respf;
int n, m;
 
void histoi() {
	for(int i=0; i<n; i++) {
		stack<pair<int, int> > st;
		for(int j=0; j<m; j++) {
			while(st.size()&&st.top().first<v[i][j]) {
				qv[i][st.top().second][0]=j;
				st.pop();
			}
			limite[i][j][2]= st.size() ? st.top().second : -1;
			st.push({v[i][j], j});
		}
		while(st.size()) st.pop();
		for(int j=m-1; j>=0; j--) {
			while(st.size()&&st.top().first<v[i][j]) {
				qv[i][st.top().second][2]=j;
				st.pop();
			}
			limite[i][j][0]= st.size() ? st.top().second : m;
			st.push({v[i][j], j});
		}
	}
}
 
void histoj() {
	for(int j=0; j<m; j++) {
		stack<pair<int, int> > st;
		for(int i=0; i<n; i++) {
			while(st.size()&&st.top().first<v[i][j]) {
				qv[st.top().second][j][3]=i;
				st.pop();
			}
			limite[i][j][1]= st.size() ? st.top().second : -1;
			st.push({v[i][j], i});
		}
		while(st.size()) st.pop();
		for(int i=n-1; i>=0; i--) {
			while(st.size()&&st.top().first<v[i][j]) {
				qv[st.top().second][j][1]=i;
				st.pop();
			}
			limite[i][j][3]= st.size() ? st.top().second : n;
			st.push({v[i][j], i});
		}
	}
}
 
void junta(int sind, int e, int d, int k, int k2) {
	if(k==0||k==3) seg[k][k2][sind]=min(seg[k][k2][e], seg[k][k2][d]);
	else seg[k][k2][sind]=max(seg[k][k2][e], seg[k][k2][d]);
}
 
void build(int sind, int ini, int fim, int k, int k2) {
	if(ini==fim) {
		if(k==0||k==2) seg[k][k2][sind]=limite[ini][k2][k];
		else seg[k][k2][sind]=limite[k2][ini][k];
		return;
	}
	int mid=(ini+fim)/2;
	int e=sind*2; int d=e+1;
	build(e, ini, mid, k, k2); build(d, mid+1, fim, k, k2);
	junta(sind, e, d, k, k2);
} 
 
void query(int sind, int ini, int fim, int qini, int qfim, int k, int k2) {
	if(sind==1) {
		if(k==0||k==3) seg[k][k2][0]=MAXN;
		else seg[k][k2][0]=-1;
	}
	if(qini<=ini&&qfim>=fim) {
		junta(0, 0, sind, k, k2);
		return;
	}
	int mid=(ini+fim)/2;
	int e=sind*2; int d=e+1;
	if(qini<=mid) query(e, ini, mid, qini, qfim, k, k2);
	if(qfim>mid) query(d, mid+1, fim, qini, qfim, k, k2);
}
 
bool checa(int a, int b, int c, int d) {
	int i, j, i2, j2;
	i=min(a, c); i2=max(a, c);
	j=min(b, d); j2=max(b, d);
	if(i<0||j<0||i2>n-1||j2>m-1) return 0;
	// printf("checa %d %d %d %d\n", i, j, i2, j2);
 
	query(1, 0, m-1, j+1, j2-1, 3, i);
	int aa=seg[3][i][0];
	if(aa<i2) return 0;
 
	query(1, 0, m-1, j+1, j2-1, 1, i2);
	int bb=seg[1][i2][0];
	if(bb>i) return 0;
 
	query(1, 0, n-1, i+1, i2-1, 0, j);
	int cc=seg[0][j][0];
	if(cc<j2) return 0;
 
	query(1, 0, n-1, i+1, i2-1, 2, j2);
	int dd=seg[2][j2][0];
	if(dd>j) return 0;
 
	// printf("ok %d %d %d %d\n", aa, bb, cc, dd);
 
	return 1;
}
 
ll count_rectangles(vector< vector<int> > A) {
	n=A.size(); m=A[0].size();
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			v[i][j]=A[i][j];
			qv[i][j][0]=m;
			qv[i][j][1]=-1;
			qv[i][j][2]=-1;
			qv[i][j][3]=n;
		}
	}
	histoi(); histoj();
	// for(int i=0; i<n; i++) {
	// 	for(int j=0; j<m; j++) printf("%d ", qv[i][j][0]);
	// 	printf("\n");
	// }
 
	for(int i=0; i<n; i++) build(1, 0, m-1, 1, i), build(1, 0, m-1, 3, i);
	for(int j=0; j<m; j++) build(1, 0, n-1, 0, j), build(1, 0, n-1, 2, j);
 
	for(int ii=1; ii<n-1; ii++) {
		for(int jj=1; jj<m-1; jj++) {
			// printf("%d %d\n", ii, jj);
			int i=qv[ii][jj][1];
			int j=qv[ii][jj][2];
			int i2=qv[ii][jj][3];
			int j2=qv[ii][jj][0];
			if(checa(i, j, i2, j2)) respf.insert({i, j, i2, j2});
		}
	}
 
	return respf.size();
}

Compilation message

In file included from /usr/include/c++/7/bits/hashtable.h:35:0,
                 from /usr/include/c++/7/unordered_map:47,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:117,
                 from rect.cpp:2:
/usr/include/c++/7/bits/hashtable_policy.h: In instantiation of 'struct std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > >':
/usr/include/c++/7/type_traits:143:12:   required from 'struct std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > >'
/usr/include/c++/7/type_traits:154:31:   required from 'struct std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
/usr/include/c++/7/bits/unordered_set.h:98:63:   required from 'class std::unordered_set<std::tuple<int, int, int, int> >'
rect.cpp:11:43:   required from here
/usr/include/c++/7/bits/hashtable_policy.h:87:34: error: no match for call to '(const std::hash<std::tuple<int, int, int, int> >) (const std::tuple<int, int, int, int>&)'
  noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
           ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/bits/move.h:54:0,
                 from /usr/include/c++/7/bits/stl_pair.h:59,
                 from /usr/include/c++/7/bits/stl_algobase.h:64,
                 from /usr/include/c++/7/vector:60,
                 from rect.h:5,
                 from rect.cpp:1:
/usr/include/c++/7/type_traits: In instantiation of 'struct std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >':
/usr/include/c++/7/bits/unordered_set.h:98:63:   required from 'class std::unordered_set<std::tuple<int, int, int, int> >'
rect.cpp:11:43:   required from here
/usr/include/c++/7/type_traits:154:31: error: 'value' is not a member of 'std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > >'
     : public __bool_constant<!bool(_Pp::value)>
                               ^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/7/unordered_set:48:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:118,
                 from rect.cpp:2:
/usr/include/c++/7/bits/unordered_set.h: In instantiation of 'class std::unordered_set<std::tuple<int, int, int, int> >':
rect.cpp:11:43:   required from here
/usr/include/c++/7/bits/unordered_set.h:98:63: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef __uset_hashtable<_Value, _Hash, _Pred, _Alloc>  _Hashtable;
                                                               ^~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:105:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::key_type key_type;
                                             ^~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:106:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::value_type value_type;
                                               ^~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:107:43: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::hasher hasher;
                                           ^~~~~~
/usr/include/c++/7/bits/unordered_set.h:108:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::key_equal key_equal;
                                              ^~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:109:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::allocator_type allocator_type;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:114:45: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::pointer  pointer;
                                             ^~~~~~~
/usr/include/c++/7/bits/unordered_set.h:115:50: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::const_pointer const_pointer;
                                                  ^~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:116:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::reference  reference;
                                               ^~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:117:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::const_reference const_reference;
                                                    ^~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:118:46: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::iterator  iterator;
                                              ^~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:119:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::const_iterator const_iterator;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:120:51: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::local_iterator local_iterator;
                                                   ^~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:121:57: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::const_local_iterator const_local_iterator;
                                                         ^~~~~~~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:122:47: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::size_type  size_type;
                                               ^~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:123:52: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       typedef typename _Hashtable::difference_type difference_type;
                                                    ^~~~~~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:282:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       operator=(initializer_list<value_type> __l)
       ^~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:375:2: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
  emplace(_Args&&... __args)
  ^~~~~~~
/usr/include/c++/7/bits/unordered_set.h:419:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       insert(const value_type& __x)
       ^~~~~~
/usr/include/c++/7/bits/unordered_set.h:423:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       insert(value_type&& __x)
       ^~~~~~
/usr/include/c++/7/bits/unordered_set.h:478:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       insert(initializer_list<value_type> __l)
       ^~~~~~
/usr/include/c++/7/bits/unordered_set.h:679:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       equal_range(const key_type& __x)
       ^~~~~~~~~~~
/usr/include/c++/7/bits/unordered_set.h:683:7: error: 'value' is not a member of 'std::__not_<std::__and_<std::__is_fast_hash<std::hash<std::tuple<int, int, int, int> > >, std::__detail::__is_noexcept_hash<std::tuple<int, int, int, int>, std::hash<std::tuple<int, int, int, int> > > > >'
       equal_range(const key_type& __x) const
       ^~~~~~~~~~~
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:147:55: error: no matching function for call to 'std::unordered_set<std::tuple<int, int, int, int> >::insert(<brace-enclosed initializer list>)'
    if(checa(i, j, i2, j2)) respf.insert({i, j, i2, j2});
                                                       ^
In file included from /usr/include/c++/7/unordered_set:48:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:118,
                 from rect.cpp:2:
/usr/include/c++/7/bits/unordered_set.h:467:2: note: candidate: template<class _InputIterator> void std::unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Value = std::tuple<int, int, int, int>; _Hash = std::hash<std::tuple<int, int, int, int> >; _Pred = std::equal_to<std::tuple<int, int, int, int> >; _Alloc = std::allocator<std::tuple<int, int, int, int> >]
  insert(_InputIterator __first, _InputIterator __last)
  ^~~~~~
/usr/include/c++/7/bits/unordered_set.h:467:2: note:   template argument deduction/substitution failed:
rect.cpp:147:55: note:   candidate expects 2 arguments, 1 provided
    if(checa(i, j, i2, j2)) respf.insert({i, j, i2, j2});
                                                       ^
rect.cpp:151:15: error: 'class std::unordered_set<std::tuple<int, int, int, int> >' has no member named 'size'
  return respf.size();
               ^~~~