Submission #423475

#	Time	Username	Problem	Language	Result	Execution time	Memory
423475		Jasiekstrz	Rectangles (IOI19_rect)	C++17	100 / 100	3164 ms	738564 KiB

rect

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include "rect.h"
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
const int N=25e2;
vector<int> st;
vector<pair<int,int>> r[N+10][N+10];
vector<pair<int,int>> u[N+10][N+10];
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> os;
long long count_rectangles(vector<vector<int>> a)
{
	int n=a.size(),m=a[0].size();
	long long ans=0;
	for(int i=1;i<n-1;i++)
	{
		st.clear();
		for(int j=0;j<m;j++)
		{
			while(!st.empty() && a[i][st.back()]<a[i][j])
			{
				if(st.back()+1<=j-1)
					r[i][st.back()+1].emplace_back(j-1,1);
				st.pop_back();
			}
			if(!st.empty() && st.back()+1<=j-1)
				r[i][st.back()+1].emplace_back(j-1,1);
			while(!st.empty() && a[i][st.back()]==a[i][j])
				st.pop_back();
			st.push_back(j);
		}
	}
	for(int j=1;j<m-1;j++)
	{
		st.clear();
		for(int i=0;i<n;i++)
		{
			while(!st.empty() && a[st.back()][j]<a[i][j])
			{
				if(st.back()+1<=i-1)
					u[st.back()+1][j].emplace_back(i-1,1);
				st.pop_back();
			}
			if(!st.empty() && st.back()+1<=i-1)
				u[st.back()+1][j].emplace_back(i-1,1);
			while(!st.empty() && a[st.back()][j]==a[i][j])
				st.pop_back();
			st.push_back(i);
		}
	}
	for(int i=n-2;i>=1;i--)
	{
		for(int j=0;j<m;j++)
		{
			size_t it=0;
			for(auto &v:r[i][j])
			{
				while(it<r[i+1][j].size() && r[i+1][j][it].fi<v.fi)
					it++;
				if(it<r[i+1][j].size() && r[i+1][j][it].fi==v.fi)
					v.se=r[i+1][j][it].se+1;
				//cerr<<"r["<<i<<"]["<<j<<"]: ("<<v.fi<<","<<v.se<<")\n";
			}
		}
	}
	for(int j=m-2;j>=1;j--)
	{
		for(int i=0;i<n;i++)
		{
			size_t it=0;
			for(auto &v:u[i][j])
			{
				while(it<u[i][j+1].size() && u[i][j+1][it].fi<v.fi)
					it++;
				if(it<u[i][j+1].size() && u[i][j+1][it].fi==v.fi)
					v.se=u[i][j+1][it].se+1;
				//cerr<<"u["<<i<<"]["<<j<<"]: ("<<v.fi<<","<<v.se<<")\n";
			}
		}
	}
	for(int i=1;i<n-1;i++)
	{
		for(int j=1;j<m-1;j++)
		{
			for(auto &v:r[i][j])
				v.fi-=j-1;
			for(auto &v:u[i][j])
				v.fi-=i-1;
		}
	}
	for(int i=1;i<n-1;i++)
	{
		for(int j=1;j<m-1;j++)
		{
			os.clear();
			sort(u[i][j].begin(),u[i][j].end(),
					[](pair<int,int> &a,pair<int,int> &b){ return a.se<b.se; });
			for(int it1=(int)r[i][j].size()-1,it2=(int)u[i][j].size()-1;it1>=0;it1--)
			{
				while(it2>=0 && u[i][j][it2].se>=r[i][j][it1].fi)
				{
					os.insert(u[i][j][it2].fi);
					it2--;
				}
				ans+=os.order_of_key(r[i][j][it1].se+1);
			}
			//cerr<<i<<" "<<j<<" "<<ans<<"\n";
		}
	}
	return ans;
}

• 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