Submission #836488

#	Time	Username	Problem	Language	Result	Execution time	Memory
836488		Rafi22	Rectangles (IOI19_rect)	C++14	59 / 100	5112 ms	868456 KiB

rect

#include <bits/stdc++.h>
     
using namespace std;
     
#define ll long long 
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;

const int N=2507,pot=1<<12;

set<int>V[N][N];
int U[N][2*pot+7];
int D[N][2*pot+7];
int n,m;

int queU(int v,int a,int b,int l,int r,int i)
{
	if(a<=l&&b>=r) return U[i][v];
	if(r<a||l>b) return -1;
	return max(queU(2*v,a,b,l,(l+r)/2,i),queU(2*v+1,a,b,(l+r)/2+1,r,i));
}
int queD(int v,int a,int b,int l,int r,int i)
{
	if(a<=l&&b>=r) return D[i][v];
	if(r<a||l>b) return n;
	return min(queD(2*v,a,b,l,(l+r)/2,i),queD(2*v+1,a,b,(l+r)/2+1,r,i));
}

int BIT[N];

int que(int x) 
{
	int s=0;
	for (;x;x-=x&-x) s+=BIT[x];
	return s;
}
void ins(int x,int s) {
	for (;x<N;x+=x&-x) BIT[x]+=s;
}

     
ll count_rectangles(vector<vector<int>>a)
{
	ll ans=0;
	n=sz(a),m=sz(a[0]);
	for(int i=1;i<n-1;i++)
	{
		deque<pair<int,int>>Q;
		Q.pb({a[i][0],0});
		for(int j=1;j<m;j++)
		{
			while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back();
			if(sz(Q)>0) V[Q.back().nd+1][j-1].insert(i);
			Q.pb({a[i][j],j});
		}
		Q.clear();
		Q.pb({a[i][m-1],m-1});
		for(int j=m-2;j>=0;j--)
		{
			while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back();
			if(sz(Q)>0) V[j+1][Q.back().nd-1].insert(i);
			Q.pb({a[i][j],j});
		}
	}
	for(int i=0;i<n;i++)
	{
		 for(int j=1;j<2*pot;j++) 
		 {
			 U[i][j]=-1;
			 D[i][j]=n;
		 }
	}
	for(int j=0;j<m;j++)
	{
		deque<pair<int,int>>Q;
		Q.pb({a[0][j],0});
		for(int i=1;i<n;i++)
		{
			while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back();
			if(sz(Q)>0) U[i][j+pot]=Q.back().nd;
			Q.pb({a[i][j],i});
		}
		Q.clear();
		Q.pb({a[n-1][j],n-1});
		for(int i=n-2;i>=0;i--)
		{
			while(sz(Q)>0&&Q.back().st<a[i][j]) Q.pop_back();
			if(sz(Q)>0) D[i][j+pot]=Q.back().nd;;
			Q.pb({a[i][j],i});
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=pot-1;j>0;j--)
		{
			U[i][j]=max(U[i][2*j],U[i][2*j+1]);
			D[i][j]=min(D[i][2*j],D[i][2*j+1]);
		}
	}
	for(int i=0;i<m;i++)
	{
		for(int j=i;j<m;j++)
		{
			if(sz(V[i][j])==0) continue;
			//cout<<i<<" "<<j<<endl;
			vector<pair<int,int>>E;
			int l=-1;
			for(auto x:V[i][j]) 
			{
				
				int k=queD(1,i+1,j+1,1,pot,x-1);
				if(k==x)
				{
					E.pb({x,inf-1});
				}
				else
				{
					E.pb({x,inf});
					E.pb({k,x});
				}
				if(x!=l+1)  E.pb({x,-inf});
				l=x;
			}
			sort(all(E));
			set<int>alive;
			for(auto [x,c]:E)
			{
				//cout<<x<<" "<<c<<endl;
				if(c==-inf) 
				{
					for(auto y:alive) ins(y+1,-1);
					alive.clear();
				}
				else if(c==inf) 
				{
					ins(x+1,1);
					ans+=(ll)que(x+1)-que(queU(1,i+1,j+1,1,pot,x+1)+1);
					alive.insert(x);
				}
				else if(c==inf-1) ans+=(ll)que(x+1)-que(queU(1,i+1,j+1,1,pot,x+1)+1);
				else
				{
					if(alive.count(c)) 
					{
						alive.erase(c);
						ins(c+1,-1);
					}
				}
			}
			for(auto x:alive) ins(x+1,-1);
		//	cout<<ans<<endl;
		}
	}
	return ans;
}
/*
int main()
{
	cout<<count_rectangles({
{4, 8, 7, 5, 6},
{7, 4, 10, 3, 5},
{9, 7, 20, 14, 2},
{9, 14, 7, 3, 6},
{5, 7, 5, 2, 7},
{4, 5, 13, 5, 6}})<<endl;
	return 0;
}*/
    

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:132:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  132 |    for(auto [x,c]:E)
      |             ^

• 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