oj.uz

답안 #1073282

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1073282 2024-08-24T11:49:02 Z n1k Rectangles (IOI19_rect) C++17
0 / 100
 1561 ms 377880 KB 
#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

int n, m;

vector<vector<array<int, 3>>> h;

vector<vector<array<int, 2>>> get(){
	vector<vector<array<int, 2>>> l(n, vector<array<int, 2>>(m));
	for(int r=1; r+1<h.size(); r++){
		vector<array<int, 3>> st = {{h[r][0]}};
		for(int c=1; c+1<h[0].size(); c++){
			while(st.size() and st.back()[0]<=h[r][c][0]){
				st.pop_back();
			}
			l[h[r][c][1]][h[r][c][2]] = (st.size()?array<int, 2>{st.back()[1], st.back()[2]}:array<int, 2>{-1, -1});
			st.push_back(h[r][c]);
		}
	}
	return l;
}

void rot(){
	vector<vector<array<int, 3>>> hh(h[0].size(), vector<array<int, 3>>(h.size()));
	for(int r=0; r<h.size(); r++){
		for(int c=0; c<h[0].size(); c++){
			hh[c][h.size() - r - 1] = h[r][c];
		}
	}
	h = hh;
}

long long count_rectangles(vector<vector<int>> a) {
	n = a.size(), m = a[0].size();
	h.assign(a.size(), vector<array<int, 3>>(a[0].size()));
	vector<array<int, 3>> order;
	for(int r=0; r<a.size(); r++){
		for(int c=0; c<a[0].size(); c++){
			h[r][c] = {a[r][c], r, c};
		}
	}
	for(int r=1; r+1<a.size(); r++){
		for(int c=1; c+1<a[0].size(); c++){
			order.push_back({a[r][c], r, c});
		}
	}
	sort(order.begin(), order.end());
	auto l=get();
	rot();
	auto d = get();
	rot();
	auto ri = get();
	rot();
	auto u = get();
	rot();

	auto find = [&](int r1, int r2, int c1, int c2){
		array<int, 3> ll={int(1e9)}, dd={int(-1e9)}, riri={int(-1e9)}, uu={int(1e9)};
		for(int r=r1+1; r<r2; r++){
			for(int c=c1+1; c<c2; c++){
				ll = min(ll, {l[r][c][1], r, c});
				dd = max(dd, {d[r][c][0], r, c});
				riri = max(riri, {ri[r][c][1], r, c});
				uu = min(uu, {u[r][c][0], r, c});
			}
		}
		set<array<int, 2>> s;
		s.insert({ll[1], ll[2]});
		s.insert({dd[1], dd[2]});
		s.insert({riri[1], riri[2]});
		s.insert({uu[1], uu[2]});
		return s;
	};

	vector g(n, vector<vector<array<int, 2>>>(m));
	for(int r=0; r<n; r++){
		for(int c=0; c<m; c++){
			// find()
			int r1 = u[r][c][0], r2 = d[r][c][0];
			int c1 = l[r][c][1], c2 = ri[r][c][1];
			if(min({r1, r2, c1, c2})==-1){
				g[r][c].push_back({-1, -1});
			}else{
				for(auto p:find(r1, r2, c1, c2)){
					g[r][c].push_back(p);
				}
			}
		}
	}
	vector mem(n, vector<int>(m, -1));
	vector vis(n, vector<int>(m));
	function<void(int, int)> dfs = [&](int r, int c){
		if(vis[r][c]) return;
		vis[r][c]=1;
		if(mem[r][c]!=-1) mem[r][c];
		bool ok = 1;
		for(auto [rr, cc]:g[r][c]){
			if(rr==r and cc==c){
				continue;
			}
			if(rr==-1 and cc==-1){
				ok = 0;
				break;
			}
			dfs(rr, cc);
			ok &= mem[rr][cc];
		}
		mem[r][c] = ok;
	};
	long long ans = 0;
	for(auto [_, r, c]:order){
		if(vis[r][c]) continue;
		dfs(r, c);
		ans += mem[r][c];
		//cerr<<r<<" "<<c<<" "<<mem[r][c]<<endl;
	}
	// build graph

	/*
	for(int r=0; r<u.size();r++){
		for(int c=0; c<u[0].size(); c++){
			cerr<<u[r][c][0]<<" "<<u[r][c][1]<<" | ";
		}
		cerr<<endl;
	}
	for(int r=0; r<h.size(); r++){
		for(int c=0; c<h[0].size(); c++){
			cerr<<h[r][c][0]<<" ";
		}
		cerr<<endl;
	}
	*/
	return ans;
}

Compilation message

rect.cpp: In function 'std::vector<std::vector<std::array<int, 2> > > get()':
rect.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int r=1; r+1<h.size(); r++){
      |               ~~~^~~~~~~~~
rect.cpp:14:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for(int c=1; c+1<h[0].size(); c++){
      |                ~~~^~~~~~~~~~~~
rect.cpp: In function 'void rot()':
rect.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::array<int, 3> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for(int r=0; r<h.size(); r++){
      |               ~^~~~~~~~~
rect.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int c=0; c<h[0].size(); c++){
      |                ~^~~~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int r=0; r<a.size(); r++){
      |               ~^~~~~~~~~
rect.cpp:40:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   for(int c=0; c<a[0].size(); c++){
      |                ~^~~~~~~~~~~~
rect.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int r=1; r+1<a.size(); r++){
      |               ~~~^~~~~~~~~
rect.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for(int c=1; c+1<a[0].size(); c++){
      |                ~~~^~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 612 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 432 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 612 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 432 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 612 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 432 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 612 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 432 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 1364 KB Output is correct
2 Correct 41 ms 1152 KB Output is correct
3 Correct 2 ms 1372 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Incorrect 3 ms 1368 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1561 ms 377880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 4 ms 612 KB Output is correct
4 Correct 4 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Incorrect 1 ms 432 KB Output isn't correct
7 Halted 0 ms 0 KB -