Submission #1022047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022047		mindiyak	Rectangles (IOI19_rect)	C++17	0 / 100	5060 ms	642524 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#include <string>
#include <iostream>
#include <cmath>
#include <numeric>
#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<int, int> pl;
typedef pair<ld, ld> pd;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
typedef vector<ld> vd;
typedef vector<long long> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
#define FOR(i, a, b) for (int i = a; i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define F first
#define nl endl
#define S second
#define lb lower_bound
#define ub upper_bound
#define aint(x) x.begin(), x.end()
#define raint(x) x.rbegin(), x.rend()
#define ins insert
const int MOD = 1000000007;
 
int N,M;
vvi arr;
ll ans = 0;
set<pair<pi,pi>> visited;
vvi seg1(2502,vi(10005,0)),seg2(2502,vi(10005,0));

int make_seg1(int pos,int l,int r,int id){
	if(l==r){
		seg1[id][pos] = arr[l][id];
		return seg1[id][pos];
	}
	int mid = (l+r)/2;
	seg1[id][pos] = max(make_seg1(2*pos+1,l,mid,id),make_seg1(2*pos+2,mid+1,r,id));
	return seg1[id][pos];
}

int make_seg2(int pos,int l,int r,int id){
	if(l==r){
		seg2[id][pos] = arr[id][l];
		return seg2[id][pos];
	}
	int mid = (l+r)/2;
	seg2[id][pos] = max(make_seg2(2*pos+1,l,mid,id),make_seg2(2*pos+2,mid+1,r,id));
	return seg2[id][pos];
}

int get_seg1(int pos,int l,int r,int ql,int qr,int id){
	if(ql>r||qr<l)return 0;
	if(ql<=l && r<=qr)return seg1[id][pos];
	int mid = (l+r)/2;
	return max(get_seg1(2*pos+1,l,mid,ql,qr,id),get_seg1(2*pos+2,mid+1,r,ql,qr,id));
}
 
int get_seg2(int pos,int l,int r,int ql,int qr,int id){
	if(ql>r||qr<l)return 0;
	if(ql<=l && r<=qr)return seg2[id][pos];
	int mid = (l+r)/2;
	return max(get_seg2(2*pos+1,l,mid,ql,qr,id),get_seg2(2*pos+2,mid+1,r,ql,qr,id));
}
 
void dfs(int a,int b,int c,int d,int wa,int wb,int wc,int wd){
	if(c<a)swap(a,c);
	if(d<b)swap(b,d);
	if(visited.count({{a,b},{c,d}}))return;
	if(a == 0 || b == 0 || c == (N-1) || d == (M-1))return;
	visited.insert({{a,b},{c,d}});
	bool bad = false;
	// cout << "a " << a << " " << c << " " << b << " " << d  << endl; 
	if(wa == -1 || wb == -1 || wc == -1 || wd == -1){
	// if(true){
		FOR(i,a,c+1){
			if(bad)break;
			int val = get_seg2(0,0,M-1,b,d,i);
			if(val >= arr[i][b-1])bad = true;
			if(val >= arr[i][d+1])bad = true;
		}
		FOR(j,b,d+1){
			if(bad)break;
			int val = get_seg1(0,0,N-1,a,c,j);
			if(val >= arr[a-1][j])bad = true;
			if(val >= arr[c+1][j])bad = true;
			// cout << "b " << val << " " << arr[a-1][j] << " " << arr[c+1][j] << endl;
		}
	}
	else{
		if(a<wa){
			FOR(i,a,wa+1){
				if(bad)break;
				int val = get_seg2(0,0,M-1,b,d,i);
				if(val >= arr[i][b-1])bad = true;
				if(val >= arr[i][d+1])bad = true;
			}
		}if (b<wb){
			FOR(j,b,wb+1){
				if(bad)break;
				int val = get_seg1(0,0,N-1,a,c,j);
				if(val >= arr[a-1][j])bad = true;
				if(val >= arr[c+1][j])bad = true;
			}
		}if(c>wc){
			FOR(i,wc,c+1){
				if(bad)break;
				int val = get_seg2(0,0,M-1,b,d,i);
				if(val >= arr[i][b-1])bad = true;
				if(val >= arr[i][d+1])bad = true;
			}
		}if (d>wd){
			FOR(j,wd,d+1){
				if(bad)break;
				int val = get_seg1(0,0,N-1,a,c,j);
				if(val >= arr[a-1][j])bad = true;
				if(val >= arr[c+1][j])bad = true;
			}
		}
		
	}
 
	// if(!bad)cout << a << " " << b << " " << c << " " << d  << " | " << wa << " " << wb << " " << wc << " " << wd << " - " << bad << endl;
 
	if(!bad)ans ++;
	if(!bad){wa=a;wb=b;wc=c;wd=d;}
	dfs(a-1,b,c,d,wa,wb,wc,wd);
	dfs(a,b-1,c,d,wa,wb,wc,wd);
	dfs(a,b,c+1,d,wa,wb,wc,wd);
	dfs(a,b,c,d+1,wa,wb,wc,wd);
	
	// FOR(i,a,c+1){
	// 	int val = get_seg2(0,0,M-1,b,d,i);
	// 	if(val >= arr[i][b-1])bad = true;
	// 	if(val >= arr[i][d+1])bad = true;
	// 	// cout << "b " << val << " " << arr[i][b-1] << " " << arr[i][b-1] << endl;
	// 	// FOR(j,b,d+1){
	// 	// 	if(arr[i][j] >= arr[i][b-1])bad = true;
	// 	// 	if(arr[i][j] >= arr[i][d+1])bad = true;
	// 	// 	if(arr[i][j] >= arr[a-1][j])bad = true;
	// 	// 	if(arr[i][j] >= arr[c+1][j])bad = true;
	// 	// 	if(bad)break;
	// 	// }
	// }
	// FOR(j,b,d+1){
	// 	int val = get_seg1(0,0,N-1,a,c,j);
	// 	if(val >= arr[a-1][j])bad = true;
	// 	if(val >= arr[c+1][j])bad = true;
	// 	// cout << "b " << val << " " << arr[a-1][j] << " " << arr[c+1][j] << endl;
	// }
	
	// // cout << "c " << bad << endl << endl;
 
	// // if(!bad)cout << a << " " << b << " " << c << " " << d  << " | " << wa << " " << wb << " " << wc << " " << wd << " - " << bad << endl;
 
	// if(!bad)ans ++;
	// dfs(a-1,b,c,d);
	// dfs(a,b-1,c,d);
	// dfs(a,b,c+1,d);
	// dfs(a,b,c,d+1);
}

//seg1 V
//seg2 >

ll count_rectangles(vvi a) {
	N = a.size();M = a[0].size();
	// cout << endl;
	arr = a;
	FOR(i,0,M){
		make_seg1(0,0,N-1,i);
	}
	FOR(i,0,N){
		make_seg2(0,0,M-1,i);
	}
	// FOR(i,0,M){
	// 	cout << get_seg1(0,0,N-1,0,0,i) << endl;
	// }
	// cout << "#" << endl;
	// FOR(i,0,N){
	// 	cout << get_seg2(0,0,M-1,0,0,i) << endl;
	// }
	// cout << "#" << endl;
	// FOR(i,0,N){
	// 	FOR(j,0,4*M){
	// 		cout << seg2[i][j] << " ";
	// 	}cout << endl;
	// }
	FOR(i,1,N-1){
		FOR(j,1,M-1){
			dfs(i,j,i,j,-1,-1,-1,-1);
		}
	}
	return ans;
}

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