Submission #424985

#	Time	Username	Problem	Language	Result	Execution time	Memory
424985		alishahali1382	Rectangles (IOI19_rect)	C++14	100 / 100	4474 ms	265880 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O2, unroll-loops")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<", ";cerr<<"\n";}
#define pb push_back
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()

const int inf=1000001000; // 1e9
const ll INF=10000000010000000; // 1e16
const int mod=1000000007;
const int N=2510;

ll ans; // :(
int n, m, k, x, y, u, v, t;
int A[N][N];
int L[N][N], R[N][N], U[N][N], D[N][N];
vector<pii> vec[N];
int dwn[N][N<<1];

ll count_rectangles(vector<vector<int>> _A){
	n=SZ(_A);
	m=SZ(_A[0]);
	for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) A[i][j]=_A[i-1][j-1];
	for (int i=1; i<=n; i++){
		for (int j=1; j<=m; j++) for (L[i][j]=j-1; L[i][j] && A[i][L[i][j]]<A[i][j]; L[i][j]=L[i][L[i][j]]) ;
		for (int j=m; j; j--) for (R[i][j]=j+1; R[i][j]<=m && A[i][R[i][j]]<A[i][j]; R[i][j]=R[i][R[i][j]]) ;
	}
	for (int j=1; j<=m; j++){
		for (int i=1; i<=n; i++) for (U[i][j]=i-1; U[i][j] && A[U[i][j]][j]<A[i][j]; U[i][j]=U[U[i][j]][j]) ;
		for (int i=n; i; i--) for (D[i][j]=i+1; D[i][j]<=n && A[D[i][j]][j]<A[i][j]; D[i][j]=D[D[i][j]][j]) ;
	}
	// debug("LRDU built")
	for (int i=n; i; i--){
		for (int j=1; j<=m; j++){
			if (L[i][j] && j-L[i][j]>1) vec[i].pb({L[i][j], j});
			if (R[i][j]<=m && R[i][j]-j>1) vec[i].pb({j, R[i][j]});
		}
		sort(all(vec[i]));
		vec[i].resize(unique(all(vec[i]))-vec[i].begin());
		for (int j=0; j<SZ(vec[i]); j++){
			auto it=lower_bound(all(vec[i+1]), vec[i][j]);
			if (it==vec[i+1].end() || *it!=vec[i][j]) dwn[i][j]=i;
			else dwn[i][j]=dwn[i+1][it-vec[i+1].begin()];
		}
	}
	for (int j=2; j<m; j++){
		vector<pii> shit;
		for (int i=1; i<=n; i++){
			if (U[i][j]) shit.pb({U[i][j], i});
			if (D[i][j]<=n) shit.pb({i, D[i][j]});
		}
		sort(all(shit)); // why?
		shit.resize(unique(all(shit))-shit.begin());
		for (pii p:shit) if (p.second-p.first>1){
			int u=p.first, d=p.second;
			if (2<j && (U[d][j-1]==u || D[u][j-1]==d)) continue ; // already counted
			int l=j, r=l;
			while (r+1<m && (D[u][r+1]==d || U[d][r+1]==u)) r++; // O(nm) amortized
			vector<pii> shit2;
			l--, r++; // :clown:
			for (int i=l; i<=r; i++){
				if (l<=L[u+1][i]) shit2.pb({L[u+1][i], i});
				if (R[u+1][i]<=r) shit2.pb({i, R[u+1][i]});
			}
			sort(all(shit2));
			shit2.resize(unique(all(shit2))-shit2.begin());
			for (pii p2:shit2) if (p2.second-p2.first>1){
				int pos=lower_bound(all(vec[u+1]), p2)-vec[u+1].begin();
				// assert(pos<SZ(vec[u+1]) && vec[u+1][pos]==p2); // namoosan ok bash
				ans+=(dwn[u+1][pos]+1>=d);
			}
		}
	}

	return ans;
}

Compilation message (stderr)

rect.cpp:3:40: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    3 | #pragma GCC optimize("O2, unroll-loops")
      |                                        ^
rect.cpp:29:43: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   29 | ll count_rectangles(vector<vector<int>> _A){
      |                                           ^

• 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: 28 / 28