Submission #1180135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180135		Zbyszek99	Sandcastle 2 (JOI22_ho_t5)	C++20	100 / 100	2169 ms	20900 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

vector<int> arr1[50001];

struct dir
{
    int l,r,u,d;
    int operator()()
    {
        return l+r*3+u*9+d*27;
    }
};

dir ntd(int x)
{
    int l = x%3;
    x/=3;
    int r = x%3;
    x/=3;
    int u = x%3;
    x/=3;
    int d = x%3;
    x/=3;
    return {l,r,u,d};
}

int* arr[50005];
int** pref[81];

int get_pref_sum(int x1, int y1, int x2, int y2, dir d)
{
    if(x1 > x2 || y1 > y2) return 0;
    int ind = d();
  //  cout << ind << " " << d.l << " " << d.r << " " << d.u << " " << d.d << " ind\n";
    return pref[ind][x2][y2] - pref[ind][x2][y1-1] - pref[ind][x1-1][y2] + pref[ind][x1-1][y1-1];
}

pii get_best(int x, int y, dir d)
{
    pair<int,pii> best;
    //l
    if(d.l != 0 && y-1 >= 0 && arr[x][y-1] < arr[x][y]) best = max(best,{arr[x][y-1],{x,y-1}});
    if(d.r != 0 && arr[x][y+1] < arr[x][y]) best = max(best,{arr[x][y+1],{x,y+1}});
    if(d.u != 0 && x-1 >= 0 && arr[x-1][y] < arr[x][y]) best = max(best,{arr[x-1][y],{x-1,y}});
    if(d.d != 0 && arr[x+1][y] < arr[x][y]) best = max(best,{arr[x+1][y],{x+1,y}});
    return best.ss;
}

int count_in(int x, int y, dir d)
{
    int ans = 0;
    if(d.l != 0)
    {
        pii b = get_best(x,y-1,{d.l-1,1,d.u,d.d});
        if(b.ff == x && b.ss == y) ans++;
    }
    if(d.r != 0)
    {
        pii b = get_best(x,y+1,{1,d.r-1,d.u,d.d});
        if(b.ff == x && b.ss == y) ans++;
    }
    if(d.u != 0)
    {
        pii b = get_best(x-1,y,{d.l,d.r,d.u-1,1});
        if(b.ff == x && b.ss == y) ans++;
    }
    if(d.d != 0)
    {
        pii b = get_best(x+1,y,{d.l,d.r,1,d.d-1});
      //  cout << " \n" <<  b.ff << " " << b.ss << " b\n";
        if(b.ff == x && b.ss == y) ans++;
    }
  //  cout << ans << " ans\n";
    if(ans == 0) return 1;
    if(ans >= 2) return 2;
    return 0;
}

bool* used_cor[50004];
vector<pii> dirs = {{0,1},{0,-1},{-1,0},{1,0}};

bool brut_force_rect(int x1, int y1, int x2, int y2)
{
    pair<int,pii> best = {-1,{-1,-1}};
    int path = 0;
    rep2(x,x1,x2)
    {
        rep2(y,y1,y2) best = max(best,{arr[x][y],{x,y}});
    }
    pii cur = best.ss;
    while(true)
    {
        path++;
        best = {-1,{-1,-1}};
        forall(it,dirs)
        {
            if(cur.ff + it.ff >= x1 && cur.ff + it.ff <= x2 && cur.ss+it.ss >= y1 && cur.ss+it.ss <= y2 && arr[cur.ff+it.ff][cur.ss+it.ss] < arr[cur.ff][cur.ss])
            {
                best = max(best,{arr[cur.ff+it.ff][cur.ss+it.ss],{it.ff+cur.ff,cur.ss+it.ss}});
            }
        }
        if(best.ff == -1) break;
        cur = best.ss;
    }
    return path == (x2-x1+1) * (y2-y1+1);
}

vector<pii> cor;

bool check_rect(int x1, int y1, int x2, int y2)
{
    if((x2-x1+1) * (y2-y1+1) <= 20) return brut_force_rect(x1,y1,x2,y2);
    int sum = get_pref_sum(x1+2,y1+2,x2-2,y2-2,{2,2,2,2});
   // cout << x1 << " " << y1 << " " << x2 << " " << y2 << " xd1\n";

    switch(x2-x1)
    {
        case 0:
        {
            sum += get_pref_sum(x1,y1+2,x1,y2-2,{2,2,0,0});
            break;
        }
        case 1:
        {
            sum += get_pref_sum(x1,y1+2,x1,y2-2,{2,2,0,1});
            sum += get_pref_sum(x1+1,y1+2,x1+1,y2-2,{2,2,1,0});
            break;
        }
        case 2:
        {
            sum += get_pref_sum(x1,y1+2,x1,y2-2,{2,2,0,2});
            sum += get_pref_sum(x1+1,y1+2,x1+1,y2-2,{2,2,1,1});
            sum += get_pref_sum(x1+2,y1+2,x1+2,y2-2,{2,2,2,0});
            break;
        }
        default:
        {
            sum += get_pref_sum(x1,y1+2,x1,y2-2,{2,2,0,2});
            sum += get_pref_sum(x1+1,y1+2,x1+1,y2-2,{2,2,1,2});
            sum += get_pref_sum(x2,y1+2,x2,y2-2,{2,2,2,0});
            sum += get_pref_sum(x2-1,y1+2,x2-1,y2-2,{2,2,2,1});
            break;
        }
    }    
    if(sum > 1) return 0;
   // cout << " xd2\n";
    
    switch(y2-y1)
    {
        case 0:
        {
            sum += get_pref_sum(x1+2,y1,x2-2,y1,{0,0,2,2});
            break;
        }
        case 1:
        {
            sum += get_pref_sum(x1+2,y1,x2-2,y1,{0,1,2,2});
            sum += get_pref_sum(x1+2,y1+1,x2-2,y1+1,{1,0,2,2});
            break;
        }
        case 2:
        {
            sum += get_pref_sum(x1+2,y1,x2-2,y1,{0,2,2,2});
            sum += get_pref_sum(x1+2,y1+1,x2-2,y1+1,{1,1,2,2});
            sum += get_pref_sum(x1+2,y1+2,x2-2,y1+2,{2,0,2,2});
            break;
        }
        default:
        {
            sum += get_pref_sum(x1+2,y1,x2-2,y1,{0,2,2,2});
            sum += get_pref_sum(x1+2,y1+1,x2-2,y1+1,{1,2,2,2});
            sum += get_pref_sum(x1+2,y2,x2-2,y2,{2,0,2,2});
            sum += get_pref_sum(x1+2,y2-1,x2-2,y2-1,{2,1,2,2});
            break;
        }
    }
  //  cout << " xd3\n";
   // cout << sum << " first_sum\n";
    if(sum > 1) return 0;
    int corner_sum = 0;
    cor = {};
    rep2(i,0,1)
    {
        cor.pb({x1+i,y1});
        cor.pb({x1+i,y1+1});
        cor.pb({x1+i,y2});
        cor.pb({x1+i,y2-1});
        
        cor.pb({x2-i,y1});
        cor.pb({x2-i,y1+1});
        cor.pb({x2-i,y2});
        cor.pb({x2-i,y2-1});
    }
    forall(it,cor)
    {
        if(it.ff >= x1 && it.ff <= x2 && it.ss >= y1 && it.ss <= y2 && !used_cor[it.ff][it.ss])
        {
            used_cor[it.ff][it.ss] = 1;
        //    cout << it.ff << " " << it.ss << " " << get_pref_sum(it.ff,it.ss,it.ff,it.ss,{min(2,it.ss-y1),min(2,y2-it.ss),min(2,it.ff-x1),min(2,x2-it.ff)}) << " " << count_in(it.ff,it.ss,{0,0,0,1}) << " cor\n";
            corner_sum += get_pref_sum(it.ff,it.ss,it.ff,it.ss,{min(2,it.ss-y1),min(2,y2-it.ss),min(2,it.ff-x1),min(2,x2-it.ff)});
        }
    }
    forall(it,cor)
    {
        if(it.ff >= x1 && it.ff <= x2 && it.ss >= y1 && it.ss <= y2)
        {
            used_cor[it.ff][it.ss] = 0;
        }
    }
    return corner_sum + sum == 1; 
}

int sumMap[1000004];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int n,m;
    cin >> n >> m;
    rep2(i,1,n)
    {
        arr1[i].resize(m+1);
        rep2(j,1,m) cin >> arr1[i][j];
    }
    if(n > m)
    {  
        rep2(i,1,m)
        {
            arr[i] = new int[n+3];
            rep2(j,1,n)
            {
                arr[i][j] = arr1[j][i];
            }
        }
        arr[0] = new int[n+3];
        arr[m+1] = new int[n+3];
        arr[m+2] = new int[n+3];
        swap(n,m);
    }
    else
    {
        rep2(i,1,n)
        {
            arr[i] = new int[m+3];
            rep2(j,1,m)
            {
                arr[i][j] = arr1[i][j];
            }
        }
        arr[0] = new int[m+3];
        arr[n+1] = new int[m+3];
        arr[n+2] = new int[m+3];
    }
    rep2(i,0,n+3)
    {
        used_cor[i] = new bool[m+3];
        rep(j,m+3) used_cor[i][j] = 0; 
    }
    rep(k,81)
    {
        pref[k] = new int*[n+3];
        rep(i,n+3)
        {
            pref[k][i] = new int[m+3];
        }
    }
    rep(k,81)
    {
        rep2(i,1,n)
        {
            rep2(j,1,m)
            {
                pref[k][i][j] = pref[k][i-1][j] + pref[k][i][j-1] - pref[k][i-1][j-1] + count_in(i,j,ntd(k));
            }
     
        }
    }
    int dod = n*m*2+6;
    ll ans = 0;
    dir d;
    rep2(x1,1,n)
    {
        rep2(x2,x1,n)
        {
            vi used_sums;
            rep2(y,1,m)
            {
                rep2(y2,y,min(m,y+2))
                {
                    if(check_rect(x1,y,x2,y2)) ans++;
                }
                if(y < 4) continue;
                y -= 3;
                ll p_sum = 0;
                switch(x2-x1)
                {
                    case 0:
                    {
                        p_sum += get_pref_sum(x1,y,x1,y,{0,2,0,0});
                        p_sum += get_pref_sum(x1,y+1,x1,y+1,{1,2,0,0});

                        d = {2,2,0,0};
                        p_sum += - pref[d()][x1][y+1] + pref[d()][x1-1][y+1];
                        break;
                    }
                    case 1:
                    {
                        p_sum += get_pref_sum(x1,y,x1,y,{0,2,0,1});
                        p_sum += get_pref_sum(x1,y+1,x1,y+1,{1,2,0,1});
                        p_sum += get_pref_sum(x1+1,y,x1+1,y,{0,2,1,0});
                        p_sum += get_pref_sum(x1+1,y+1,x1+1,y+1,{1,2,1,0});

                        d = {2,2,0,1};
                        p_sum += - pref[d()][x1][y+1] + pref[d()][x1-1][y+1];
                        d = {2,2,1,0};
                        p_sum += - pref[d()][x1+1][y+1] + pref[d()][x1][y+1];
                        break;
                    }
                    case 2:
                    {
                        p_sum += get_pref_sum(x1,y,x1,y,{0,2,0,2});
                        p_sum += get_pref_sum(x1,y+1,x1,y+1,{1,2,0,2});
                        p_sum += get_pref_sum(x1+1,y,x1+1,y,{0,2,1,1});
                        p_sum += get_pref_sum(x1+1,y+1,x1+1,y+1,{1,2,1,1});
                        p_sum += get_pref_sum(x1+2,y,x1+2,y,{0,2,2,0});
                        p_sum += get_pref_sum(x1+2,y+1,x1+2,y+1,{1,2,2,0});
                        
                        d = {2,2,0,2};
                        p_sum += - pref[d()][x1][y+1] + pref[d()][x1-1][y+1];
                        d = {2,2,1,1};
                        p_sum += - pref[d()][x1+1][y+1] + pref[d()][x1][y+1];
                        d = {2,2,2,0};
                        p_sum += - pref[d()][x1+2][y+1] + pref[d()][x1+1][y+1];
                        break;
                    }
                    default:
                    {
                        p_sum += get_pref_sum(x1,y,x1,y,{0,2,0,2});
                        p_sum += get_pref_sum(x1,y+1,x1,y+1,{1,2,0,2});
                        p_sum += get_pref_sum(x1+1,y,x1+1,y,{0,2,1,2});
                        p_sum += get_pref_sum(x1+1,y+1,x1+1,y+1,{1,2,1,2});

                        p_sum += get_pref_sum(x2,y,x2,y,{0,2,2,0});
                        p_sum += get_pref_sum(x2,y+1,x2,y+1,{1,2,2,0});
                        p_sum += get_pref_sum(x2-1,y,x2-1,y,{0,2,2,1});
                        p_sum += get_pref_sum(x2-1,y+1,x2-1,y+1,{1,2,2,1});

                        p_sum += get_pref_sum(x1+2,y,x2-2,y,{0,2,2,2});
                        p_sum += get_pref_sum(x1+2,y+1,x2-2,y+1,{1,2,2,2});

                        d = {2,2,2,0};
                        p_sum += - pref[d()][x2][y+1] + pref[d()][x2-1][y+1];
                        d = {2,2,2,1};
                        p_sum += -pref[d()][x2-1][y+1] + pref[d()][x2-2][y+1];
                        d = {2,2,0,2};
                        p_sum += -pref[d()][x1][y+1] + pref[d()][x1-1][y+1];
                        d = {2,2,1,2};
                        p_sum += -pref[d()][x1+1][y+1] + pref[d()][x1][y+1];
                        break;
                    }
                }
                if(x2-x1 > 3)
                {
                    d = {2,2,2,2};
                    p_sum += -pref[d()][x2-2][y+1] + pref[d()][x1+1][y+1];
                }
                y+=3;
                sumMap[p_sum+dod]++;
                used_sums.pb(p_sum);
                ll my_sum = 0;
                switch(x2-x1)
                {
                    case 0:
                    {
                        my_sum += get_pref_sum(x1,y,x1,y,{2,0,0,0});
                        my_sum += get_pref_sum(x1,y-1,x1,y-1,{2,1,0,0});
                        d = {2,2,0,0};
                        my_sum += pref[d()][x1][y-2] - pref[d()][x1-1][y-2];
                        break;
                    }
                    case 1:
                    {
                        my_sum += get_pref_sum(x1,y,x1,y,{2,0,0,1});
                        my_sum += get_pref_sum(x1,y-1,x1,y-1,{2,1,0,1});
                        my_sum += get_pref_sum(x1+1,y,x1+1,y,{2,0,1,0});
                        my_sum += get_pref_sum(x1+1,y-1,x1+1,y-1,{2,1,1,0});

                        d = {2,2,0,1};
                        my_sum += pref[d()][x1][y-2] - pref[d()][x1-1][y-2];
                        d = {2,2,1,0};
                        my_sum += pref[d()][x1+1][y-2] - pref[d()][x1][y-2];
                        break;
                    }
                    case 2:
                    {
                        my_sum += get_pref_sum(x1,y,x1,y,{2,0,0,2});
                        my_sum += get_pref_sum(x1,y-1,x1,y-1,{2,1,0,2});
                        my_sum += get_pref_sum(x1+1,y,x1+1,y,{2,0,1,1});
                        my_sum += get_pref_sum(x1+1,y-1,x1+1,y-1,{2,1,1,1});
                        my_sum += get_pref_sum(x1+2,y,x1+2,y,{2,0,2,0});
                        my_sum += get_pref_sum(x1+2,y-1,x1+2,y-1,{2,1,2,0});

                        d = {2,2,0,2};
                        my_sum += pref[d()][x1][y-2] - pref[d()][x1-1][y-2];
                        d = {2,2,1,1};
                        my_sum += pref[d()][x1+1][y-2] - pref[d()][x1][y-2];
                        d = {2,2,2,0};
                        my_sum += pref[d()][x1+2][y-2] - pref[d()][x1+1][y-2];
                        break;
                    }
                    default:
                    {
                        my_sum += get_pref_sum(x1,y,x1,y,{2,0,0,2});
                        my_sum += get_pref_sum(x1,y-1,x1,y-1,{2,1,0,2});
                        my_sum += get_pref_sum(x1+1,y,x1+1,y,{2,0,1,2});
                        my_sum += get_pref_sum(x1+1,y-1,x1+1,y-1,{2,1,1,2});

                        my_sum += get_pref_sum(x2,y,x2,y,{2,0,2,0});
                        my_sum += get_pref_sum(x2,y-1,x2,y-1,{2,1,2,0});
                        my_sum += get_pref_sum(x2-1,y,x2-1,y,{2,0,2,1});
                        my_sum += get_pref_sum(x2-1,y-1,x2-1,y-1,{2,1,2,1});

                        my_sum += get_pref_sum(x1+2,y,x2-2,y,{2,0,2,2});
                        my_sum += get_pref_sum(x1+2,y-1,x2-2,y-1,{2,1,2,2});

                        d = {2,2,2,0};
                        my_sum += pref[d()][x2][y-2] - pref[d()][x2-1][y-2];
                        d = {2,2,2,1};
                        my_sum += pref[d()][x2-1][y-2] - pref[d()][x2-2][y-2];
                        d = {2,2,0,2};
                        my_sum += pref[d()][x1][y-2] - pref[d()][x1-1][y-2];
                        d = {2,2,1,2};
                        my_sum += pref[d()][x1+1][y-2] - pref[d()][x1][y-2];
                        break;
                    }
                }
                if(x2-x1 > 3)
                {
                    d = {2,2,2,2};
                    my_sum += pref[d()][x2-2][y-2] - pref[d()][x1+1][y-2];
                }
                ans += sumMap[1-my_sum+dod];
            }
            forall(it,used_sums)
            {
                sumMap[it+dod] = 0;
            }
        }
    }
    cout << ans << "\n";
}

• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 5 / 5
• Subtask 4: 56 / 56
• Subtask 5: 20 / 20