Submission #1064757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064757		jamjanek	Rectangles (IOI19_rect)	C++14	100 / 100	4177 ms	673236 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>stosy[2510];
int nast[2510][2510][4];
int nast2[2510][2510][4];

const int base = 1<<12;
int tree1[2510][2*base];
int tree2[2510][2*base];
int tree3[2*base][2510];
int tree4[2*base][2510];

int MAXI1(int w, int l, int p, int a, int b, int war){
	if(p<a || b<l)return -1;
	if(a<=l && p<=b)return tree3[w][war];
	return max(MAXI1(w*2, l, (l+p)/2, a, b, war), MAXI1(w*2+1, (l+p)/2+1, p, a, b, war));
}
int MINI1(int w, int l, int p, int a, int b, int war){
	if(p<a || b<l)return 2600;
	if(a<=l && p<=b)return tree4[w][war];
	return min(MINI1(w*2, l, (l+p)/2, a, b, war), MINI1(w*2+1, (l+p)/2+1, p, a, b, war));
}
int MAXI2(int w, int l, int p, int a, int b, int war){
	if(p<a || b<l)return -1;
	if(a<=l && p<=b)return tree1[war][w];
	return max(MAXI2(w*2, l, (l+p)/2, a, b, war), MAXI2(w*2+1, (l+p)/2+1, p, a, b, war));
}
int MINI2(int w, int l, int p, int a, int b, int war){
	if(p<a || b<l)return 2600;
	if(a<=l && p<=b)return tree2[war][w];
	return min(MINI2(w*2, l, (l+p)/2, a, b, war), MINI2(w*2+1, (l+p)/2+1, p, a, b, war));
}

int maxi1(int war, int l, int r){
//	printf("%d %d %d  ", war, l, r);
	l+=base, r+=base;
	if(l>r)return -1;
	int res = max(tree3[l][war], tree3[r][war]);
	while(l/2<r/2){
		if((l&1)==0){
			res = max(res, tree3[l^1][war]);
		}
		if(r&1){
			res = max(res, tree3[r^1][war]);
		}
		l>>=1;
		r>>=1;
	}
//	printf("%d\n", res);
	return res;
	return MAXI1(1, 0, base-1, l, r, war);
	for(int i=l;i<=r;i++)
		res = max(res, nast2[i][war][0]);
	return res;
}
int mini1(int war, int l, int r){
	l+=base, r+=base;
	if(l>r)return 2600;
	int res = min(tree4[l][war], tree4[r][war]);
	while(l/2<r/2){
		if((l&1)==0){
			res = min(res, tree4[l^1][war]);
		}
		if(r&1){
			res = min(res, tree4[r^1][war]);
		}
		l>>=1;
		r>>=1;
	}
//	printf("%d\n", res);
	return res;

	return MINI1(1, 0, base-1, l, r, war);
//	int res = 2600;
	for(int i=l;i<=r;i++)
		res = min(res, nast2[i][war][1]);
	return res;
}
int maxi2(int war, int l, int r){
	return MAXI2(1, 0, base-1, l, r, war);
	int res = -1;
	for(int i=l;i<=r;i++)
		res = max(res, nast2[war][i][2]);
	return res;
}
int mini2(int war, int l, int r){
	return MINI2(1, 0, base-1, l, r, war);
	int res = 2600;
	for(int i=l;i<=r;i++)
		res = min(res, nast2[war][i][3]);
	return res;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	int n = a.size();
	int m = a[0].size();
	int i, j;

	//poprzednie po x [0]	
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			while(stosy[i].size() && stosy[i].back().first<=a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[i][j][0] = stosy[i].back().second;
			else
				nast[i][j][0] = -1;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();

	//nastepne po x [1]

	for(i=0;i<n;i++){
		for(j=m-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<=a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[i][j][1] = stosy[i].back().second;
			else
				nast[i][j][1] = m;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();
	
	//poprzednie po y [2]
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			while(stosy[i].size() && stosy[i].back().first<=a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[j][i][2] = stosy[i].back().second;
			else
				nast[j][i][2] = -1;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();

	//nastepne po y [3]
	for(i=0;i<m;i++){
		for(j = n-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<=a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast[j][i][3] = stosy[i].back().second;
			else
				nast[j][i][3] = n;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();
		
		
		
		
		
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			while(stosy[i].size() && stosy[i].back().first<a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast2[i][j][0] = stosy[i].back().second;
			else
				nast2[i][j][0] = -1;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();

	//nastepne po x [1]

	for(i=0;i<n;i++){
		for(j=m-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<a[i][j])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast2[i][j][1] = stosy[i].back().second;
			else
				nast2[i][j][1] = m;
			stosy[i].push_back({a[i][j], j});
		}
	}
	for(i=0;i<n;i++)
		stosy[i].clear();
	
	//poprzednie po y [2]
	for(i=0;i<m;i++){
		for(j=0;j<n;j++){
			while(stosy[i].size() && stosy[i].back().first<a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast2[j][i][2] = stosy[i].back().second;
			else
				nast2[j][i][2] = -1;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();

	//nastepne po y [3]
	for(i=0;i<m;i++){
		for(j = n-1;j>=0;j--){
			while(stosy[i].size() && stosy[i].back().first<a[j][i])
				stosy[i].pop_back();
			if(stosy[i].size())
				nast2[j][i][3] = stosy[i].back().second;
			else
				nast2[j][i][3] = n;
			stosy[i].push_back({a[j][i], j});
		}
	}
	for(i=0;i<m;i++)
		stosy[i].clear();



	vector<pair<pair<int,int>, pair<int,int>>>sett;
	for(i=1;i<n-1;i++)
		for(j=1;j<m-1;j++){
			//printf("%d %d %d %d\n", nast[i][j][0], nast[i][j][1], nast[i][j][2], nast[i][j][3]);
			if(nast[i][j][0]!=-1 && nast[i][j][1]!=m && nast[i][j][2]!=-1 && nast[i][j][3]!=n){
				//printf("dodaje\n");
				sett.push_back({{nast[i][j][0], nast[i][j][1]}, {nast[i][j][2], nast[i][j][3]}});
			}
		}
	
	for(i=0;i<n;i++)
		for(j=0;j<m;j++){
			tree3[base+i][j] = nast2[i][j][0];
			tree4[base+i][j] = nast2[i][j][1];
			tree1[i][base+j] = nast2[i][j][2];
			tree2[i][base+j] = nast2[i][j][3];
		}
	for(i=0;i<n;i++)
		for(j=base-1;j>0;j--){
			tree1[i][j] = max(tree1[i][j*2], tree1[i][j*2+1]);
			tree2[i][j] = min(tree2[i][j*2], tree2[i][j*2+1]);
		}
	for(i=0;i<m;i++)
		for(j=base-1;j>0;j--){
			tree3[j][i] = max(tree3[j*2][i], tree3[j*2+1][i]);
			tree4[j][i] = min(tree4[j*2][i], tree4[j*2+1][i]);
		}
	sort(sett.begin(), sett.end());
	long long wynik = 0;
	for(i=0;i<(int)sett.size();i++){
		if(i!=0 && sett[i-1]==sett[i])continue;
		auto x = sett[i];
		if(mini1(x.first.first, x.second.first+1, x.second.second-1)<x.first.second)continue;
		if(maxi1(x.first.second, x.second.first+1, x.second.second-1)>x.first.first)continue;

		if(mini2(x.second.first, x.first.first+1, x.first.second-1)<x.second.second)continue;
		if(maxi2(x.second.second, x.first.first+1, x.first.second-1)>x.second.first)continue;
		wynik++;
	}
	
	return wynik;
}

• 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