Submission #1229414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229414		Gray	Rectangles (IOI19_rect)	C++20	37 / 100	757 ms	1114112 KiB

rect

#pragma GCC optimize("unroll-loops,Ofast")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second

struct Fenwick{
    vector<ll> tr;
    ll n, offs;
    Fenwick(ll N){
        n=N+20; offs=10;
        tr.resize(n+1);
    }
    void add(ll i, ll x){
        i+=offs;
        for (; i; i-=(-i&i)) tr[i]+=x;
    }
    ll get(ll i){
        ll res=0; i+=offs;
        for (; i<=n; i+=(-i&i)) res+=tr[i];
        return res;
    }
};

long long count_rectangles(vector<vector<int>> a) {
    ll n=a.size(), m=a[0].size();
    vector cols(m, vector(n, vector(n, false)));
    vector rows(n, vector(m, vector(m, false)));
    for (ll j=1; j<m-1; j++){
        for (ll up=1; up<n-1; up++){
            int cmx=a[up][j];
            for (ll down=up; down<n-1; down++){
                cmx=max(cmx, a[down][j]);
                if (cmx<a[up-1][j] and cmx<a[down+1][j]){
                    cols[j][up][down]=1;
                }
            }
        }
    }
    vector leftw(m, vector(n, vector(n, 0ll)));

    for (ll j=1; j<m-1; j++){
        for (ll up=1; up<n-1; up++){
            for (ll down=up; down<n-1; down++){
                leftw[j][up][down]=(cols[j][up][down]?leftw[j-1][up][down]+1:0);
            }
        }
    }


    for (ll i=1; i<n-1; i++){
        for (ll l=1; l<m-1; l++){
            int cmx=a[i][l];
            for (ll r=l; r<m-1; r++){
                cmx=max(cmx, a[i][r]);
                if (cmx<a[i][l-1] and cmx<a[i][r+1]){
                    rows[i][l][r]=1;
                }
            }
        }
    }
    vector upw(n, vector(m, vector(m, 0ll)));
    for (ll i=1; i<n-1; i++){
        for (ll l=1; l<m-1; l++){
            for (ll r=l; r<m-1; r++){
                upw[i][l][r]=(rows[i][l][r]?upw[i-1][l][r]+1:0);
            }
        }
    }
    ll cnt=0;

    for (ll right=1; right<m-1; right++){
        for (ll down=1; down<n-1; down++){
            vector<array<ll, 2>> posb;
            Fenwick gres(m);
            for (ll left=right; left>=1; left--){
                posb.push_back({upw[down][left][right], left});
                gres.add(left, 1);
            }
            sort(posb.rbegin(), posb.rend());
            for (ll up=down; up>=1; up--){
                ll l=right-leftw[right][up][down]+1;
                while (!posb.empty() and posb.back()[0]<down-up+1){
                    gres.add(posb.back()[1], -1);
                    posb.pop_back();
                }
                cnt+=gres.get(l);
            }
        }
    }

    // for (ll up=1; up<n-1; up++){
    //     for (ll down=up; down<n-1; down++){
    //         for (ll r=1; r<m-1; r++){
    //             for (ll l=r; l>=1; l--){
    //                 if (!cols[l][up][down]){
    //                     break;
    //                 }
    //                 if (upw[down][l][r]>=(down-up+1)) {
    //                     cnt++;
    //                 }
    //             }
    //         }
    //     }
    // }
	return cnt;
}

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