Submission #308226

#	Time	Username	Problem	Language	Result	Execution time	Memory
308226		AngelKnows	Rectangles (IOI19_rect)	C++14	10 / 100	1000 ms	579320 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+10;
const double eps=1e-5;
const int mo=1e9+7;
 
int n,m;
int a[N][N];
int s[N],tail;
int l[N],r[N],pre[N];
vector<int> e[N][N],e2[N][N],e3[N][N];
int far_up[2][N][N],far_left[N][N];
int before[N];
int nxt[N];
ll res;
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];
	FOR(i,n) {
		FOR(j,m) l[j]=r[j]=pre[j]=0;
		tail=0;
		FOR(j,m) {
			while (tail>=1&&a[i][s[tail]]<=a[i][j]) tail--;
			if (tail>=1) l[j]=s[tail]+1;
			s[++tail]=j;
		}
		tail=0;
		for (int j=m;j>=1;j--) {
			while (tail>=1&&a[i][s[tail]]<a[i][j]) tail--;
			if (tail>=1) {
				if (a[i][j]==a[i][s[tail]]) {
					if (pre[tail]) r[j]=pre[tail]-1;
				} else {
					r[j]=s[tail]-1;
				}
			}
			s[++tail]=j;
			if (tail==1) pre[tail]=0;
			else if (a[i][j]!=a[i][s[tail-1]]) pre[tail]=s[tail-1];
			else pre[tail]=pre[tail-1];
		}
		FOR(j,m) if (l[j]&&r[j]) {
			e[i][l[j]].pb(r[j]);
			//printf("(%d,%d) (%d,%d)\n",i,l[j],i,r[j]);
			e3[i][r[j]].pb(l[j]);
		}
	}
	FOR(j,m) {
		FOR(i,n) l[i]=r[i]=pre[i]=0;
		tail=0;
		FOR(i,n) {
			while (tail>=1&&a[s[tail]][j]<=a[i][j]) tail--;
			if (tail>=1) l[i]=s[tail]+1;
			s[++tail]=i;
		}
		tail=0;
		for (int i=n;i>=1;i--) {
			while (tail>=1&&a[s[tail]][j]<a[i][j]) tail--;
			if (tail>=1) {
				if (a[i][j]==a[s[tail]][j]) {
					if (pre[tail]) r[i]=pre[tail]-1;
				} else {
					r[i]=s[tail]-1;
				}
			}
			s[++tail]=i;
			if (tail==1) pre[tail]=0;
			else if (a[i][j]!=a[s[tail-1]][j]) pre[tail]=s[tail-1];
			else pre[tail]=pre[tail-1];
		}
		FOR(i,n) if (l[i]&&r[i]) {
			e2[r[i]][j].pb(l[i]);
			//printf("(%d,%d) (%d,%d)\n",r[i],j,l[i],j);
		}
	}
	int head;
	FOR(i,n) {
		FOR(j,m) {
			for (int k=0;k<e[i][j].size();k++) {
				far_up[i%2][j][e[i][j][k]]=far_up[(i-1)%2][j][e[i][j][k]]+1;
			}
		}
		FOR(j,m) {
			for (int k=0;k<e2[i][j].size();k++) {
				far_left[e2[i][j][k]][j]=far_left[e2[i][j][k]][j-1]+1; 
			}
		}
		FOR(j,m) {
			head=e2[i][j].size()-1;
			for (int u=e2[i][j].size()-1;u>=0;u--) {
				before[u]=u+1;
				nxt[u]=u-1;
			}
			for (int k=e3[i][j].size()-1;k>=0;k--) {
				for (int u=head;u>=0;u=nxt[u]) {
					//if (far_up[i%2][e3[i][j][k]][j]<i-e2[i][j][u]+1) break;
					if (far_left[e2[i][j][u]][j]>=j-e3[i][j][k]+1) {
						res++;
					} else {
						if (before[u]!=e2[i][j].size()) nxt[before[u]]=nxt[u];
						if (nxt[u]>=0) before[nxt[u]]=before[u];
						if (u==head) head=nxt[u];
					}
				}
			}
		}
		FOR(j,m) {
			for (int k=0;k<e[i-1][j].size();k++) {
				far_up[(i-1)%2][j][e[i-1][j][k]]=0;
			}
		}
		FOR(j,m) {
			for (int k=0;k<e2[i][j].size();k++) {
				far_left[e2[i][j][k]][j]=0;
			}
		}
	}
	return res;
}

#ifdef DEBUG
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;
}
#endif

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |    for (int k=0;k<e[i][j].size();k++) {
      |                 ~^~~~~~~~~~~~~~~
rect.cpp:103:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |    for (int k=0;k<e2[i][j].size();k++) {
      |                 ~^~~~~~~~~~~~~~~~
rect.cpp:119:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |       if (before[u]!=e2[i][j].size()) nxt[before[u]]=nxt[u];
      |           ~~~~~~~~~^~~~~~~~~~~~~~~~~
rect.cpp:127:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |    for (int k=0;k<e[i-1][j].size();k++) {
      |                 ~^~~~~~~~~~~~~~~~~
rect.cpp:132:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |    for (int k=0;k<e2[i][j].size();k++) {
      |                 ~^~~~~~~~~~~~~~~~

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