Submission #298129

#	Time	Username	Problem	Language	Result	Execution time	Memory
298129		erd1	Rectangles (IOI19_rect)	C++14	72 / 100	4453 ms	1048580 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<int16_t>> U, D, L, R, t, ans;
vector<vector<bool>> ansb;
vector<int16_t> dsu, sz, rtx;
inline void init(){ iota(all(dsu), 0); fill(all(sz), 1); iota(all(rtx), 0); }
int16_t root(int i){ return dsu[i] == i? i: dsu[i] = root(dsu[i]); }
inline void join(int16_t i, int16_t j){ i = root(i), j = root(j); int16_t u = j; if(sz[i] > sz[j])swap(i, j); dsu[i] = j; rtx[j] = u; }
struct node;
vector<node> nodes;
struct node{
	int L, R;
	int16_t l, r;
	array<vector<pair<int16_t, pair<int16_t, int16_t>>>, 2500> queries;
	void init(int16_t ix, int16_t ll, int16_t rr, int16_t m){
		l = ll, r = rr;
		if(l != r)L = ix*2, R = ix*2+1, nodes[L].init(L, l, l+r>>1, m), nodes[R].init(R, (l+r>>1)+1, r, m);
	}
	void add(int16_t ll, int16_t rr, int16_t l2, int16_t r2, int16_t x, int16_t y){
		if(ll > r || rr < l)return;
		if(ll <= l && r <= rr)queries[r2].pb({l2, {x, y}});
		else nodes[L].add(ll, rr, l2, r2, x, y), nodes[R].add(ll, rr, l2, r2, x, y);
	}
	inline void answer(int l, const bool c){
		::init(); tmp.resize(0);
		for(int i = 0; i < t[l].size(); i++){
			while(tmp.size() && (c?t[l][i] < tmp.back().ff:t[l][i]>tmp.back().ff))join(tmp.back().ss, i), tmp.pop_back();
			tmp.pb({t[l][i], i});
			for(auto p: queries[i]) //
				if(ans[p.ss.ff][p.ss.ss] == -2 || (c?t[l][root(p.ff)]<ans[p.ss.ff][p.ss.ss]:t[l][root(p.ff)]>ans[p.ss.ff][p.ss.ss]))
					ans[p.ss.ff][p.ss.ss] = t[l][rtx[root(p.ff)]];
			}
	}
	void process(const bool c){
		//cout << "process" << l << " " << r << endl;
		if(l != r){
			nodes[L].process(c), nodes[R].process(c);
			for(int i = 0; i < t[l].size(); i++)
				t[l][i] = (c?t[l][i]<t[(l+r>>1)+1][i]:t[l][i]>t[(l+r>>1)+1][i])?t[l][i]:t[(l+r>>1)+1][i];
		}
		answer(l, c);
		//cout << "end_process" << l << " " << r << endl;
	}
};
vector<tuple<int16_t, int16_t, int16_t, int16_t>> st;

long long count_rectangles(vector<vector<int>> a) {
	int n = a.size(), m = a[0].size();
	ans.resize(n); for(auto& i: ans)i.resize(m);
	ansb.resize(n); for(auto& i: ansb)i.resize(m, 1);
	dsu.resize(m); rtx.resize(m); sz.resize(m, 1);
	U = D = L = R = ans;
	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});
		}
	}
	nodes.resize(4*n+10);
	nodes[1].init(1, 0, n-1, m);
	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))
				nodes[1].add(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1, i, j);
	for(auto& i: ans)fill(all(i), -2); t = U, nodes[1].process(1); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != U[i][j])ansb[i][j] = false;
	for(auto& i: ans)fill(all(i), -2); t = L, nodes[1].process(1); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != L[i][j])ansb[i][j] = false;
	for(auto& i: ans)fill(all(i), -2); t = D, nodes[1].process(0); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != D[i][j])ansb[i][j] = false;
	for(auto& i: ans)fill(all(i), -2); t = R, nodes[1].process(0); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != R[i][j])ansb[i][j] = false;
	//cout << "hi" << endl;
	//u.init(n, m), d.init(n, m), l.init(n, m), r.init(n, m);
	for(int i = 1; i <= n-2; i++)
		for(int j = 1; j <= m-2; j++)
			if(ansb[i][j])
				st.pb({U[i][j], L[i][j], D[i][j], R[i][j]});
	sort(all(st));
	return unique(all(st))-st.begin();
}

Compilation message (stderr)

rect.cpp: In member function 'void node::init(int16_t, int16_t, int16_t, int16_t)':
rect.cpp:38:56: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   if(l != r)L = ix*2, R = ix*2+1, nodes[L].init(L, l, l+r>>1, m), nodes[R].init(R, (l+r>>1)+1, r, m);
      |                                                       ~^~
rect.cpp:38:86: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   if(l != r)L = ix*2, R = ix*2+1, nodes[L].init(L, l, l+r>>1, m), nodes[R].init(R, (l+r>>1)+1, r, m);
      |                                                                                     ~^~
rect.cpp: In member function 'void node::answer(int, bool)':
rect.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for(int i = 0; i < t[l].size(); i++){
      |                  ~~^~~~~~~~~~~~~
rect.cpp: In member function 'void node::process(bool)':
rect.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for(int i = 0; i < t[l].size(); i++)
      |                   ~~^~~~~~~~~~~~~
rect.cpp:60:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     t[l][i] = (c?t[l][i]<t[(l+r>>1)+1][i]:t[l][i]>t[(l+r>>1)+1][i])?t[l][i]:t[(l+r>>1)+1][i];
      |                             ~^~
rect.cpp:60:55: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     t[l][i] = (c?t[l][i]<t[(l+r>>1)+1][i]:t[l][i]>t[(l+r>>1)+1][i])?t[l][i]:t[(l+r>>1)+1][i];
      |                                                      ~^~
rect.cpp:60:81: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     t[l][i] = (c?t[l][i]<t[(l+r>>1)+1][i]:t[l][i]>t[(l+r>>1)+1][i])?t[l][i]:t[(l+r>>1)+1][i];
      |                                                                                ~^~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:108:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  108 |  for(auto& i: ans)fill(all(i), -2); t = U, nodes[1].process(1); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != U[i][j])ansb[i][j] = false;
      |  ^~~
rect.cpp:108:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  108 |  for(auto& i: ans)fill(all(i), -2); t = U, nodes[1].process(1); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != U[i][j])ansb[i][j] = false;
      |                                     ^
rect.cpp:109:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  109 |  for(auto& i: ans)fill(all(i), -2); t = L, nodes[1].process(1); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != L[i][j])ansb[i][j] = false;
      |  ^~~
rect.cpp:109:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  109 |  for(auto& i: ans)fill(all(i), -2); t = L, nodes[1].process(1); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != L[i][j])ansb[i][j] = false;
      |                                     ^
rect.cpp:110:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  110 |  for(auto& i: ans)fill(all(i), -2); t = D, nodes[1].process(0); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != D[i][j])ansb[i][j] = false;
      |  ^~~
rect.cpp:110:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  110 |  for(auto& i: ans)fill(all(i), -2); t = D, nodes[1].process(0); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != D[i][j])ansb[i][j] = false;
      |                                     ^
rect.cpp:111:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  111 |  for(auto& i: ans)fill(all(i), -2); t = R, nodes[1].process(0); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != R[i][j])ansb[i][j] = false;
      |  ^~~
rect.cpp:111:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  111 |  for(auto& i: ans)fill(all(i), -2); t = R, nodes[1].process(0); for(int i = 1; i <= n-2; i++) for(int j = 1; j <= m-2; j++) if(ans[i][j] != R[i][j])ansb[i][j] = false;
      |                                     ^

• 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