Submission #154454

#	Time	Username	Problem	Language	Result	Execution time	Memory
154454		liwi	Rectangles (IOI19_rect)	C++14	72 / 100	2770 ms	1048580 KiB

rect

#include "rect.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define MOD2 1494318097
#define SEED 131
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);

#define MAXN 2505

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;

mt19937 g1(time(0));

int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}

ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll  b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}

int num_rows,num_cols,arr[MAXN][MAXN],bit[MAXN],ans;
vector<pii> row_dp[MAXN][MAXN],col_dp[MAXN][MAXN];
//vector<pii> rows[MAXN],cols[MAXN];
vector<int> h_segs[MAXN][MAXN],v_segs[MAXN][MAXN];
//vector<int> r_range[MAXN][MAXN],v_range[MAXN][MAXN];

inline void update(int pos, int val){
	for(int i=pos; i<=num_cols; i+=i&-i)
		bit[i]+=val;
}

inline int query(int pos){
	int res = 0;
	for(int i=pos; i>0; i-=i&-i)
		res+=bit[i];
	return res;
}

inline void init_rows(){
	for(int i=2; i<num_rows; i++){
		deque<pii> dq;
		for(int k=1; k<=num_cols; k++){
			while(dq.size() && dq.back().first < arr[i][k]) dq.pop_back();
			int lft = (dq.size()?dq.back().second:INT_INF);
			if(lft < k-1 && (h_segs[lft+1][k-1].empty() || h_segs[lft+1][k-1].back() != i))
				h_segs[lft+1][k-1].pb(i); //rows[i].pb(mp(lft+1,k-1));
			while(dq.size() && dq.back().first == arr[i][k]) dq.pop_back();
			dq.pb(mp(arr[i][k],k));
		}
		while(dq.size()) dq.pop_back();
		for(int k=num_cols; k>=1; k--){
			while(dq.size() && dq.back().first < arr[i][k]) dq.pop_back();
			int rgt = (dq.size()?dq.back().second:-INT_INF);
			if(rgt > k+1 && (h_segs[k+1][rgt-1].empty() || h_segs[k+1][rgt-1].back() != i))
				h_segs[k+1][rgt-1].pb(i); //rows[i].pb(mp(k+1,rgt-1));
			while(dq.size() && dq.back().first == arr[i][k]) dq.pop_back();
			dq.pb(mp(arr[i][k],k));
		}
	}
}

inline void init_cols(){
	for(int i=2; i<num_cols; i++){
		deque<pii> dq;
		for(int k=1; k<=num_rows; k++){
			while(dq.size() && dq.back().first < arr[k][i]) dq.pop_back();
			int lft = (dq.size()?dq.back().second:INT_INF);
			if(lft < k-1 && (v_segs[lft+1][k-1].empty() || v_segs[lft+1][k-1].back() != i))
				v_segs[lft+1][k-1].pb(i); //cols[i].pb(mp(lft+1,k-1));
			while(dq.size() && dq.back().first == arr[k][i]) dq.pop_back();
			dq.pb(mp(arr[k][i],k));
		}
		while(dq.size()) dq.pop_back();
		for(int k=num_rows; k>=1; k--){
			while(dq.size() && dq.back().first < arr[k][i]) dq.pop_back();
			int rgt = (dq.size()?dq.back().second:-INT_INF);
			if(rgt > k+1 && (v_segs[k+1][rgt-1].empty() || v_segs[k+1][rgt-1].back() != i))
				v_segs[k+1][rgt-1].pb(i); //cols[i].pb(mp(k+1,rgt-1));
			while(dq.size() && dq.back().first == arr[k][i]) dq.pop_back();
			dq.pb(mp(arr[k][i],k));
		}
	}
}

inline void calc_hor_dp(){
//	for(int i=2; i<num_rows; i++){
//		sort(all(rows[i])); complete_unique(rows[i]);
//		for(pii check:rows[i]){
//			h_segs[check.first][check.second].pb(i);
////			r_range[i][check.first].pb(check.second);
//		}
//		rows[i].clear();
//	}
	for(int l=2; l<=num_cols-1; l++){
		for(int r=l; r<=num_cols-1; r++){
			vector<int> &nums = h_segs[l][r];
			if(!nums.size()) continue;
//			sort(all(nums)); complete_unique(nums);
			int lst = 0;
			for(int i=1; i<nums.size(); i++){
				if(nums[i] == nums[i-1]+1) continue;
				for(int k=nums[lst]; k<=nums[i-1]; k++)
					row_dp[k][l].pb(mp(nums[i-1]-k+1,r));
				lst = i;
			}
			for(int k=nums[lst]; k<=nums.back(); k++)
				row_dp[k][l].pb(mp(nums.back()-k+1,r));
		}
	}
}

inline void calc_col_dp(){
//	for(int i=2; i<num_cols; i++){
//		sort(all(cols[i])); complete_unique(cols[i]);
//		for(pii check:cols[i]){
//			v_segs[check.first][check.second].pb(i);
////			v_range[check.first][i].pb(check.second);
//		}
//		cols[i].clear();
//	}
	for(int l=2; l<=num_rows-1; l++){
		for(int r=l; r<=num_rows-1; r++){
			vector<int> &nums = v_segs[l][r];
			if(!nums.size()) continue;
//			sort(all(nums)); complete_unique(nums);
			int lst = 0;
			for(int i=1; i<nums.size(); i++){
				if(nums[i] == nums[i-1]+1) continue;
				for(int k=nums[lst]; k<=nums[i-1]; k++)
					col_dp[l][k].pb(mp(r,nums[i-1]));
				lst = i;
			}
			for(int k=nums[lst]; k<=nums.back(); k++)
				col_dp[l][k].pb(mp(r,nums.back()));
		}
	}
}

ll count_rectangles(vector<vector<int>> a){
	ans = 0, num_rows = (int)a.size(), num_cols = (int)a[0].size();
	for(int i=0; i<a.size(); i++)
		for(int k=0; k<a[i].size(); k++)
			arr[i+1][k+1] = a[i][k];
	init_rows(); init_cols();
	calc_hor_dp(); calc_col_dp();
	for(int i=2; i<num_rows; i++){
		for(int k=2; k<num_cols; k++){
			sort(all(row_dp[i][k]));
			sort(all(col_dp[i][k]));
			int ptr = 0, res = 0, cnt = 0;
			for(int v=0; v<row_dp[i][k].size(); v++){
//				pii curr = row_dp[i][k][v];
				while(ptr < col_dp[i][k].size() && col_dp[i][k][ptr].first-i+1 <= row_dp[i][k][v].first){
//					assert(col_dp[i][k][ptr].second>=k);
					update(col_dp[i][k][ptr].second-k+1,1);
					ptr++, cnt++;
				}
				res+=cnt-query(row_dp[i][k][v].second-k);
			}
			while(ptr--){
				if(ptr == -1) break;
				update(col_dp[i][k][ptr].second-k+1,-1);
			}
			ans+=res;
		}
	}
	return ans;
}

Compilation message (stderr)

rect.cpp: In function 'void calc_hor_dp()':
rect.cpp:128:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=1; i<nums.size(); i++){
                 ~^~~~~~~~~~~~
rect.cpp: In function 'void calc_col_dp()':
rect.cpp:155:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=1; i<nums.size(); i++){
                 ~^~~~~~~~~~~~
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:169:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<a.size(); i++)
               ~^~~~~~~~~
rect.cpp:170:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0; k<a[i].size(); k++)
                ~^~~~~~~~~~~~
rect.cpp:179:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int v=0; v<row_dp[i][k].size(); v++){
                 ~^~~~~~~~~~~~~~~~~~~~
rect.cpp:181:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(ptr < col_dp[i][k].size() && col_dp[i][k][ptr].first-i+1 <= row_dp[i][k][v].first){
           ~~~~^~~~~~~~~~~~~~~~~~~~~

• 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