Submission #211827

#	Time	Username	Problem	Language	Result	Execution time	Memory
211827		MarcoMeijer	Rectangles (IOI19_rect)	C++14	72 / 100	2766 ms	1048580 KiB

rect

#include <bits/stdc++.h>
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MX=2510;
int n, m;
vii areasHor[MX];
set<int> heights[MX][MX];
ll ans=0;
int oldMLast[MX][MX];
int oldMVal[MX][MX];
vector<pair<ii, int>> queries[MX*4];
set<int> sts[MX];

void addQuery(pair<ii, int> q, int p=0, int l=0, int r=m-1) {
	if(q.fi.se < l || q.fi.fi > r) return;
	int md=(l+r)/2;
	if(l == r || (q.fi.fi <= md && q.fi.se >= md+1)) {
		queries[p].pb(q);
		return;
	}
	addQuery(q,p*2+1,l,md);
	addQuery(q,p*2+2,md+1,r);
}
void addAns(int i, int p=0, int l=0, int r=m-1) {
	if(l == r) {
		for(auto q : queries[p]) {
			for(int j : heights[i][q.fi.fi]) {
				if(j >= q.se) ans++;
			}
		}
		return;
	}
	int md=(l+r)/2;
	if(!queries[p].empty()) {
		sts[md] = heights[i][md];
		REV(j,l,md) {
			sts[j].clear();
			set_intersection(sts[j+1].begin(), sts[j+1].end(), heights[i][j].begin(), heights[i][j].end(), inserter(sts[j], sts[j].end()));
		}
		sts[md+1] = heights[i][md+1];
		REP(j,md+2,r+1) {
			sts[j].clear();
			set_intersection(sts[j-1].begin(), sts[j-1].end(), heights[i][j].begin(), heights[i][j].end(), inserter(sts[j], sts[j].end()));
		}
	}
	for(auto q : queries[p]) {
		set<int> s;
		int a=q.fi.fi, b=q.fi.se;
		set_intersection(sts[a].begin(),sts[a].end(),sts[b].begin(),sts[b].end(),inserter(s,s.end()));
		for(int j : s) {
			if(j >= q.se) ans++;
		}
	}
	addAns(i,p*2+1,l,md);
	addAns(i,p*2+2,md+1,r);
}
long long count_rectangles(vector<vector<int>> a) {
	n = a.size();
	m = a[0].size();
	RE(i,n) {
		stack<int> stck;
		RE(j,m) {
			while(!stck.empty() && a[i][stck.top()] < a[i][j]) {
				int v = a[i][stck.top()];
				stck.pop();
				if(!stck.empty() && v != a[i][stck.top()]) areasHor[i].pb({stck.top()+1,j-1});
			}
			stck.push(j);
		}
	}
	RE(j,m) {
		stack<int> stck;
		RE(i,n) {
			while(!stck.empty() && a[stck.top()][j] < a[i][j]) {
				int v = a[stck.top()][j];
				stck.pop();
				if(!stck.empty() && v != a[stck.top()][j]) heights[i-1][j].insert(stck.top()+1);
			}
			stck.push(i);
		}
	}
	RE(i,MX) RE(j,MX) oldMVal[i][j] = -2, oldMLast[i][j] = -2;
	RE(i,n) {
		RE(j,m*4) queries[j].clear();
		for(ii p : areasHor[i]) {
			pair<ii, int> ans;
			ans.fi = p;
			ans.se = i;
			if(oldMLast[p.fi][p.se] == i-1) {
				ans.se = oldMVal[p.fi][p.se];
			} else {
				oldMVal[p.fi][p.se] = i;
			}
			oldMLast[p.fi][p.se] = i;
			addQuery(ans);
		}
		addAns(i);
	}
	return ans;
}

• 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