Submission #836878

#	Time	Username	Problem	Language	Result	Execution time	Memory
836878		winter0101	Rectangles (IOI19_rect)	C++14	72 / 100	4003 ms	1048576 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;
set<int>b[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';
if (t.top()!=n+1){
    b[i][t.top()].insert(j);
}
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());
}
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){
for (auto v:b[i+1][j]){
if (j-v+1-2<=0)continue;
int vl=st.getmin(1,1,n,v+1,j-1);
if (a[i+1][v]>=a[i+1][j]){
    l[i+1][j].fi=vl;
}
if (a[i+1][j]>=a[i+1][v]){
    r[i+1][v].fi=vl;
}
}
}
}
for1(i,2,m){
for1(j,1,n){
st.upmax(1,1,n,j,up[i][j]);
}
for1(j,1,n){
for (auto v:b[i-1][j]){
if (j-v+1-2<=0)continue;
int vl=st.getmax(1,1,n,v+1,j-1);
if (a[i-1][v]>=a[i-1][j]){
    l[i-1][j].se=vl;
}
if (a[i-1][j]>=a[i-1][v]){
    r[i-1][v].se=vl;
}
}
}
}
}
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 bit;
bit.resz(m);
long long ans=0;
for1(i,2,m-1){
for1(j,1,n){
vector<int>num;
for (auto v:b[i][j])num.pb(v);
for (auto v:num){
    int p=i;
    for1(k,i,m-1){
    if (b[k][j].find(v)!=b[k][j].end()){
        p=k;
    }
    else break;
    }
    for1(k,i,p){
    b[k][j].erase(v);
    }
    if (j-v+1-2<=0)continue;
    //ans=0;
    //cout<<v+1<<" "<<j-1<<" "<<i<<" "<<p<<'\n';
    for2(k,p,i){
    //int vdcot=st[k+1].getmax(1,1,n,v+1,j-1);
    int vdcot;
    if (a[k][v]>=a[k][j])vdcot=l[k][j].se;
    if (a[k][v]<=a[k][j])vdcot=r[k][v].se;
    vdcot=max(vdcot+1,i);
    //cout<<v+1<<" "<<j-1<<" "<<vdcot<<" "<<k<<'\n';
    if (vdcot<=k){
    bit.add(k,1);
    del[vdcot].pb(k);
    }
    //int maxcot=st[k-1].getmin(1,1,n,v+1,j-1)-1;
    int maxcot;
    if (a[k][v]>=a[k][j])maxcot=l[k][j].fi;
    if (a[k][v]<=a[k][j])maxcot=r[k][v].fi;
    maxcot=min(maxcot-1,p);
    //cout<<k<<" "<<i<<" "<<maxcot<<'\n';
    //cout<<down[k-1][v+1]<<'\n';
    //ans=0;
    ans+=1ll*bit.get(i,maxcot);
    //cout<<k<<" "<<ans<<'\n';
    for (auto v1:del[k]){
    bit.add(v1,-1);
    }
    del[k].clear();
    }
    //cout<<ans<<" "<<v+1<<" "<<j-1<<" "<<i<<" "<<p<<'\n';
}
}
}
//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: 0 / 28