Submission #956974

#	Time	Username	Problem	Language	Result	Execution time	Memory
956974		Macker	Rectangles (IOI19_rect)	C++17	72 / 100	2318 ms	1048576 KiB

rect

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)

struct node{
	int on = 0, mxx, mnx, mxy, mny;
};
vector<vector<node>> st;
int lenx = 1, leny = 1;
node zero({1, 0, INT_MAX/2, 0, INT_MAX/2});

vector<int> get_last_big(vector<int> v){
	int n = v.size();
	vector<int> res(n, -1);
	stack<pii> s;
	s.push({INT_MAX/2, -1});
	FOR(i, n){
		int a = v[i];
		while(a >= s.top().ff) s.pop();
		res[i] = s.top().ss;
		s.push({a, i});
	}
	return res;
}

node comb(node a, node b){
	node res;
	res.on = min(a.on, b.on);
	res.mnx = min(a.mnx, b.mnx);
	res.mny = min(a.mny, b.mny);
	res.mxx = max(a.mxx, b.mxx);
	res.mxy = max(a.mxy, b.mxy);
	return res;
}

void updy(int y, node val, int i, int j = 1, int s = 0, int e = leny){
	if(y < s || y >= e) return;
	if(y == s && s + 1 == e) {
		if(i >= lenx) st[i][j] = val;
		else st[i][j] = comb(st[i * 2][j], st[i * 2 + 1][j]);
		return;
	}

	updy(y, val, i, j * 2, s, (s + e) / 2);
	updy(y, val, i, j * 2 + 1, (s + e) / 2, e);
	st[i][j] = comb(st[i][j * 2], st[i][j * 2 + 1]);
}

void updx(int x, int y, node val, int i = 1, int s = 0, int e = lenx){
	if(x < s || x >= e) return;
	if(x == s && s + 1 == e) {updy(y, val, i); return;}

	updx(x, y, val, i * 2, s, (s + e) / 2);
	updx(x, y, val, i * 2 + 1, (s + e) / 2, e);
	
	updy(y, val, i);
}

node qryy(int l, int r, int i, int j = 1, int s = 0, int e = leny){
	if(l >= e || r <= s) return zero;
	if(l <= s && e <= r) return st[i][j];

	return comb(qryy(l, r, i, j * 2, s, (s + e) / 2),
				qryy(l, r, i, j * 2 + 1, (s + e) / 2, e));
}

node qryx(int xl, int xr, int yl, int yr, int i = 1, int s = 0, int e = lenx){
	if(xl >= e || xr <= s) return zero;
	if(xl <= s && e <= xr) return qryy(yl, yr, i);

	return comb(qryx(xl, xr, yl, yr, i * 2, s, (s + e) / 2),
				qryx(xl, xr, yl, yr, i * 2 + 1, (s + e) / 2, e));
}

long long count_rectangles_2(vector<vector<signed>> v) {
	int n = v.size();
	int m = v[0].size();
	st.assign(n, vector<node>(m));
 
	FOR(i, n){
		vector<int> cur;
		vector<int> res;
		FOR(j, m){
			cur.push_back(v[i][j]);
		}
		res = get_last_big(cur);
		FOR(j, m){
			st[i][j].mnx = res[j];
		}
		reverse(all(cur));
		res = get_last_big(cur);
		reverse(all(res));
		FOR(j, m){
			st[i][j].mxx = m - res[j] - 1;
		}
	}
	FOR(j, m){
		vector<int> cur;
		vector<int> res;
		FOR(i, n){
			cur.push_back(v[i][j]);
		}
		res = get_last_big(cur);
		FOR(i, n){
			st[i][j].mny = res[i];
		}
		reverse(all(cur));
		res = get_last_big(cur);
		reverse(all(res));
		FOR(i, n){
			st[i][j].mxy = n - res[i] - 1;
		}
	}
	
	vector<vector<pii>> ord(7000005);
	FOR(i, n) FOR(j, m){
		ord[v[i][j]].push_back({i, j});
	}
	ll res = 0;
	for (auto o : ord) {
		for (auto [x, y] : o) {
			st[x][y].on = true;
			int mxx, mnx, mxy, mny;
			mxx = st[x][y].mxx;
			mnx = st[x][y].mnx;
			mxy = st[x][y].mxy;
			mny = st[x][y].mny;
			if(mxx >= m || mxy >= n || mnx < 0 || mny < 0) continue;
 
			bool f = 0;
			for (int i = mny + 1; i < mxy; i++){
				for (int j = mnx + 1; j < mxx; j++) {
					if(!st[i][j].on) {f = 1; break;}
					if(st[i][j].mnx < mnx) {f = 1; break;}
					if(st[i][j].mny < mny) {f = 1; break;}
					if(st[i][j].mxx > mxx) {f = 1; break;}
					if(st[i][j].mxy > mxy) {f = 1; break;}
				}
				if(f) break;
			}
			if(!f) res++;
		}
	}
	return res;
}

long long count_rectangles(vector<vector<signed>> v) {
	int n = v.size();
	while(lenx < n) lenx *= 2;
	int m = v[0].size();
	while(leny < m) leny *= 2;

	int mxval = 0;
	FOR(i, n) FOR(j, m) mxval = max(mxval, v[i][j]);
	if(mxval < 2){
		return count_rectangles_2(v);
	}

	st.assign(2 * lenx, vector<node>(2 * leny));
	vector<vector<node>> passive(n, vector<node>(m));

	FOR(i, n){
		vector<int> cur;
		vector<int> res;
		FOR(j, m){
			cur.push_back(v[i][j]);
		}
		res = get_last_big(cur);
		FOR(j, m){
			passive[i][j].mnx = res[j];
		}
		reverse(all(cur));
		res = get_last_big(cur);
		reverse(all(res));
		FOR(j, m){
			passive[i][j].mxx = m - res[j] - 1;
		}
	}
	FOR(j, m){
		vector<int> cur;
		vector<int> res;
		FOR(i, n){
			cur.push_back(v[i][j]);
		}
		res = get_last_big(cur);
		FOR(i, n){
			passive[i][j].mny = res[i];
		}
		reverse(all(cur));
		res = get_last_big(cur);
		reverse(all(res));
		FOR(i, n){
			passive[i][j].mxy = n - res[i] - 1;
		}
	}
	
	vector<vector<pii>> ord(mxval + 1);
	FOR(i, n) FOR(j, m){
		ord[v[i][j]].push_back({i, j});
	}
	ll res = 0;
	for (auto o : ord) {
		for (auto [x, y] : o) {
			passive[x][y].on = true;
			updx(x, y, passive[x][y]);

			int mnx = passive[x][y].mnx;
			int mny = passive[x][y].mny;
			int mxx = passive[x][y].mxx;
			int mxy = passive[x][y].mxy;

			if(mxx >= m || mxy >= n || mnx < 0 || mny < 0) continue;
			
			node ret = qryx(
				mny + 1,
				mxy,
				mnx + 1,
				mxx
			);
			bool f = 0;
			if(!ret.on) f = 1;
			if(ret.mnx < mnx) f = 1;
			if(ret.mny < mny) f = 1;
			if(ret.mxx > mxx) f = 1;
			if(ret.mxy > mxy) f = 1;

			if(!f)
				res++;
		}
	}
	return res;
}

• 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