Submission #724312

#	Time	Username	Problem	Language	Result	Execution time	Memory
724312		QwertyPi	Rectangles (IOI19_rect)	C++14	0 / 100	4 ms	812 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;
const int N = 2500 + 11;
vector<pii> x[N], y[N];

struct DSU{
	int dsu[N], l[N], r[N], mx[N];
	void init(int n){
		for(int i = 0; i <= n + 2; i++) dsu[i] = l[i] = r[i] = i;
	}
	int root(int x){
		if(x == dsu[x]) return x;
		return dsu[x] = root(dsu[x]);
	}
	void join(int x, int y){
		x = root(x), y = root(y);
		if(x == y) return;
		dsu[y] = x;
		l[x] = min(l[x], l[y]);
		r[x] = max(r[x], r[y]);
	}
} dsu;

int at(const vector<int>& v, int idx){
	if(idx < 0 || idx >= v.size()) return -(1 << 30);
	return v[idx];
}

vector<pii> build(const vector<int>& v){
	vector<pii> res;
	vector<pii> vp; int n = v.size();
	for(int i = 0; i < n; i++){
		vp.push_back({v[i], i});
	}
	sort(vp.begin(), vp.end());
	dsu.init(n);
	for(auto i : vp){
		dsu.join(i.se, i.se + 1);
		int rt = dsu.root(i.se);
		int b_l = dsu.l[rt], b_r = dsu.r[rt] - 1;
		if(at(v, b_l - 1) > i.fi && at(v, b_r + 1) > i.fi){
			res.push_back({b_l, b_r});
		}
	}
	return res;
}

long long count_rectangles(std::vector<std::vector<int>> a) {
	int n = a.size(), m = a[0].size();
	cout << n << ' ' << m << endl;
	for(int i = 0; i < n; i++){
		vector<int> v; for(int j = 0; j < m; j++) v.push_back(a[i][j]);
		x[i] = build(v);
	}
	for(int j = 0; j < m; j++){
		vector<int> v; for(int i = 0; i < n; i++) v.push_back(a[i][j]);
		y[j] = build(v);
	}
	for(int i = 0; i < n; i++){
		for(auto j : x[i]){
			cout << j.fi << ":" << j.se << "|";
		}
		cout << endl;
	}
	return 1;
}

Compilation message (stderr)

rect.cpp: In function 'int at(const std::vector<int>&, int)':
rect.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  if(idx < 0 || idx >= v.size()) return -(1 << 30);
      |                ~~~~^~~~~~~~~~~

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