Submission #928812

#	Time	Username	Problem	Language	Result	Execution time	Memory
928812		knon0501	Rectangles (IOI19_rect)	C++17	59 / 100	1432 ms	1048576 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> b[2505][2505];
vector<int> c[2505][2505];
vector<pair<int,int>> d[2505][2505];
vector<pair<int,int>> e[2505][2505];

int lef[2505][2505];
int rig[2505][2505];
int up[2505][2505];
int down[2505][2505];
vector<vector<int>> v;

long long count_rectangles(std::vector<std::vector<int> > a) {



	int n = a.size();
	int m = a[0].size();


	
	
	
	for(int i=1 ; i<n-1 ; i++){
		stack<int> S;

		for(int j=0 ; j<m ; j++){
			bool flag = true;
			while(!S.empty() && a[i][S.top()] <=  a[i][j]){
				int x = S.top(); 
				
				
				if(x +1 <j && flag)
					b[x+1][j-1].push_back(i);
				if(a[i][S.top()]==a[i][j])flag=false;
				S.pop();
				
			}
			if(!S.empty() ){
				int x = S.top();
				lef[i][j] = x;
				if(x+1<j && flag)
					b[x+1][j-1].push_back(i);
			}
			else{
				lef[i][j]=-1;
			}
			S.push(j);
		}
		while(!S.empty())S.pop();
		for(int j=m-1; j>=0 ; j--){
		
			while(!S.empty() && a[i][S.top()] <=  a[i][j]){
				
				S.pop();
				
			}
			if(!S.empty() ){
				int x = S.top();
				rig[i][j] = x;
				
			}
			else{
				rig[i][j]=-1;
			}
			S.push(j);
		}
	}

	for(int i=1 ; i<m-1 ; i++){
		stack<int> S;

		for(int j=0 ; j<n ; j++){
			bool flag = true;
			while(!S.empty() && a[S.top()][i] <=  a[j][i]){
				int x = S.top(); 
				
				
				if(x +1 <j && flag)
					c[x+1][j-1].push_back(i);
				if(a[S.top()][i]==a[j][i])flag=false;
				S.pop();
				
			}
			
			if(!S.empty() ){
				
				int x = S.top();
		
				up[j][i]=x;
				if(x+1<j && flag)
					c[x+1][j-1].push_back(i);
			}
			else{
				up[j][i]=-1;
			}
			S.push(j);
		}
		while(!S.empty())S.pop();
		for(int j=n-1 ; j>=0 ; j--){
			while(!S.empty() && a[S.top()][i] <=  a[j][i]){
			
				S.pop();
				
			}
			if(!S.empty() ){
				int x = S.top();
				down[j][i]=x;	
			}
			else{
				down[j][i]=-1;
			}
			S.push(j);
		}
	}
	long long ans = 0;
	for(int i=1 ; i<m ; i++){
		for(int j=i ; j<m ; j++){
			reverse(b[i][j].begin(),b[i][j].end());
			int prv = -1;
			int y;
			for(auto x: b[i][j]){
				if(x != prv-1){
					if(prv>=0)
						d[i][j].push_back({prv,y});
					y=x;
				}
				prv=x;
			}
			if(prv>=0){

				d[i][j].push_back({prv,y});
			}
			sort(d[i][j].begin(),d[i][j].end());
			std::vector<int>().swap(b[i][j]);

		}
	}
	for(int i=1 ; i<n  ; i++){
		for(int j=i ; j<n ; j++){
			reverse(c[i][j].begin(),c[i][j].end());
			int prv = -1;
			int y;
			for(auto x: c[i][j]){
				if(x != prv-1){
					if(prv>=0)
						e[i][j].push_back({prv,y});
					y=x;
				}
				prv=x;
			}
			if(prv>=0){
			
				e[i][j].push_back({prv,y});
			}
			sort(e[i][j].begin(),e[i][j].end());
			std::vector<int>().swap(c[i][j]);

		}
	}
	
	for(int i = 1 ; i<n-1 ; i++){
		for(int j=1 ; j<m-1 ; j++){
			int x = lef[i][j];
			int y = rig[i][j];
			int z = up[i][j];
			int w = down[i][j];
			v.push_back({x,y,z,w});
			
		}
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(auto vv: v){
		int x=vv[0];
		int y = vv[1];
		int z =vv[2];
		int  w = vv[3];
		if(x==-1 ||y==-1 || z==-1 || w==-1)continue;
			
			auto k = upper_bound(d[x+1][y-1].begin(),d[x+1][y-1].end(),make_pair(z+1,10000000));
			if(k== d[x+1][y-1].begin())continue;
		
			if((--k)->second <w-1)continue;
			
			//cout<<z+1<<" "<<w-1<<" "<<e[z+1][w-1].size()<<" "<<c[z+1][w-1].size()<<endl;
			auto t = upper_bound(e[z+1][w-1].begin(),e[z+1][w-1].end(),make_pair(x+1,10000000));
			
			if(t== e[z+1][w-1].begin())continue;
			
			if((--t)->second <y-1)continue;
			ans++;
	}
	return ans;
}

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