Submission #810622

#	Time	Username	Problem	Language	Result	Execution time	Memory
810622		fatemetmhr	Rectangles (IOI19_rect)	C++17	100 / 100	1421 ms	355804 KiB

rect

// na mn tanha nistam :) hich vaghtam bi bahre naboodam ...


#include <bits/stdc++.h>
#include "rect.h"

using namespace std;

#define all(x) x.begin(), x.end()
#define pb     push_back
#define fi     first
#define se     second
#define mp     make_pair

typedef long long ll;

const int lg = 12;
const int maxn5 = 2510;

int n, m;
vector <int> av;
ll ans = 0;
int lef[maxn5][maxn5], rig[maxn5][maxn5];
int dw[maxn5][maxn5], up[maxn5][maxn5];
pair <int, int> have[2][maxn5][maxn5], ex[2][maxn5][maxn5];


namespace rmqmn{
	int mn[lg][maxn5];
	void build(int n){
		for(int i = 1; i < lg; i++) for(int j = 0; j < n; j++)
			mn[i][j] = min(mn[i - 1][j], (j + (1 << (i - 1)) < n ? mn[i - 1][j + (1 << (i - 1))] : maxn5));
	}

	int get(int l, int r){
		if(r < l)
			return 0;
		int k = 31 - __builtin_clz(r - l + 1);
		return min(mn[k][l], mn[k][r - (1 << k) + 1]);
	}
}

namespace rmqmx{
	int mx[lg][maxn5];
	void build(int n){
		for(int i = 1; i < lg; i++) for(int j = 0; j < n; j++)
			mx[i][j] = max(mx[i - 1][j], (j + (1 << (i - 1)) < n ? mx[i - 1][j + (1 << (i - 1))] : maxn5));
	}

	int get(int l, int r){
		if(r < l)
			return 0;
		int k = 31 - __builtin_clz(r - l + 1);
		return max(mx[k][l], mx[k][r - (1 << k) + 1]);
	}
}

namespace fen{
	int fen[maxn5];
	ll all = 0;

	void add(int id, int val){
		all += val;
		for(id += 5; id < maxn5; id += id & -id)
			fen[id] += val;
	}

	int get(int id){
		int ret = 0;
		for(id += 4; id; id -= id & -id)
			ret += fen[id];
		////////cout << id << ' ' << all << ' ' << ret << endl;
		return all - ret;
	}
}

namespace anscalcer{

	vector <pair<int, int>> req[2], rem;

	void clear(){
		req[0].clear();
		req[1].clear();
		rem.clear();
	}

	void add(int ty, int l, int r){
		//cout << "here " << ty << ' ' << l << ' ' << r << endl;
		if(ty){
			req[ty].pb({l, r});
			rem.pb({r, l});
		}
		else{
			req[ty].pb({r, l});
		}
	}

	void calc(){
		sort(all(req[0]));
		sort(all(req[1]));
		sort(all(rem));

		int ind = 0, ind2 = 0;
		for(auto [r, l] : req[0]){
			while(ind < req[1].size() && req[1][ind].fi + 2 <= r){
				fen::add(req[1][ind].fi, 1);
				//cout << "adding " << req[1][ind].fi << endl;
				ind++;
			}
			while(ind2 < rem.size() && rem[ind2].fi < r){
				fen::add(rem[ind2].se, -1);
				ind2++;
			}
			ans += fen::get(l);
			//cout << l << ' ' << r << ' ' << fen::get(l) << ' ' << ans << endl;
		}
		while(ind < req[1].size()){
			fen::add(req[1][ind].fi, 1);
			ind++;
		}
		while(ind2 < rem.size()){
			fen::add(rem[ind2].se, -1);
			ind2++;
		}
	}
}

bool exi(int id, int l, int r){
	return id >= 0 && id < n && (lef[id][r] == l || rig[id][l] == r);
}

pair <int, int> get_val(int id, int l, int r, int last){
	//////cout << id << ' ' << l << ' ' << r << endl;
	if(lef[id][r] == l)
		return have[0][id][r];
	if(rig[id][l] == r) 
		return have[1][id][l];
	//////cout << "no " << endl;
	if(id < last){
		if(id + 1 < n && rig[id + 1][l] == r)
			return ex[1][id + 1][l];
		//////cout << "now " << endl;
		if(id + 1 < n && lef[id + 1][r] == l)
			return ex[0][id + 1][r];
		////cout << "ridi " << endl;

	}
	//////cout << "and " << endl;
		if(id && rig[id - 1][l] == r)
			return ex[1][id - 1][l];
		//////cout << "ha " << endl;
		if(id && lef[id - 1][r] == l)
			return ex[0][id - 1][r];
}


void solve(int id, int l, int r){
	//////cout << "ha? " << id << ' ' << l << ' ' << r << endl;
	if(id > 1 && exi(id - 1, l, r))
		return;
	int rq = id + 1;
	while(rq < n - 1 && exi(rq, l, r))
		rq++;
	anscalcer::clear();
	//cout << "solve of " << id << ' ' << rq << ' ' << l << ' ' << r << endl;
	for(int i = max(0, id - 1); i <= rq; i++){
		pair <int, int> ret = get_val(i, l, r, id);
		//cout << "** " << i << ' ' << ret.fi << ' ' << ret.se << endl;
		if(ret.fi + 1 < i && i >= id)
			anscalcer::add(0, ret.fi, i);
		if(i + 1 < ret.se && i < rq)
			anscalcer::add(1, i, ret.se);
	}
	anscalcer::calc();
	//cout << "finally " << ans << endl;
	return;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	n = a.size();
	m = a[0].size();
	memset(up, -1, sizeof up);
	if(min(n, m) < 3)
		return 0;
	for(int j = 0; j < m; j++){
		av.clear();
		for(int i = 0; i < n; i++){
			while(av.size() && a[av.back()][j] < a[i][j]){
				dw[av.back()][j] = i;
				av.pop_back();
			}
			dw[i][j] = n;
			if(av.size()){
				if(a[av.back()][j] == a[i][j]){
					up[i][j] = av.back();
					dw[av.back()][j] = i;
					av.pop_back();
				}
				else
					up[i][j] = av.back();
			}
			av.pb(i);
		}
	}
	memset(lef, -1, sizeof lef);
	for(int i = 0; i < n; i++){
		av.clear();
		for(int j = 0; j < m; j++){
			rig[i][j] = m;
			while(av.size() && a[i][av.back()] < a[i][j]){
				rig[i][av.back()] = j;
				av.pop_back();
			}
			if(av.size()){
				////////////////cout << i << ' ' << j << ' ' << av.back() << ' ' << a[i][av.back()] << endl;
				if(a[i][av.back()] == a[i][j]){
					lef[i][j] = av.back();
					rig[i][av.back()] = j;
					av.pop_back();
				}
				else
					lef[i][j] = av.back();
			}
			av.pb(j);
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			rmqmx::mx[0][j] = up[i][j];
			rmqmn::mn[0][j] = dw[i][j];
		}
		rmqmx::build(m);
		rmqmn::build(m);
		for(int j = 0; j < m; j++){
			//////////////cout << i << ' ' << j << endl;
			if(lef[i][j] != -1){
				have[0][i][j].fi = rmqmx::get(lef[i][j] + 1, j - 1);
				have[0][i][j].se = rmqmn::get(lef[i][j] + 1, j - 1);
			}
			//else{
				if(i && lef[i - 1][j] != -1)
					ex[0][i - 1][j].fi = rmqmx::get(lef[i - 1][j] + 1, j - 1);
				if(i + 1 < n && lef[i + 1][j] != -1)
					ex[0][i + 1][j].se = rmqmn::get(lef[i + 1][j] + 1, j - 1);
			//}
			if(rig[i][j] != -1){
				have[1][i][j].fi = rmqmx::get(j + 1, rig[i][j] - 1);
				have[1][i][j].se = rmqmn::get(j + 1, rig[i][j] - 1);
			}
			//else{
				if(i && rig[i - 1][j] != -1)
					ex[1][i - 1][j].fi = rmqmx::get(j + 1, rig[i - 1][j] - 1);
				if(i + 1 < n && rig[i + 1][j] != -1)
					ex[1][i + 1][j].se = rmqmn::get(j + 1, rig[i + 1][j] - 1);

			//}
		}
	}

	for(int i = 1; i < n - 1; i++) for(int j = 0; j < m; j++){
		//////////////cout << "*** " << i << ' ' << j << ' ' << lef[i][j] << ' ' << rig[i][j] << ' ' << up[i][j] << ' ' << dw[i][j] << endl;
		if(lef[i][j] != -1 && (j != rig[i][lef[i][j]]) && lef[i][j] + 1 < j){
			//////////////////cout << "hmm " << rig[i][lef[i][j]] << endl;
			solve(i, lef[i][j], j);
		}
		if(rig[i][j] < m && j + 1 < rig[i][j])
			solve(i, j, rig[i][j]);
	}
	return ans;

}

Compilation message (stderr)

rect.cpp: In function 'void anscalcer::calc()':
rect.cpp:105:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    while(ind < req[1].size() && req[1][ind].fi + 2 <= r){
      |          ~~~~^~~~~~~~~~~~~~~
rect.cpp:110:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |    while(ind2 < rem.size() && rem[ind2].fi < r){
      |          ~~~~~^~~~~~~~~~~~
rect.cpp:117:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |   while(ind < req[1].size()){
      |         ~~~~^~~~~~~~~~~~~~~
rect.cpp:121:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   while(ind2 < rem.size()){
      |         ~~~~~^~~~~~~~~~~~
rect.cpp: In function 'std::pair<int, int> get_val(int, int, int, int)':
rect.cpp:154:1: warning: control reaches end of non-void function [-Wreturn-type]
  154 | }
      | ^

• 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: 28 / 28