Submission #836703

#	Time	Username	Problem	Language	Result	Execution time	Memory
836703		winter0101	Rectangles (IOI19_rect)	C++14	72 / 100	4172 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=2509;
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 update(int id,int l,int r,int u,int v1,int v2){
if (l>u||r<u)return;
if (l==r){
    mx[id]=v2;
    mn[id]=v1;
    return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,v1,v2);
update(id*2+1,mid+1,r,u,v1,v2);
mx[id]=max(mx[id*2],mx[id*2+1]);
mn[id]=min(mn[id*2],mn[id*2+1]);
}*/
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 a[maxn][maxn];
set<int>b[maxn][maxn];
ST st[maxn];
vector<int>del[maxn];
void build(){
//up[i][j]=i1 j i1<i a[i1][j]>=a[i][j]
for1(i,1,m)st[i].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();
st[i].upmax(1,1,n,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();
st[i].upmin(1,1,n,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);
    //cout<<t.top()<<" "<<j<<'\n';
}
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);
}
}
}
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];
}
}
//cout<<m<<" "<<n<<'\n';
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);
    vdcot=max(vdcot+1,i);
    //cout<<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;
    maxcot=min(maxcot,p);
    //cout<<k<<" "<<i<<" "<<maxcot<<'\n';
    //cout<<down[k-1][v+1]<<'\n';
    //ans=0;
    if (maxcot>=i)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';
}
}
}
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