Submission #1236343

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236343		mariza	Rectangles (IOI19_rect)	C++20	13 / 100	148 ms	108240 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=3000;

ll pref[N][N];
ll sum(ll u, ll d, ll l, ll r){
    ll ans=pref[d][r];
    // cout<<ans<<endl;
    if(l>0) ans-=pref[d][l-1];
    // cout<<ans<<endl;
    if(u>0) ans-=pref[u-1][r];
    // cout<<ans<<endl;
    if(l>0 && u>0) ans+=pref[u-1][l-1];
    // cout<<ans<<endl;
    return ans;
}

long long count_rectangles(vector<vector<int>> a){
    ll n=a.size(), m=a[0].size();

    pref[0][0]=a[0][0];
    for(ll j=1; j<m; j++){
        pref[0][j]=pref[0][j-1]+a[0][j];
    }
    for(ll i=1; i<n; i++){
        pref[i][0]=pref[i-1][0]+a[i][0];
    }
    for(ll i=1; i<n; i++){
        for(ll j=1; j<m; j++){
            pref[i][j]=pref[i][j-1]+pref[i-1][j]-pref[i-1][j-1]+a[i][j];
        }
    }

    ll ans=0;
    for(ll u=1; u<n-1; u++){
        for(ll l=1; l<m-1; l++){
            if(a[u][l]==1 || a[u-1][l]==0 || a[u][l-1]==0) continue;

            ll d=u;
            while(d+1<n-1 && a[d+1][l]==0) d++;
            ll r=l;
            while(r+1<m-1 && a[u][r+1]==0) r++;

            // cout<<u<<" "<<d<<" "<<l<<" "<<r<<" "<<sum(u,d,l,r)<<endl;

            if(sum(u,d,l,r)==0 && sum(u-1,u-1,l,r)==r-l+1 && sum(d+1,d+1,l,r)==r-l+1 && sum(u,d,l-1,l-1)==d-u+1 && sum(u,d,r+1,r+1)==d-u+1) ans++;
        }
    }

    return ans;
}

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