Submission #641050

#	Time	Username	Problem	Language	Result	Execution time	Memory
641050		someone	Sandcastle 2 (JOI22_ho_t5)	C++14	9 / 100	53 ms	11660 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Sit {
    int nbMax, nbMin, col;
};

const int M = 5e4 + 42, N = 5 * M, K = 230, INF = 1e18 + 42;

Sit l[M], r[M];
int n, m, val[N];
vector<Sit> deb[K][K], fin[K][K];

int dl[] = {0, 0, 1, -1},
    dc[] = {1, -1, 0, 0};

inline int getId(int i, int j) {
    return (i + 2) * (m + 4) + (j + 2);
}

struct SDD {
    bool isMin[N];
    int value[N], nbPre[N], nbMin[M], nbSup[M], nbMinCol[M], nbPreCol[M];
    
    void init() {
        for(int i = 0; i < N; i++)
            value[i] = INF;
    }
    
    void getNext(int i, int j, int cancel) {
        if(value[getId(i, j)] == INF)
            return;
        int id = -1;
        for(int k = 0; k < 4; k++) {
            int id2 = getId(i + dl[k], j + dc[k]);
            if(value[getId(i, j)] > value[id2]) {
                if(id == -1 || value[id2] > value[id])
                    id = id2;
            }
        }
        if(id == -1) {
            if(isMin[getId(i, j)])
                nbMinCol[j]--;
            if(cancel != -1)
                nbMinCol[j]++;
            isMin[getId(i, j)] = (cancel != -1);
        } else {
            int iCol = (id % (m+4)) - 2;
            if(nbPre[id] > 1)
                nbSup[iCol]--;
            nbPre[id] += cancel;
            if(nbPre[id] > 1)
                nbSup[iCol]++;
            nbPreCol[iCol] += cancel;
        }
    }
    
    void update(int i, int j, int cancel) {
        getNext(i, j, cancel);
        for(int k = 0; k < 4; k++)
            getNext(i + dl[k], j + dc[k], cancel);
    }
    
    void change(int i, int j, int newVal) {
        update(i, j, -1);
        value[getId(i, j)] = newVal;
        update(i, j, 1);
    }
};

SDD sdd;
int ans = 0;

void count3() {
    for(int width = 1; width < 4; width++) {
        for(int i = 0; i <= m-width; i++) {
            for(int j = 0; j < n; j++) {
                for(int k = j; k < n; k++) {
                    for(int l = i; l < i+width; l++)
                        sdd.change(k, l, val[getId(k, l)]);
                        
                    int nbPre = 0, nbMin = 0, nbSup = 0;
                    for(int l = i; l < i+width; l++)
                        nbPre += sdd.nbPreCol[l],
                        nbMin += sdd.nbMinCol[l],
                        nbSup += sdd.nbSup[l];
                    
                    if(nbPre == width * (k - j + 1) - 1 && nbMin == 1 && nbSup == 0) {
                        ans++;
                    }
                }
                for(int k = j; k < n; k++)
                    for(int l = i; l < i+width; l++)
                        sdd.change(k, l, INF);
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    sdd.init();
    
    cin >> n >> m;
    int n2 = n, m2 = m;
    if(n > m)
        swap(n, m);
    for(int i = 0; i < n2; i++)
        for(int j = 0; j < m2; j++)
            if(n2 <= m2)
                cin >> val[getId(i, j)];
            else
                cin >> val[getId(j, i)];
    
    count3();
    
    for(int i = 0; i <= m-4; i++) {
        for(int j = 0; j < n; j++) {
            for(int k = j; k < n; k++) {
                for(int l = i; l < i+4; l++)
                    sdd.change(k, l, val[getId(k, l)]);
                if(sdd.nbSup[i] == 0 && sdd.nbSup[i+1] == 0 && sdd.nbMinCol[i] + sdd.nbMinCol[i+1] < 2 && sdd.nbPreCol[i] + sdd.nbPreCol[i+1] >= 2*(k-j)+1) {
                    deb[j][k].push_back({2*(k-j+1) - sdd.nbPreCol[i] - sdd.nbPreCol[i+1], sdd.nbMinCol[i] + sdd.nbMinCol[i+1], i+2});
                }
                if(sdd.nbSup[i+2] == 0 && sdd.nbSup[i+3] == 0 && sdd.nbMinCol[i+2] + sdd.nbMinCol[i+3] < 2 && sdd.nbPreCol[i+2] + sdd.nbPreCol[i+3] >= 2*(k-j)+1) {
                    fin[j][k].push_back({2*(k-j+1) - sdd.nbPreCol[i+2] - sdd.nbPreCol[i+3], sdd.nbMinCol[i+2] + sdd.nbMinCol[i+3], i+2});
                }
            }
            for(int k = j; k < n; k++)
                for(int l = i; l < i+4; l++)
                    sdd.change(k, l, INF);
        }
    }
    
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            for(int k = 0; k < m; k++)
                sdd.change(j, k, val[getId(j, k)]);
            for(int k = 0; k < m; k++) {
                l[k].col = r[k].col = -1;
                l[k].nbMin = r[k].nbMin = l[k].nbMax = r[k].nbMax = 0;
            }
            for(Sit sit : deb[i][j]) {
                l[sit.col].col = 0;
                l[sit.col].nbMax = sit.nbMax;
                l[sit.col].nbMin = sit.nbMin;
            }
            for(Sit sit : fin[i][j]) {
                r[sit.col].col = 0;
                r[sit.col].nbMax = sit.nbMax;
                r[sit.col].nbMin = sit.nbMin;
            }
            
            for(int nbmin : {0, 1})
                for(int nbmax : {0, 1}) {
                    int nbMin = nbmin, nbMax = nbmax,
                        right = 1, nbType[2][2] = {{0, 0}, {0, 0}};
                    for(int left = 2; left < m-1; left++) {
                        
                        if(right < left) {
                            right++;
                            if(r[right].col != -1)
                                nbType[r[right].nbMin][r[right].nbMax]++;
                        }
                        
                        while(right < m-2 && sdd.nbSup[right] == 0 && (nbMin >= sdd.nbMinCol[right] && nbMax >= (j-i+1) - sdd.nbPreCol[right])) {
                            nbMin -= sdd.nbMinCol[right],
                            nbMax -= (j-i+1) - sdd.nbPreCol[right];
                            right++;
                            if(r[right].col != -1)
                                nbType[r[right].nbMin][r[right].nbMax]++;
                        }
                        
                        if(nbMin == 0 && nbMax == 0 && nbmin + l[left].nbMin <= 1 && nbmax + l[left].nbMax <= 1) {
                            ans += nbType[1 - nbmin - l[left].nbMin][1 - nbmax - l[left].nbMax];
                        }
                        
                        if(r[left].col != -1)
                            nbType[r[left].nbMin][r[left].nbMax]--;
                        if(left < right) {
                            nbMin += sdd.nbMinCol[left],
                            nbMax += (j-i+1) - sdd.nbPreCol[left];
                        }
                    }
                }
        }
        for(int j = i; j < n; j++)
            for(int k = 0; k < m; k++)
                sdd.change(j, k, INF);
    }
    cout << ans;
}

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