Submission #596294

#	Time	Username	Problem	Language	Result	Execution time	Memory
596294		Koosha_mv	Rectangles (IOI19_rect)	C++14	23 / 100	1745 ms	665564 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=2555,inf=1e8;

int n,m,a[N][N],L[N][N],D[N][N],U[N][N],R[N][N],fen[N][N],dp[N],mark[N],lupd[N][N],pd[N][N];
vector<int> lv[N][N];
vector<pair<int,int>> uv[N][N];
ll ans;

void do_it(){
	f(i,1,n+1){
		f(j,1,m+1){
			U[i][j]=i-1;
			while(a[U[i][j]][j]<a[i][j]){
				U[i][j]=U[U[i][j]][j];
			}
			L[i][j]=j-1;
			while(a[i][L[i][j]]<a[i][j]){
				L[i][j]=L[i][L[i][j]];
			}
			if(a[U[i][j]][j]==a[i][j]){
				U[i][j]=0;
			}
			if(a[i][L[i][j]]==a[i][j]){
				L[i][j]=0;
			}
			if(U[i][j] && U[i][j]!=i-1){
				uv[i][j].pb({U[i][j],0});
			}			
			if(L[i][j] && L[i][j]!=j-1){
				lv[i][j].pb(L[i][j]);
			}
		}
	}
	f_(i,n,1){
		f_(j,m,1){
			D[i][j]=i+1;
			while(a[D[i][j]][j]<a[i][j]){
				D[i][j]=D[D[i][j]][j];
			}
			R[i][j]=j+1;
			while(a[i][R[i][j]]<a[i][j]){
				R[i][j]=R[i][R[i][j]];
			}
			if(D[i][j]<=n && D[i][j]!=i+1){
				uv[D[i][j]][j].pb({i,0});
			}
			if(R[i][j]<=m && R[i][j]!=j+1){
				lv[i][R[i][j]].pb(j);
			}
		}
	}
}
void edame(){
	f(i,1,n+1){
		f(j,1,m+1){
			f(k,0,int(uv[i][j].size())){
				int x=uv[i][j][k].F;
				lupd[x][j]=i;
				pd[x][j]=j;
				if(lupd[x][j-1]==i){
					pd[x][j]=pd[x][j-1];
				}
				uv[i][j][k].S=pd[x][j];
			}
		}
	}
}
void ad(int x,int y,int val){
	for(y++;y>0;y-=(y&-y)){
		fen[x][y]+=val;
	}
}
int gt(int x,int y){
	int res=0;
	for(y++;y<N;y+=(y&-y)){
		res+=fen[x][y];
	}
	return res;
}
void add(int x,int y,int val){
	for(x++;x<N;x+=(x&-x)){
		ad(x,y,val);
	}
}
int get(int x,int y){
	int res=0;
	for(x++;x>0;x-=(x&-x)){
		res+=gt(x,y);
	}
	return res;
}
void solve(int y){
	vector<pair<int,pair<int,int>>> op;
	fill(dp,dp+N,N);
	fill(mark,mark+N,0);
	f(x,2,n+1){
		for(auto u : lv[x][y]){
			mark[u]=x;
			if(dp[u]==N){
				dp[u]=x;
				add(dp[u],u,1);
				op.pb({-1,{dp[u],u}});
			}
		}
		for(auto u : lv[x-1][y]){
			if(mark[u]==x-1){
				add(dp[u],u,-1);
				op.pb({+1,{dp[u],u}});
				dp[u]=N;
			}
		}
		for(auto p : uv[x+1][y-1]){
			ans+=get(p.F+1,p.S-1);
		}
		//eror(ans);
	}
	for(auto p : op){
		add(p.S.F,p.S.S,p.F);
	}
	//f(i,0,N) f(j,0,N) fen[i][j]=0;
}
ll count_rectangles(vector<vector<int>> T) {
	n=T.size(),m=T[0].size();
	f(i,0,n){
		f(j,0,m){
			a[i+1][j+1]=T[i][j]+1;
		}
	}
	f(i,0,n+2){
		f(j,0,m+2){
			if(a[i][j]) continue ;
			a[i][j]=inf;
		}
	}
	do_it();
	edame();
	f(i,3,m+1){
		solve(i);
	}
	//solve(5);
	return ans;
}
/*
3 3
2 2 2
2 1 2
2 2 2

3 3
2 2 2
2 2 2
2 2 2

4 4
10 10 10 10
10 2 2 10
10 1 2 10
10 10 10 10
*/

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