Submission #307957

#	Time	Username	Problem	Language	Result	Execution time	Memory
307957		AngelKnows	Rectangles (IOI19_rect)	C++14	0 / 100	2357 ms	778292 KiB

rect

#include "rect.h"
#include <cstdio>
#include <unistd.h>
#include <cassert>
#include <string>
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
 
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
 
typedef long long ll;
 
const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=2500+1;
const double eps=1e-5;
const int mo=1e9+7;
 
int n,m;
ll a[N][N];
struct node {
	int pos;
	ll v;
};
node b[N];
int c[N],c2[N];
vector<int> e[N][N],e2[N][N];
bool cmp(node x,node y) {
	if (x.v==y.v) return x.pos<y.pos;
	return x.v>y.v;
}
vector<node> bit_q[N][N]; // q的树状数组 
int l_max[N][N],u_max[N][N];
struct point {
	int x,y;
};
vector<point> Q[N][N];
int far_up[N][N];
ll res;
int lowbit(int x) {
	return x&-x;
}
void add(int x,int v,int len) {
	int t=x;
	while (x<=len) {
		c[x]=max(c[x],v);
		x+=lowbit(x);
	}
	x=len-t+1;
	while (x<=len) {
		c2[x]=min(c2[x],v);
		x+=lowbit(x);
	}
}
int getmax(int x) {
	int ans=0;
	while (x>=1) {
		ans=max(ans,c[x]);
		x-=lowbit(x);
	}
	return ans;
}
int getmin(int x,int len) {
	x=len-x+1;
	int ans=inf;
	while (x>=1) {
		ans=min(ans,c2[x]);
		x-=lowbit(x);
	}
	return ans;
}
void uniquelize() {
	FOR(i,n) FOR(j,m) {
		vector<int> &v=e[i][j];
		sort(v.begin(),v.end());
		//v.erase(unique(v.begin(),v.end()),v.end());
	}
	FOR(i,m) FOR(j,n) {
		vector<int> &v=e2[i][j];
		sort(v.begin(),v.end(),greater<int>());
		//v.erase(unique(v.begin(),v.end()),v.end());
	}
}
void get_valid_interval() {
	int p,pos,l,r,old_l=0,old_r=0;
	FOR(i,n) {
		FOR(j,m) c[j]=0,c2[j]=inf;
		FOR(j,m) b[j].pos=j,b[j].v=a[i][j];
		sort(b+1,b+1+m,cmp);
		p=1;
		FOR(j,m) {
			if (j==m||b[j].v!=b[j+1].v) {
				for (int k=p;k<=j;k++) {
					pos=b[k].pos;
					if (old_l<=pos&&pos<=old_r) continue;
					l=getmax(pos);
					r=getmin(pos,m);
					if (l!=0&&r!=inf) {
						l++;r--;
						e[i][l].pb(r);
						old_l=l,old_r=r;
					}
				}
				for (int k=p;k<=j;k++) {
					pos=b[k].pos;
					add(pos,pos,m);
				}
				p=j+1;
			}
		}
	}
	FOR(j,m) {
		FOR(i,n) c[i]=0,c2[i]=inf;
		FOR(i,n) b[i].pos=i,b[i].v=a[i][j];
		sort(b+1,b+1+n,cmp);
		p=1;
		FOR(i,n) {
			if (i==n||b[i].v!=b[i+1].v) {
				for (int k=p;k<=i;k++) {
					pos=b[k].pos;
					l=getmax(pos);
					r=getmin(pos,n);
					if (l!=0&&r!=inf) {
						l++;r--;
						e2[j][r].pb(l);
					}
				}
				for (int k=p;k<=i;k++) {
					pos=b[k].pos;
					add(pos,pos,n);
				}
				p=i+1;
			}
		}
	}
}
void get_Q(){
	int x,y,sz;
	FOR(i,n) {
		FOR(j,m) {
			sz=int(e2[j][i].size());
			y=j;
			for (int k=0;k<sz;k++) {
				x=e2[j][i][k];
				l_max[x][y]=l_max[x][y-1]+1;
				Q[x][y-l_max[x][y]+1].pb(point{i,j});
			}
		}
		FOR(j,m) {
			sz=int(e2[j][i].size());
			y=j;
			for (int k=0;k<sz;k++) {
				x=e2[j][i][k];
				l_max[x][y]=0;
			}
		}
	}
}
void get_bit_q() {
	int sz;
	FOR(i,n) FOR(j,m) {
		sz=int(e2[j][i].size());
		for (int k=0;k<sz;k++) {
			bit_q[i][j].pb(node{e2[j][i][k],0});
		}
	}
}
void add2(vector<node> &a,int x,int v) {
	int sz=int(a.size());
	while (x<=sz) {
		a[x-1].v+=v;
		x+=lowbit(x);
	}
}
int getsum(vector<node> &a,int x) {
	int ans=0;
	while (x>=1) {
		ans+=a[x-1].v;
		x-=lowbit(x);
	}
	return ans;
}
long long count_rectangles(std::vector<std::vector<int> > aa) {
	n=aa.size();
	m=aa[0].size();
	FOR(i,n) {
		FOR(j,m) {
			a[i][j]=aa[i-1][j-1];
		}
	}
	get_valid_interval();
	uniquelize();
	get_Q();
	get_bit_q();
	int sz,x,y,px,py,l,r,mid,ok_mid;
	point q;
	FOR(j,m) {
		FOR(i,n) {
			sz=int(e[i][j].size());
			x=i;
			for (int k=0;k<sz;k++) {
				y=e[i][j][k];
				u_max[x][y]=u_max[x-1][y]+1;
				far_up[x][y]=x-u_max[x][y]+1;
			}
		}
		FOR(i,n) {
			sz=int(e[i][j].size());
			x=i;
			for (int k=0;k<sz;k++) {
				y=e[i][j][k];
				u_max[x][y]=0;
			}
		}
		FOR(i,n) {
			sz=Q[i][j].size();
			for (int k=0;k<sz;k++) {
				q=Q[i][j][k];
				x=q.x,y=q.y;
				px=i,py=q.y;
				l=1,r=int(e2[y][x].size());
				ok_mid=0;
				// 找最小的>=px的数字
				
				while (l<=r) {
					mid=(l+r)/2;
					if (e2[y][x][mid-1]>=px) {
						l=mid+1;
						ok_mid=mid;
					} else r=mid-1;
				}
				if (ok_mid) add2(bit_q[x][y],ok_mid,1);
			}
		}
		FOR(i,n) {
			sz=int(e[i][j].size());
			for (int k=0;k<sz;k++) {
				y=e[i][j][k];
				l=1,r=int(e2[y][i].size());
				ok_mid=0;
				while (l<=r) {
					mid=(l+r)/2;
					if (e2[y][i][mid-1]>=far_up[i][y]) {
						l=mid+1;
						ok_mid=mid;
					} else r=mid-1;
				}
				if (ok_mid) {
					res+=getsum(bit_q[i][y],ok_mid);
				}
			}
		}
	}
	return res;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:201:16: warning: variable 'py' set but not used [-Wunused-but-set-variable]
  201 |  int sz,x,y,px,py,l,r,mid,ok_mid;
      |                ^~

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