Submission #1024468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1024468		hotboy2703	Rectangles (IOI19_rect)	C++17	100 / 100	2816 ms	955056 KiB

rect

#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 2510;
const ll MAXK = 13;
vector <pll> row[MAXN][MAXN];
vector <pair <ll,pll> > col[MAXN][MAXN];
pll bound[MAXN][MAXN];
vector <ll> down[MAXN][MAXN];
ll sp[MAXK][MAXN];
vector <ll> b;
ll highest(ll x,ll y){
    if (b[y]>b[x])return y;
    return x;
}
ll query(ll l,ll r){
    ll sz = __lg(r-l+1);
    return highest(sp[sz][l],sp[sz][r-MASK(sz)+1]);
}
void solve(ll l,ll r,vector <pll> &ans){
    if (l > r)return;
    ll mid = query(l,r);
    solve(l,mid-1,ans);
    solve(mid+1,r,ans);
    ans[mid] = MP(l,r);
}
vector <pll> build(){
    ll n = sz(b);
    for (ll i = 0;i < n;i ++){
        sp[0][i] = i;
    }
    for (ll j = 1;j < MAXK;j ++){
        for (ll i = 0;i + MASK(j) - 1 < n;i ++){
            sp[j][i] = highest(sp[j-1][i],sp[j-1][i+MASK(j-1)]);
        }
    }
    vector <pll> res(n);
    solve(0,n-1,res);
    for (ll i = 0;i < n;i ++){
        if (res[i].fi == 0 || res[i].se == n-1 || b[res[i].fi-1] <= b[i] || b[res[i].se+1] <= b[i])res[i] = MP(-1,-1);
    }
    return res;
}
long long count_rectangles(std::vector<std::vector<int> > a){
    ll n = sz(a);
    ll m = sz(a[0]);
//    cout<<n<<' '<<m<<endl;
    for (ll i = 0;i < n; i ++){
        b = a[i];
        vector <pll> tmp = build();
        for (ll j = 0;j < m;j ++){
            bound[i][j] = tmp[j];
            if (bound[i][j].fi != -1)row[bound[i][j].fi][bound[i][j].se].push_back(MP(i,0));
        }
    }
    for (ll i = 0;i < m;i ++){
        for (ll j = i;j < m;j ++){
            for (ll k = sz(row[i][j])-1;k>=0;k--){
                if (k == sz(row[i][j])-1 || row[i][j][k].fi + 1 < row[i][j][k+1].fi)row[i][j][k].se = row[i][j][k].fi ;
                else row[i][j][k].se = row[i][j][k+1].se;
//                if (i==j&&j==1)cout<<row[i][j][k].fi<<' '<<row[i][j][k].se<<endl;
            }
        }
    }
    for (ll j = 0;j < m;j ++){
        b.resize(n);
        for (ll i = 0;i < n;i ++){
            b[i] = a[i][j];
        }
        vector <pll> tmp = build();
        for (auto x:tmp){
            if (x.fi==-1)continue;
            col[x.fi][x.se].push_back(MP(j,MP(0,0)));
            down[x.fi][j].push_back(x.se);
        }
    }
    for (ll i = 0;i < n;i ++){
        for (ll j = i;j < n;j ++){
            for (ll k = sz(col[i][j])-1;k>=0;k--){
                if (k == sz(col[i][j])-1 || col[i][j][k].fi + 1 < col[i][j][k+1].fi)col[i][j][k].se.se = col[i][j][k].fi;
                else col[i][j][k].se.se = col[i][j][k+1].se.se;
            }
            for (ll k = 0;k < sz(col[i][j]);k ++){
                if (k == 0 || col[i][j][k].fi - 1 > col[i][j][k-1].fi)col[i][j][k].se.fi = col[i][j][k].fi;
                else col[i][j][k].se.fi = col[i][j][k-1].se.fi;
            }
        }
    }
    ll res = 0;
    for (ll i = 0;i < n;i ++){
        for (ll j = 0;j < m;j ++){
            if (bound[i][j].fi==-1)continue;
            ll l = bound[i][j].fi,r = bound[i][j].se;
            ll max1 = (*lower_bound(row[l][r].begin(),row[l][r].end(),MP(i,-1))).se;
//            cout<<i<<' '<<j<<' '<<l<<' '<<r<<' '<<max1<<endl;
            for (auto x:down[i][j]){

                pll tmp = (*lower_bound(col[i][x].begin(),col[i][x].end(),MP(j,MP(-1,-1)))).se;
//                cout<<x<<' '<<tmp.fi<<' '<<tmp.se<<endl;
                if (tmp.fi <= l && tmp.se >= r && x <= max1){
//                    cout<<i<<' '<<l<<' '<<x<<' '<<r<<endl;
                    res++;
                }
            }

        }
    }
    return res;
}

• 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