Submission #430071

#	Time	Username	Problem	Language	Result	Execution time	Memory
430071		egekabas	Rectangles (IOI19_rect)	C++14	59 / 100	5066 ms	229644 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int bit[2509][2509];
int bitsz;
void upd(int x, int y, int val){
	for(int i1 = x+1; i1 > 0; i1 -= i1&(-i1))
		for(int i2 = y+1; i2 <= bitsz; i2 += i2&(-i2))
			bit[i1][i2] += val;
}
int get(int x, int y){
	int ret = 0;
	for(int i1 = x+1; i1 <= bitsz; i1 += i1&(-i1))
		for(int i2 = y+1; i2 > 0; i2 -= i2&(-i2))
			ret += bit[i1][i2];
	return ret;
}
ll pickdouble(int n){
	return ll(n)*(n+1)/2;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size(), m = a[0].size();
	bitsz = max(n, m);
	for(int i = 1; i <= bitsz; ++i)
		for(int j = 1; j <= bitsz; ++j)
			bit[i][j] = 0;
	
	vector<set<pii>> pos(n);
	for(int i = 0; i < n; ++i){
		vector<int> cur;
		for(int j = m-1; j >= 0; --j){
			while(cur.size() && a[i][cur.back()] < a[i][j]){
				pos[i].insert({j, cur.back()});
				cur.pop_back();
			}
			if(cur.size())
				pos[i].insert({j, cur.back()});
			while(cur.size() && a[i][cur.back()] <= a[i][j])
				cur.pop_back();
			
			cur.pb(j);
		}
	}
	vector<vector<pair<pii, int>>> maxval(m);
	for(int i = 0; i < n; ++i)
		for(auto u : pos[i]){
			int j;
			for(j = i+1; j < n; ++j){
				auto it = pos[j].lower_bound(u);
				if(it == pos[j].end() || *it != u)
					break;
				pos[j].erase(it);
			}
			--j;
			if(u.ss-u.ff > 1)
				maxval[u.ff].pb({{i, j}, u.ss});
			//cout << u.ff << ' ' << u.ss << ' ' << i << ' ' << j << '\n';
		}
	pos = vector<set<pii>>(m);
	for(int i = 0; i < m; ++i){
		vector<int> cur;
		for(int j = n-1; j >= 0; --j){
			while(cur.size() && a[cur.back()][i] < a[j][i]){
				pos[i].insert({j, cur.back()});
				cur.pop_back();
			}
			if(cur.size())
				pos[i].insert({j, cur.back()});
			while(cur.size() && a[cur.back()][i] <= a[j][i])
				cur.pop_back();
			
			cur.pb(j);
		}
	}
	vector<vector<pair<pii, int>>> fin(m);
	for(int i = 0; i < m; ++i)
		for(auto u : pos[i]){
			int j;
			for(j = i+1; j < m; ++j){
				auto it = pos[j].lower_bound(u);
				if(it == pos[j].end() || *it != u)
					break;
				pos[j].erase(it);
			}
			--j;
			if(u.ss-u.ff > 1)
				for(int k = i; k <= j; ++k)
					fin[k].pb({{u.ff, u.ss}, j});
		}
	ll ans = 0;
	for(int i = 1; i < m; ++i){
		sort(all(fin[i]));
		sort(all(maxval[i-1]));
		int curidx = 0;
		for(auto u : fin[i]){
			while(curidx < (int)maxval[i-1].size() && maxval[i-1][curidx].ff.ff <= u.ff.ff+1){
				upd(maxval[i-1][curidx].ff.ss, maxval[i-1][curidx].ss, 1);
				++curidx;
			}
			int val = get(u.ff.ss-1, u.ss+1);
			//cout << i << ' ' << u.ss << ' ' << u.ff.ff << ' ' << u.ff.ss << ' ' << val << '\n';
			ans += val;
		}
		for(int j = 0; j < curidx; ++j)
			upd(maxval[i-1][j].ff.ss, maxval[i-1][j].ss, -1);
	}
	return ans;
}

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