Submission #298013

#	Time	Username	Problem	Language	Result	Execution time	Memory
298013		erd1	Rectangles (IOI19_rect)	C++14	72 / 100	5109 ms	807692 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;


template<typename Cmp>
struct Sgt{
	Cmp _cmp;
	int cmp(int a, int b){ return _cmp(a, b)?a:b; }
	vector<vector<int>> data;
	int n, m;
	void build_data(int j, int i, int ll, int rr, const vector<int>& v){
		if(data[j].size() <= i)data[j].resize(i+1);
		if(ll == rr)data[j][i] = v[ll];
		else build_data(j, i<<1, ll, (ll+rr)>>1, v), build_data(j, (i<<1)+1, ((ll+rr)>>1)+1, rr, v), data[j][i] = cmp(data[j][i<<1], data[j][(i<<1)+1]);
	}
	void build(int i, int ll, int rr, const vector<vector<int>>& v){
		if(data.size() <= i)data.resize(i+1);
		if(ll == rr) build_data(i, 1, 0, m-1, v[ll]);
		else {
			build(i<<1, ll, (ll+rr)>>1, v); build((i<<1)+1, ((ll+rr)>>1)+1, rr, v);
			data[i].resize(data[i<<1].size());
			for(int j = 0; j < data[i].size(); j++)
				data[i][j] = cmp(data[i<<1][j], data[(i<<1)+1][j]);
		}
	}
	void init(int nn, int mm, const vector<vector<int>>& v){
		n = nn, m = mm;
		build(1, 0, n-1, v);
	}
	int query_data(int j, int i, int ll, int rr, int ql, int qr){
		assert(ql <= rr && qr >= ll);
		if(ql <= ll && qr >= rr)return data[j][i];
		if(qr <= ((ll+rr)>>1))return query_data(j, i<<1, ll, (ll+rr)>>1, ql, qr);
		if(ql > ((ll+rr)>>1))return query_data(j, (i<<1)+1, ((ll+rr)>>1)+1, rr, ql, qr);
		return cmp(query_data(j, i<<1, ll, (ll+rr)>>1, ql, qr), query_data(j, (i<<1)+1, ((ll+rr)>>1)+1, rr, ql, qr));
	}
	int qquery(int i, int ll, int rr, int ql, int qr, int l2, int r2){
		assert(ql <= rr && qr >= ll);
		if(ql <= ll && qr >= rr)return query_data(i, 1, 0, m-1, l2, r2);
		if(qr <= ((ll+rr)>>1))return qquery(i<<1, ll, (ll+rr)>>1, ql, qr, l2, r2);
		if(ql > ((ll+rr)>>1))return qquery((i<<1)+1, ((ll+rr)>>1)+1, rr, ql, qr, l2, r2);
		return cmp(qquery(i<<1, ll, (ll+rr)>>1, ql, qr, l2, r2), qquery((i<<1)+1, ((ll+rr)>>1)+1, rr, ql, qr, l2, r2));
	}
	int query(int a, int b, int c, int d){
		return qquery(1, 0, n-1, a, b, c, d);
	}
};

/*
template<typename Cmp>
struct node{
	node *L, *R;
	int l, r, mid, s;
	int cmp(int a, int b){ return Cmp()(a, b)?a:b; }
	vector<int> data;
	node(int ll, int rr, int st, const vector<vector<int>>& v) : l(ll), r(rr), mid((l+r)/2), s(st) {
		data.resize(s*4);
		if(l != r){
			L = new node(l, mid, s, v), R = new node(mid+1, r, s, v);
			for(int i = 0; i < data.size(); i++)data.at(i) = cmp(L->data.at(i), R->data.at(i));
		}
		else build_data(1, 0, s, v.at(l));
	}
	void build_data(int i, int ll, int rr, const vector<int>& v){
		if(data.size() <= i)data.resize(i+1);
		if(ll == rr)data[i] = v[ll];
		else build_data(i<<1, ll, (ll+rr)>>1, v), build_data((i<<1)+1, ((ll+rr)>>1)+1, rr, v), data[i] = cmp(data[i<<1], data[(i<<1)+1]);
	}
	int query_data(int i, int ll, int rr, int ql, int qr){
		//cout << ll << " " << rr << " " << ql << " " << qr << endl;
		assert(ql <= rr && qr >= ll);
		if(ql <= ll && qr >= rr)return data[i];
		if(qr <= ((ll+rr)>>1))return query_data(i<<1, ll, (ll+rr)>>1, ql, qr);
		if(ql > ((ll+rr)>>1))return query_data((i<<1)+1, ((ll+rr)>>1)+1, rr, ql, qr);
		return cmp(query_data(i<<1, ll, (ll+rr)>>1, ql, qr), query_data((i<<1)+1, ((ll+rr)>>1)+1, rr, ql, qr));

	}
	int query(int l1, int r1, int l2, int r2){
		assert(l1 <= r && r1 >= l);
		if(l1 <= l && r1 >= r)return query_data(1, 0, s, l2, r2);
		if(l1 > mid)return R->query(l1, r1, l2, r2);
		if(r1 <= mid)return L->query(l1, r1, l2, r2);
		return cmp(L->query(l1, r1, l2, r2), R->query(l1, r1, l2, r2));
	}
};
*/

Sgt<greater<int>> d, r;
Sgt<less<int>> u, l;
set<tuple<int, int, int, int>> st;

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});
		}
	}
	u.init(n, m, U), d.init(n, m, D), l.init(n, m, L), r.init(n, m, R);
	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] << " " << u->query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) << endl;
			if(u.query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != U[i][j])goto next;
			if(l.query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != L[i][j])goto next;
			if(d.query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != D[i][j])goto next;
			if(r.query(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1) != R[i][j])goto next;
			st.insert({U[i][j], L[i][j], D[i][j], R[i][j]});
			next:;
		}
	return st.size();
}

Compilation message (stderr)

rect.cpp: In instantiation of 'void Sgt<Cmp>::build(int, int, int, const std::vector<std::vector<int> >&) [with Cmp = std::less<int>]':
rect.cpp:50:3:   required from 'void Sgt<Cmp>::init(int, int, const std::vector<std::vector<int> >&) [with Cmp = std::less<int>]'
rect.cpp:145:16:   required from here
rect.cpp:39:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |   if(data.size() <= i)data.resize(i+1);
      |      ~~~~~~~~~~~~^~~~
rect.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    for(int j = 0; j < data[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~~~~
rect.cpp: In instantiation of 'void Sgt<Cmp>::build(int, int, int, const std::vector<std::vector<int> >&) [with Cmp = std::greater<int>]':
rect.cpp:50:3:   required from 'void Sgt<Cmp>::init(int, int, const std::vector<std::vector<int> >&) [with Cmp = std::greater<int>]'
rect.cpp:145:33:   required from here
rect.cpp:39:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |   if(data.size() <= i)data.resize(i+1);
      |      ~~~~~~~~~~~~^~~~
rect.cpp:44:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    for(int j = 0; j < data[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~~~~
rect.cpp: In instantiation of 'void Sgt<Cmp>::build_data(int, int, int, int, const std::vector<int>&) [with Cmp = std::less<int>]':
rect.cpp:40:16:   required from 'void Sgt<Cmp>::build(int, int, int, const std::vector<std::vector<int> >&) [with Cmp = std::less<int>]'
rect.cpp:50:3:   required from 'void Sgt<Cmp>::init(int, int, const std::vector<std::vector<int> >&) [with Cmp = std::less<int>]'
rect.cpp:145:16:   required from here
rect.cpp:34:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |   if(data[j].size() <= i)data[j].resize(i+1);
      |      ~~~~~~~~~~~~~~~^~~~
rect.cpp: In instantiation of 'void Sgt<Cmp>::build_data(int, int, int, int, const std::vector<int>&) [with Cmp = std::greater<int>]':
rect.cpp:40:16:   required from 'void Sgt<Cmp>::build(int, int, int, const std::vector<std::vector<int> >&) [with Cmp = std::greater<int>]'
rect.cpp:50:3:   required from 'void Sgt<Cmp>::init(int, int, const std::vector<std::vector<int> >&) [with Cmp = std::greater<int>]'
rect.cpp:145:33:   required from here
rect.cpp:34:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]

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