Submission #723272

#	Time	Username	Problem	Language	Result	Execution time	Memory
723272		myrcella	Rectangles (IOI19_rect)	C++17	72 / 100	5098 ms	591632 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];
set <pii> hi[maxn];
int tree[maxn][maxn];
stack <int> q;

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];
	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].insert({q.top(),j});
			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].insert({j,q.top()});
			q.push(j);
		}
	}
	rep(i,1,N-1) {
		for (auto it:hi[i]) {
			int cur = i+1;
			while (cur<N-1 and hi[cur].find(it)!=hi[cur].end()) {
				hi[cur].erase(it);
				cur++;
			}
			rep(j,i,cur) row1[j].pb({{it.fi+1,it.se-1},cur-1});
		}
		hi[i].clear();
		sort(ALL(row1[i]));
	}
	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].insert({q.top(),j});
			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].insert({j,q.top()});
			q.push(j);
		}
	}
	rep(i,1,M-1) {
		for (auto it:hi[i]) {
			int cur = i+1;
			while (cur<M-1 and hi[cur].find(it)!=hi[cur].end()) {
				hi[cur].erase(it);
				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: 0 / 28