Submission #836939

#	Time	Username	Problem	Language	Result	Execution time	Memory
836939		winter0101	Rectangles (IOI19_rect)	C++17	100 / 100	2905 ms	318556 KiB

rect

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=2e3+5e2+9;
const int inf=7e6+9;
struct ST{
vector<int>mx,mn;
void resz(int n){
mx.resize(4*n+9);
mn.resize(4*n+9);
}
void upmin(int id,int l,int r,int u,int v1){
if (l>u||r<u)return;
if (l==r){
    //mx[id]=v2;
    mn[id]=v1;
    return;
}
int mid=(l+r)/2;
upmin(id*2,l,mid,u,v1);
upmin(id*2+1,mid+1,r,u,v1);
mn[id]=min(mn[id*2],mn[id*2+1]);
}
void upmax(int id,int l,int r,int u,int v2){
if (l>u||r<u)return;
if (l==r){
    mx[id]=v2;
    return;
}
int mid=(l+r)/2;
upmax(id*2,l,mid,u,v2);
upmax(id*2+1,mid+1,r,u,v2);
mx[id]=max(mx[id*2],mx[id*2+1]);
}
int getmin(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 2509;
if (u<=l&&r<=v)return mn[id];
int mid=(l+r)/2;
return min(getmin(id*2,l,mid,u,v),getmin(id*2+1,mid+1,r,u,v));
}
int getmax(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return mx[id];
int mid=(l+r)/2;
return max(getmax(id*2,l,mid,u,v),getmax(id*2+1,mid+1,r,u,v));
}
};
struct BIT{
vector<int>bit;
int n;
void resz(int _n){
n=_n;
bit.resize(n+1);
}
void add(int pos,int val){
for(;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
int get(int pos){
int sum=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))sum+=bit[pos];
return sum;
}
int get(int l,int r){
if (l>r)return 0;
return get(r)-get(l-1);
}
};
int m,n;
int up[maxn][maxn],down[maxn][maxn],a[maxn][maxn];
pii l[maxn][maxn],r[maxn][maxn];
//fi min se max
ST st;
int b[maxn][maxn],c[maxn][maxn];
vector<int>del[maxn];
void build(){
//up[i][j]=i1 j i1<i a[i1][j]>=a[i][j]
st.resz(n);
for1(j,1,n){
stack<int>t;
t.push(0);
a[0][j]=inf;
for1(i,1,m){
while (!t.empty()&&a[t.top()][j]<a[i][j])t.pop();
up[i][j]=t.top();
t.push(i);
}
}
for1(j,1,n){
a[m+1][j]=inf;
stack<int>t;
t.push(m+1);
for2(i,m,1){
while (!t.empty()&&a[t.top()][j]<a[i][j])t.pop();
down[i][j]=t.top();
t.push(i);
}
}
for1(i,1,m){
a[i][n+1]=inf;
stack<int>t;
t.push(n+1);
for2(j,n,1){
while (!t.empty()&&a[i][t.top()]<a[i][j])t.pop();
//cout<<i<<" "<<j<<" "<<t.top()<<'\n';
//b[i][t.top()].insert(j);
c[i][j]=t.top();
t.push(j);
}
}
for1(i,1,m){
a[i][0]=inf;
stack<int>t;
t.push(0);
for1(j,1,n){
while (!t.empty()&&a[i][t.top()]<a[i][j])t.pop();
//if (t.top()!=0){
//b[i][j].insert(t.top());
b[i][j]=t.top();
//}
t.push(j);
}
}
for1(i,1,m-1){
for1(j,1,n){
st.upmin(1,1,n,j,down[i][j]);
}
for1(j,1,n){
//min
l[i+1][j].fi=st.getmin(1,1,n,b[i+1][j]+1,j-1);
r[i+1][j].fi=st.getmin(1,1,n,j+1,c[i+1][j]-1);
}
}
for1(i,2,m){
for1(j,1,n){
st.upmax(1,1,n,j,up[i][j]);
}
for1(j,1,n){
l[i-1][j].se=st.getmax(1,1,n,b[i-1][j]+1,j-1);
r[i-1][j].se=st.getmax(1,1,n,j+1,c[i-1][j]-1);
}
}
}
BIT bit;
long long ans=0;
bool check(int i,int l1,int r1){
if (c[i][l1]>=r1&&b[i][r1]<=l1)return 1;
return 0;
}
void solve(int i,int l1,int r1){
if (i>2&&check(i-1,l1,r1))return;
if (l1==0||r1==n+1)return;
int p=i;
for1(k,i,m-1){
if (check(k,l1,r1))p=k;
else break;
}
if (r1-l1+1-2<=0)return;
//ans=0;
for2(k,p,i){
int vdcot;
if (a[k][l1]>=a[k][r1])vdcot=l[k][r1].se;
if (a[k][l1]<=a[k][r1])vdcot=r[k][l1].se;
vdcot=max(vdcot+1,i);
if (vdcot<=k){
bit.add(k,1);
del[vdcot].pb(k);
}
int maxcot;
if (a[k][l1]>=a[k][r1])maxcot=l[k][r1].fi;
if (a[k][l1]<=a[k][r1])maxcot=r[k][l1].fi;
maxcot=min(maxcot-1,p);
ans+=1ll*bit.get(i,maxcot);
for (auto v1:del[k])bit.add(v1,-1);
del[k].clear();
}
//cout<<i<<" "<<p<<" "<<l1+1<<" "<<r1-1<<" "<<ans<<'\n';
}
long long count_rectangles(vector<vector<int>>a1){
m=a1.size();
for1(i,0,m-1){
n=a1[i].size();
for1(j,0,n-1){
a[i+1][j+1]=a1[i][j];
}
}
build();
bit.resz(m);
for1(i,2,m-1){
for1(j,1,n){
solve(i,b[i][j],j);
//cout<<i<<" "<<b[i][j]<<" "<<j<<'\n';
if (a[i][c[i][j]]!=a[i][j])solve(i,j,c[i][j]);
}
}
//cout<<ans<<'\n';
return ans;
}
/*signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    freopen("temp.INP","r",stdin);
    //freopen(".OUT","w",stdout);
	int n1, m1;
	cin>>n1>>m1;
	vector<vector<int>> a1(n1, vector<int>(m1));
	for (int i = 0; i < n1; i++)	{
		for (int j = 0; j < m1; j++) {
			cin>>a1[i][j];
		}
	}
	long long result = count_rectangles(a1);
	printf("%lld\n", result);
	return 0;
}*/

• 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