Submission #656837

#	Time	Username	Problem	Language	Result	Execution time	Memory
656837		jcelin	Rectangles (IOI19_rect)	C++14	100 / 100	2664 ms	695328 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 long long ll;
typedef long double ld;
typedef unsigned int ui;

#define ii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define matrix vector<vi>
#define matrixLL vector<vll>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()

const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 2510;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 13;
const int off = 1 << logo;
const int trsz = off << 1;

struct tournament{
	int seg[trsz], type;
	
	int merge(int a, int b){
		if(type == 0) return max(a, b);
		return min(a, b);
	}
	
	
	void build(){
		for(int i=off - 1; i; i--) seg[i] = merge(seg[i * 2], seg[i * 2 + 1]);
	}
	
	void update(int x, int val){
		seg[x + off] = val;
	}
	
	int query(int x, int lo, int hi, int a, int b){
		if(lo >= b or hi <= a) return inf * type - 5;
		if(lo >= a and hi <= b) return seg[x];
		int mid = (lo + hi) / 2;
		return merge(query(x * 2, lo, mid, a, b), query(x * 2 + 1, mid, hi, a, b));
	}
	
	int query(int l, int r){
		int sol = inf * type - 5;;
		for(l += off, r += off; l<r; l >>= 1, r >>= 1){
			if(l & 1) sol = merge(sol, seg[l++]);
			if(r & 1) sol = merge(sol, seg[--r]);
		}
		return sol;
	}
	
}h1[MAXN], h2[MAXN], h3[MAXN], h4[MAXN];

ii st[MAXN];
// i j 0 - prvi veci nalijevo od (i, j)
// i j 1 - prvi veci nadesno od (i, j)
// i j 2 - prvi veci gore od (i, j)
// i j 3 - prvi veci dolje od (i, j)
int bg[MAXN][MAXN][4];

ll count_rectangles(matrix mat){
	int n = mat.size();
	int m = mat[0].size();
	
	int ind = 0;
	REP(i, n){
		st[0] = {inf, -1};
		ind = 0;
		REP(j, m){
			while(st[ind].X < mat[i][j]) ind--;
			bg[i][j][0] = st[ind].Y;
			h1[j].update(i, bg[i][j][0]);
			while(st[ind].X <= mat[i][j]) ind--;
			bg[i][j][0] = st[ind].Y;
			ind++;
			st[ind] = {mat[i][j], j};
		}
		
		st[0] = {inf, m + 1};
		ind = 0;
		for(int j = m - 1; j >= 0; j--){
			while(st[ind].X < mat[i][j]) ind--;
			bg[i][j][1] = st[ind].Y;
			h2[j].update(i, bg[i][j][1]);
			while(st[ind].X <= mat[i][j]) ind--;
			bg[i][j][1] = st[ind].Y;
			ind++;
			st[ind] = {mat[i][j], j};
		}
	}
	
	
	REP(j, m){
		st[0] = {inf, -1};
		ind = 0;
		REP(i, n){
			while(st[ind].X < mat[i][j]) ind--;
			bg[i][j][2] = st[ind].Y;
			h3[i].update(j, bg[i][j][2]);
			while(st[ind].X <= mat[i][j]) ind--;
			
			ind++;
			st[ind] = {mat[i][j], i};
		}
		
		st[0] = {inf, n + 1};
		ind = 0;
		for(int i = n - 1; i >= 0; i--){
			while(st[ind].X < mat[i][j]) ind--;
			bg[i][j][3] = st[ind].Y;
			h4[i].update(j, bg[i][j][3]);
			while(st[ind].X <= mat[i][j]) ind--;
			bg[i][j][3] = st[ind].Y;
			ind++;
			st[ind] = {mat[i][j], i};
		}
	}
	
	
	/*
	REP(i, n) REP(j, m){
		h1[j].update(i, bg[i][j][0]);
		h2[j].update(i, bg[i][j][1]);
		h3[i].update(j, bg[i][j][2]);
		h4[i].update(j, bg[i][j][3]);
	}
	*/
	REP(i, m) h1[i].type = 0, h2[i].type = 1, h1[i].build(), h2[i].build();
	REP(j, n) h3[j].type = 0, h4[j].type = 1, h3[j].build(), h4[j].build();
	/*
	cout << "\n";
	REP(i, n){
		REP(j, m){
			cout << bg[i][j][3] << " ";
		}
		cout << "\n";
	}
	cout << "\n";
	REP(i, n){
		REP(j, m){
			cout << bg[i][j][2] << " ";
		}
		cout << "\n";
	}*/
	
	vll good;
	REP(i, n){
		REP(j, m){
			if(i == 0 or j == 0 or i == n - 1 or j == m - 1) continue;
			if(bg[i][j][0] == -1 or bg[i][j][1] == m + 1) continue;
			if(bg[i][j][2] == -1 or bg[i][j][3] == n + 1) continue;
			//if(i != 2 or j != 1) continue;
			
			//cout << i << " " << j << "\n";
			//REP(k, 4) cout << bg[i][j][k] << " ";
			//cout << '\n';
			
			ll hash = 0;
			REP(k, 4) hash *= MAXN, hash += bg[i][j][k];
			
			//lijeve gr.
			if(bg[i][j][0] < h1[bg[i][j][1]].query(bg[i][j][2] + 1, (bg[i][j][3] - 1) + 1)) continue;
			//cout << "PR1" << "\n";
			//desne
			if(bg[i][j][1] > h2[bg[i][j][0]].query(bg[i][j][2] + 1, (bg[i][j][3] - 1) + 1)) continue;
			//cout << "PR2" << "\n";
			//gore
			if(bg[i][j][2] < h3[bg[i][j][3]].query(bg[i][j][0] + 1, (bg[i][j][1] - 1) + 1)) continue;
			//cout << "PR3" << "\n";
			
			//cout << bg[i][j][3] << " " << h4[bg[i][j][2]].query(1, 0, off, bg[i][j][0] + 1, (bg[i][j][1] - 1) + 1) << "\n";
			//dolje
			if(bg[i][j][3] > h4[bg[i][j][2]].query(bg[i][j][0] + 1, (bg[i][j][1] - 1) + 1)) continue;
			//cout << "PR4" << "\n";
			//cout << "DOBARR " << i << " " << j << "\n";
			//REP(k, 4) cout << bg[i][j][k] << " ";
			//cout << "\n---------------\n";
			
			good.PB(hash);
		}
	}
	if(good.empty()) return 0;
	sort(all(good));
	ll pre = good[0];
	int ret = 1;
	for(auto &x : good) ret += (x != pre), pre = x;
	return ret;
}

/*
10 10
1 1 0 0 1 0 0 1 0 0
0 1 0 0 1 0 0 1 1 0
0 1 0 0 0 0 0 1 1 0
1 0 0 0 1 0 0 0 1 1
1 0 1 1 0 0 1 1 0 1
0 0 1 0 0 0 1 1 0 0
1 0 1 1 1 1 1 1 1 0
1 0 0 0 1 1 1 1 0 0
1 0 0 1 1 0 1 0 1 1
0 0 0 0 0 1 0 1 1 0


*/
/*
void solve(){
	int n, m;
	cin >> n >> m;
	matrix cur;
	vi s;
	s.resize(m);
	REP(i, n){
		for(auto &x : s) cin >> x;
		cur.PB(s);
	}
	cout << count_rectangles(cur);
}



int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t=1;
	//cin >> t;
	while(t--)solve();
	return 0;
}


*/

• 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