Submission #347696

#	Time	Username	Problem	Language	Result	Execution time	Memory
347696		ryansee	Rectangles (IOI19_rect)	C++14	72 / 100	5068 ms	1016140 KiB

rect

#include "rect.h"

#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=int; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (2503)

ll r, c, A[MAXN][MAXN];

struct grid {
	short r, l, u, d;
} G[MAXN][MAXN], P[MAXN][MAXN];
set<dpi> s;

short tmp[MAXN];
struct _st {
	short st[12][MAXN];
	void build() {
		FOR(i,1,MAXN-1) st[0][i]=tmp[i];
		FOR(h,1,11) for(ll i=1;i+(1<<h)-1<MAXN;++i) {
			st[h][i] = min(st[h-1][i], st[h-1][i+(1<<(h-1))]);
		}
	}
	int lg2(int x) {
		return 31 ^ __builtin_clz(x);  // ll has 2^64 - 1 so 63 bits
	}
	short query(int x, int y) { // inclusive in this case
		int p = lg2(y-x+1);
		return min(st[p][x], st[p][y-(1<<p)+1]);
	}
} R[MAXN], L[MAXN], U[MAXN], D[MAXN];

// #define gc getchar_unlocked
// inline ll in() {
	// char ch=gc();
	// ll x=0;
	// while(ch<'0'||ch>'9') ch=gc();
	// while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch&15),ch=gc();
	// return x;
// }

int main2() {
	// FAST
	// r=in(), c=in();
	// FOR(i,1,r) FOR(j,1,c) A[i][j]=in();
	vector<pi> v;
	
	FOR(j,1,c) {
		v.clear();
		DEC(i,r,1) {
			while(v.size() && v.back().f < A[i][j]) v.pop_back();
			G[i][j].d = v.size() ? v.back().s : r + 1;
			v.eb(A[i][j], i);
		}
	}
	FOR(j,1,c) {
		v.clear();
		FOR(i,1,r) {
			while(v.size() && v.back().f < A[i][j]) v.pop_back();
			G[i][j].u = v.size() ? v.back().s : 0;
			v.eb(A[i][j], i);
		}
	}
	FOR(i,1,r) {
		v.clear();
		DEC(j,c,1) {
			while(v.size() && v.back().f < A[i][j]) v.pop_back();
			G[i][j].r = v.size() ? v.back().s : c + 1;
			v.eb(A[i][j], j);
		}
	}
	FOR(i,1,r) {
		v.clear();
		FOR(j,1,c) {
			while(v.size() && v.back().f < A[i][j]) v.pop_back();
			G[i][j].l = v.size() ? v.back().s : 0;
			v.eb(A[i][j], j);
		}
	}
	
	
	FOR(j,1,c) {
		v.clear();
		DEC(i,r,1) {
			while(v.size() && v.back().f < A[i][j]) v.pop_back();
			P[i][j].d = v.size() ? v.back().s : r + 1;
			v.eb(A[i][j], i);
		}
	}
	FOR(j,1,c) {
		v.clear();
		FOR(i,1,r) {
			while(v.size() && v.back().f <= A[i][j]) v.pop_back();
			P[i][j].u = v.size() ? v.back().s : 0;
			v.eb(A[i][j], i);
		}
	}
	FOR(i,1,r) {
		v.clear();
		DEC(j,c,1) {
			while(v.size() && v.back().f < A[i][j]) v.pop_back();
			P[i][j].r = v.size() ? v.back().s : c + 1;
			v.eb(A[i][j], j);
		}
	}
	FOR(i,1,r) {
		v.clear();
		FOR(j,1,c) {
			while(v.size() && v.back().f <= A[i][j]) v.pop_back();
			P[i][j].l = v.size() ? v.back().s : 0;
			v.eb(A[i][j], j);
		}
	}
	
	// FOR(i,1,r) {
		// FOR(j,0,MAXN-1) tmp[j] = A[i][j];
		// row[i].build();
	// }
	
	// FOR(j,1,c) {
		// FOR(i,0,MAXN-1) tmp[i] = A[i][j];
		// col[j].build();
	// }
	
	FOR(i,1,r) {
		FOR(j,0,MAXN-1) tmp[j] = -G[i][j].u;
		U[i].build();
		FOR(j,0,MAXN-1) tmp[j] = G[i][j].d;
		D[i].build();
	}
	
	FOR(j,1,c) {
		FOR(i,0,MAXN-1) tmp[i] = G[i][j].r;
		R[j].build();
		FOR(i,0,MAXN-1) tmp[i] = -G[i][j].l;
		L[j].build();
	}
	
	int ans = 0;
	v.clear();
	FOR(i,1,r) FOR(j,1,c) v.eb(i, j);
	sort(all(v), [](pi x,pi y){return A[x.f][x.s] > A[y.f][y.s];});
	for(auto k:v) {
		ll i=k.f, j=k.s;
		int r1,c1,r2,c2;
		r1 = P[i][j].u, r2 = P[i][j].d, c1 = P[i][j].l, c2 = P[i][j].r;
		if(r1 == 0 || r2 == r + 1 || c1 == 0 || c2 == c+1 || s.find(dpi(pi(r1, c1),pi(r2, c2))) != s.end()) continue;
		s.ins(dpi(pi(r1, c1),pi(r2, c2)));
		
		bool okay = 1;
		// FOR(r,r1+1,r2-1) okay &= A[r][c1] > A[i][j], okay &= A[r][c2] > A[i][j], 
			// okay &= G[r][c1].r >= c2, okay &= G[r][c2].l <= c1;
		// okay &= col[c1].query(r1+1, r2-1) > A[i][j], okay &= col[c2].query(r1+1, r2-1) > A[i][j];
		okay &= R[c1].query(r1+1, r2-1) >= c2, okay &= -L[c2].query(r1+1, r2-1) <= c1;
		// FOR(c,c1+1,c2-1) okay &= A[r1][c] > A[i][j], okay &= A[r2][c] > A[i][j], 
			// okay &= G[r1][c].d >= r2, okay &= G[r2][c].u <= r1;
		// okay &= row[r1].query(c1+1, c2-1) > A[i][j], okay &= row[r2].query(c1+1, c2-1) > A[i][j];
		okay &= D[r1].query(c1+1, c2-1) >= r2, okay &= -U[r2].query(c1+1, c2-1) <= r1;
		
		ans += okay;
		// if(okay) {
			// cerr<<r1<<' '<<c1<<' '<<r2<<' '<<c2<<' '<<i<<' '<<j<<'\n';
		// }
	}
	return ans;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	r = siz(a), c = siz(a[0]);
	FOR(i,1,r)FOR(j,1,c)A[i][j]=a[i-1][j-1];
	return main2();
}

• 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