Submission #723288

#	Time	Username	Problem	Language	Result	Execution time	Memory
723288		myrcella	Rectangles (IOI19_rect)	C++17	100 / 100	3234 ms	600740 KiB

rect

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

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

#include "rect.h"

int N,M;
const int maxn = 2555;
int grid[maxn][maxn];
vector <pair<pii,int> > row1[maxn];
vector <pii> row[maxn][maxn];
vector <pii> hi[maxn];
int tree[maxn][maxn];
stack <int> q;
int lft[maxn][maxn],rit[maxn][maxn];

void update(pii tmp,int val) {
	int pos = tmp.se;
	while (pos<maxn) {
		tree[tmp.fi][pos] += val;
		pos += lowbit(pos);
	}
	return;
}

int query(int id,int pos) {
	int ret = 0;
	while (pos) {
		ret += tree[id][pos];
		pos -= lowbit(pos);
	}
	return ret;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	N = SZ(a),M=SZ(a[0]);
	rep(i,0,N) rep(j,0,M) grid[i][j] = a[i][j];
	memset(lft,-1,sizeof(lft));memset(rit,-1,sizeof(rit));
	rep(i,1,N-1) {
		while (!q.empty()) q.pop();
		rep(j,0,M) {
			while (!q.empty() and a[i][q.top()]<a[i][j]) q.pop();
			if (!q.empty() and q.top()!=j-1) hi[i].pb({q.top(),j}),lft[i][j] = q.top();
			q.push(j);
		}
		while (!q.empty()) q.pop();
		for (int j = M-1;j>=0;j--) {
			while (!q.empty() and a[i][q.top()]<a[i][j]) q.pop();
			if (!q.empty() and q.top()!=j+1) hi[i].pb({j,q.top()}),rit[i][j] = q.top();
			q.push(j);
		}
	}
	rep(i,1,N-1) {
		for (auto it:hi[i]) {
			if (lft[i][it.se]!=it.fi and rit[i][it.fi]!=it.se) continue;
			if (lft[i][it.se]==it.fi) lft[i][it.se]=-1;
			if (rit[i][it.fi]==it.se) rit[i][it.fi] = -1;
			int cur = i+1;
			while (cur<N-1 and (lft[cur][it.se]==it.fi or rit[cur][it.fi]==it.se)) {
				if (lft[cur][it.se]==it.fi) lft[cur][it.se]=-1;
				if (rit[cur][it.fi]==it.se) rit[cur][it.fi] = -1;
				cur++;
			}
			rep(j,i,cur) row1[j].pb({{it.fi+1,it.se-1},cur-1});
		}
		while (!hi[i].empty()) hi[i].pop_back();
		sort(ALL(row1[i]));
	}
	memset(lft,-1,sizeof(lft));memset(rit,-1,sizeof(rit));
	rep(i,1,M-1) {
		while (!q.empty()) q.pop();
		rep(j,0,N) {
			while (!q.empty() and a[q.top()][i]<a[j][i]) q.pop();
			if (!q.empty() and q.top()!=j-1) hi[i].pb({q.top(),j}),lft[j][i] = q.top();
			q.push(j);
		}
		while (!q.empty()) q.pop();
		for (int j = N-1;j>=0;j--) {
			while (!q.empty() and a[q.top()][i]<a[j][i]) q.pop();
			if (!q.empty() and q.top()!=j+1) hi[i].pb({j,q.top()}),rit[j][i] = q.top();
			q.push(j);
		}
	}
	rep(i,1,M-1) {
		for (auto it:hi[i]) {
			if (lft[it.se][i]!=it.fi and rit[it.fi][i]!=it.se) continue;
			int cur = i+1;
			if (lft[it.se][i]==it.fi) lft[it.se][i] = -1;
			if (rit[it.fi][i]==it.se) rit[it.fi][i] = -1;
			while (cur<M-1 and (lft[it.se][cur]==it.fi or rit[it.fi][cur] == it.se)) {
				if (lft[it.se][cur]==it.fi) lft[it.se][cur] = -1;
				if (rit[it.fi][cur]==it.se) rit[it.fi][cur] = -1;
				cur++;
			}
			rep(j,i,cur) row[(it).fi+1][i].pb({j,(it).se-1});
		}
	}
	ll ans = 0;
	rep(i,1,N-1) {
		int cur = 1;
		vector <pii> tmp;
		for (auto it:row1[i]) {
			while (cur<=it.fi.fi) {
				for (auto itt:row[i][cur]) update(itt,1),tmp.pb(itt);
				cur++;
			}
			ans += query(it.fi.se,it.se);
//			cout<<it.fi.fi<<" "<<it.fi.se<<" "<<i<<" "<<it.se<<" "<<ans<<endl;
		}
		while (!tmp.empty()) update(tmp.back(),-1),tmp.pop_back();
	}
	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: 28 / 28