답안 #152080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
152080	2019-09-06T10:21:15 Z	oolimry	Rectangles (IOI19_rect)	C++14	컴파일 오류	0 ms	0 KB

rect

#include <bits/stdc++.h>

using namespace std;

class Segment{
public:
	vector<int> tree;
	int n;
	
	void create(int nn){
		n = nn;
		for(int i = 0;i < 2 * n + 5;i++){
			tree.push_back(-1);
		}
	}
	
	void update(int i, int x){
		i += n;
		while(i > 0){
			tree[i] = max(tree[i],x);
			i >>= 1;
		}
	}
	
	int query(int l, int r){
		int ans = -1;
		for(l += n,r += n;l < r;l >>= 1, r >>= 1){
			if(l&1){
				ans = max(ans,tree[l]);
				l++;
			}
			if(r&1){
				r--;
				ans = max(ans,tree[r]);
			}
		}
		return ans;
	}
};

static int hh[701][701][701];
static int vv[701][701][701];
long long count_rectangles(std::vector<std::vector<int> > a) {
	int rows = a.size();
	int cols = a[0].size();
	long long ans = 0;
	Segment hori[rows];
	Segment vert[cols];
	
	set<long long> answers;
	for(int c = 0;c < cols;c++){
		vert[c].create(rows);
	}
	for(int r = 0;r < rows;r++){
		hori[r].create(cols);
	}
	
	for(int r = 0;r < rows;r++){
		for(int i = 0;i < cols;i++){
			for(int j = i;j < cols;j++){
				if(i == j) hh[r][i][j] = a[r][i];
				else hh[r][i][j] = max(hh[r][i][j-1],a[r][j]);
			}
		}
	}
	for(int c = 0;c < cols;c++){
		for(int i = 0;i < rows;i++){
			for(int j = i;j < rows;j++){
				if(i == j) vv[c][i][j] = a[i][c];
				else vv[c][i][j] = max(vv[c][i][j-1],a[j][c]);
			}
		}
	}
	for(int r = 0;r < rows;r++){
		for(int c = 0;c < cols;c++){
			hori[r].update(c,a[r][c]);
			vert[c].update(r,a[r][c]);
		}
	}
	typedef pair<int,int> ii;
	typedef pair<int,ii> iii;
	
	vector<iii> points;
	for(int r = 0;r < rows;r++){
		for(int c = 0;c < cols;c++){
			points.push_back(iii(a[r][c],ii(r,c)));
		}
	}
	
	sort(points.begin(),points.end());
	stack<ii> arr;
	for(int p = 0;p < points.size();p++){
		int rr = points[p].second.first;
		int cc = points[p].second.second;
		//cout << rr << " " << cc << " " << a[rr][cc] << "\n";
		arr.push(ii(rr,cc));
		if(p == points.size()-1 || points[p].first != points[p+1].first){
			while(!arr.empty()){
				int r = arr.top().first;
				int c = arr.top().second;
				arr.pop();
				if(r == 0 || r == rows - 1 || c == 0 || c == cols-1) continue;
				
				//if(hhh[r].query(c) != 0) continue;
				
				int lr = r, hr = r, lc = c, hc = c; //exclusive
				
				while(lr > 0){
					if(a[lr][c] > a[r][c]) break;
					lr--;
				}
				
				while(hr < rows-1){
					if(a[hr][c] > a[r][c]) break;
					hr++;
				}
				
				while(lc > 0){
					if(a[r][lc] > a[r][c]) break;
					lc--;
				}
				
				while(hc < cols-1){
					if(a[r][hc] > a[r][c]) break;
					hc++;
				}
				
				bool can = true;
				for(int sr = lr+1;sr < hr;sr++){
					//int value = hori[sr].query(lc+1,hc);
					int value = hh[sr][lc+1][hc-1];
					if(value >= a[sr][lc] || value >= a[sr][hc]){
						can = false;
						break;
					}
				}
				for(int sc = lc+1;sc < hc;sc++){
					//int value = vert[sc].query(lr+1,hr);
					int value = vv[sc][lr+1][hr-1];
					if(value >= a[lr][sc] || value >= a[hr][sc]){
						can = false;
						break;
					}
				}
				
				if(can){
					
					long long vvv = lr * 1000000000ll;
					vvv += hr * 1000000ll;
					vvv += lc * 1000ll;
					vvv += hc;
					answers.insert(vvv);
				}
				
				//cout << r << " " << c << " " << lr << " " << hr << " " << lc << " " << hc << "\n";
			}
			
		}
	}
	return answers.size();
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:92:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int p = 0;p < points.size();p++){
                ~~^~~~~~~~~~~~~~~
rect.cpp:97:8: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(p == points.size()-1 || points[p].first != points[p+1].first){
      ~~^~~~~~~~~~~~~~~~~~
rect.cpp:46:12: warning: unused variable 'ans' [-Wunused-variable]
  long long ans = 0;
            ^~~
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::(anonymous namespace)::__destroy_string<wchar_t>(void*)':
(.text._ZNSt13__facet_shims12_GLOBAL__N_116__destroy_stringIwEEvPv+0x1e): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::(anonymous namespace)::__destroy_string<char>(void*)':
(.text._ZNSt13__facet_shims12_GLOBAL__N_116__destroy_stringIcEEvPv+0x1e): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<wchar_t>::do_get(std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, bool, std::ios_base&, std::_Ios_Iostate&, std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIwE6do_getESt19istreambuf_iteratorIwSt11char_traitsIwEES6_bRSt8ios_baseRSt12_Ios_IostateRSbIwS5_SaIwEE+0xfe): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<wchar_t>::do_get(std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, std::istreambuf_iterator<wchar_t, std::char_traits<wchar_t> >, bool, std::ios_base&, std::_Ios_Iostate&, std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIwE6do_getESt19istreambuf_iteratorIwSt11char_traitsIwEES6_bRSt8ios_baseRSt12_Ios_IostateRSbIwS5_SaIwEE+0x17b): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<char>::do_get(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, bool, std::ios_base&, std::_Ios_Iostate&, std::string&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIcE6do_getESt19istreambuf_iteratorIcSt11char_traitsIcEES6_bRSt8ios_baseRSt12_Ios_IostateRSs+0xfe): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `std::__facet_shims::(anonymous namespace)::money_get_shim<char>::do_get(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, bool, std::ios_base&, std::_Ios_Iostate&, std::string&) const':
(.text._ZNKSt13__facet_shims12_GLOBAL__N_114money_get_shimIcE6do_getESt19istreambuf_iteratorIcSt11char_traitsIcEES6_bRSt8ios_baseRSt12_Ios_IostateRSs+0x17b): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<char>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<char>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0xa1): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<char>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<char>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIcEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x24f): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0xa9): relocation truncated to fit: R_X86_64_32S against symbol `std::string::_Rep::_S_empty_rep_storage' defined in .bss._ZNSs4_Rep20_S_empty_rep_storageE[_ZNSs4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-string-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x114): relocation truncated to fit: R_X86_64_32S against symbol `std::basic_string<wchar_t, std::char_traits<wchar_t>, std::allocator<wchar_t> >::_Rep::_S_empty_rep_storage' defined in .bss._ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE[_ZNSbIwSt11char_traitsIwESaIwEE4_Rep20_S_empty_rep_storageE] section in /usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-wstring-inst.o)
/usr/lib/gcc/x86_64-linux-gnu/7/libstdc++.a(cow-shim_facets.o): In function `void std::__facet_shims::__numpunct_fill_cache<wchar_t>(std::integral_constant<bool, false>, std::locale::facet const*, std::__numpunct_cache<wchar_t>*)':
(.text._ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E[_ZNSt13__facet_shims21__numpunct_fill_cacheIwEEvSt17integral_constantIbLb0EEPKNSt6locale5facetEPSt16__numpunct_cacheIT_E]+0x294): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status