Submission #307979

#	Time	Username	Problem	Language	Result	Execution time	Memory
307979		AngelKnows	Rectangles (IOI19_rect)	C++14	72 / 100	5142 ms	995352 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() {
	int sz;
	FOR(i,n) FOR(j,m) {
		vector<int> &v=e[i][j];
		sz=v.size();
		FOR(k,sz/2) {
			swap(v[k-1],v[sz-k]);
		}
		//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];
		sz=v.size();
		FOR(k,sz/2) {
			swap(v[k-1],v[sz-k]);
		}
		//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,old_r;
	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,old_l=old_r=0;
		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) {
						old_l=l,old_r=r;
						l++;r--;
						e[i][l].pb(r);
					}
				}
				for (int k=p;k<=j;k++) {
					pos=b[k].pos;
					add(pos,pos,m);
				}
				p=j+1,old_l=old_r=0;
			}
		}
	}
	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,old_l=old_r=0;
		FOR(i,n) {
			if (i==n||b[i].v!=b[i+1].v) {
				for (int k=p;k<=i;k++) {
					pos=b[k].pos;
					if (old_l<=pos&&pos<=old_r) continue;
					l=getmax(pos);
					r=getmin(pos,n);
					if (l!=0&&r!=inf) {
						old_l=l,old_r=r;
						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,old_l=old_r=0;
			}
		}
	}
}
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;
}
/*
class InputReader {
private:
	static const int SIZE = 4096;
	
	int inputFileDescriptor;
	char buf[SIZE];
	int curChar;
	int numChars;
 
public:
 
	inline InputReader(int _inputFileDescriptor):
		inputFileDescriptor(_inputFileDescriptor),
		curChar(0),
		numChars(0) {
	}
 
	inline void close() {
		::close(inputFileDescriptor);
	}
 
	inline char read() {
		assert(numChars != -1);
		if (curChar >= numChars) {
			curChar = 0;
			numChars = ::read(inputFileDescriptor, buf, SIZE);
			if (numChars == -1)
				return -1;
		}
		return buf[curChar++];
	}
 
	inline int readInt() {
		int c = eatWhite();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			assert(c >= '0' && c <= '9');
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
 
	inline string readString() {
		char c = eatWhite();
		string res;
		do {
			res += c;
			c = read();
		} while (!isSpaceChar(c));
		return res;
	}
 
	inline string readLine() {
		string res;
		while (true) {
			char c = read();
			if (c == '\n' || c == '\r' || c == -1)
				break;
			res += c;
		}
		return res;
	}
 
	inline char eatWhite() {
		char c = read();
		while (isSpaceChar(c)) 
			c = read();
		return c;
	}
 
	static inline bool isSpaceChar(char c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}
};
 
 
int main() {
	InputReader inputReader(STDIN_FILENO);
	int n, m;
	n = inputReader.readInt();
	m = inputReader.readInt();
	vector<vector<int>> a(n, vector<int>(m));
	for (int i = 0; i < n; i++)	{
		for (int j = 0; j < m; j++) {
			a[i][j] = inputReader.readInt();
		}
	}
	inputReader.close();
 
	long long result = count_rectangles(a);
 
	printf("%lld\n", result);
	fclose(stdout);
	return 0;
}*/

Compilation message (stderr)

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

• 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