Submission #1031030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031030		Zicrus	Rectangles (IOI19_rect)	C++17	50 / 100	320 ms	62728 KiB

rect

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

typedef long long ll;

ll n, m;
ll pow2N, pow2M;
vector<vector<ll>> segN, segM;

unordered_map<ll, ll> sN, sM;
 
ll segMaxN(ll low, ll high, ll m) {
    ll hash = (low << 32) | (high << 16) | m;
    if (sN[hash]) return sN[hash];

    low += pow2N; high += pow2N;
    ll mx = 0;
    while (low <= high) {
        if (low & 1) mx = max(mx, segN[m][low++]);
        if (!(high & 1)) mx = max(mx, segN[m][high--]);
        low /= 2; high /= 2;
    }
    return sN[hash] = mx;
}
 
ll segMaxM(ll low, ll high, ll n) {
    ll hash = (low << 32) | (high << 16) | n;
    if (sM[hash]) return sM[hash];

    low += pow2M; high += pow2M;
    ll mx = 0;
    while (low <= high) {
        if (low & 1) mx = max(mx, segM[n][low++]);
        if (!(high & 1)) mx = max(mx, segM[n][high--]);
        low /= 2; high /= 2;
    }
    return sM[hash] = mx;
}

ll count_rectangles(vector<vector<int>> a) {
    if (a.size() <= 2) return 0;
    n = a.size(); m = a[0].size();

    if (n > 200 && m > 200) {
        if (a.size() <= 2) return 0;
        n = a.size(); m = a[0].size();
    
        vector<vector<bool>> vst(n, vector<bool>(m));
        ll res = 0;
        for (int i = 1; i < n-1; i++) {
            for (int j = 1; j < m-1; j++) {
                if (a[i][j] || vst[i][j]) continue;
                
                ll ptrN = i, ptrM = j;
                while (!a[ptrN][ptrM] && ptrM < m-1) ptrM++;
                ptrM--;
                while (!a[ptrN][ptrM] && ptrN < n-1) ptrN++;
                ptrN--;
    
                bool poss = true;
                for (int x = i; x <= ptrN && poss; x++) {
                    for (int y = j; y <= ptrM && poss; y++) {
                        vst[x][y] = true;
                        if (a[x][y]) poss = false;
                    }
                }
                for (int x = i; x <= ptrN && poss; x++) {
                    if (!a[x][j-1]) poss = false;
                    if (!a[x][ptrM+1]) poss = false;
                }
                for (int y = j; y <= ptrM && poss; y++) {
                    if (!a[i-1][y]) poss = false;
                    if (!a[ptrN+1][y]) poss = false;
                }
                res += poss;
            }
        }
        return res;
    }

    pow2N = 1ll << (ll)ceil(log2(n));
    pow2M = 1ll << (ll)ceil(log2(m));
    sN = unordered_map<ll, ll>(); sM = unordered_map<ll, ll>();
    vector<int> am = a[1];
    segN = vector<vector<ll>>(m, vector<ll>(2*pow2N));
    segM = vector<vector<ll>>(n, vector<ll>(2*pow2M));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            segN[j][pow2N+i] = a[i][j];
            segM[i][pow2M+j] = a[i][j];
        }
    }
    for (int meta = 0; meta < n; meta++) {
        for (int i = pow2M-1; i > 0; i--) {
            segM[meta][i] = max(segM[meta][2*i], segM[meta][2*i+1]);
        }
    }
    for (int meta = 0; meta < m; meta++) {
        for (int i = pow2N-1; i > 0; i--) {
            segN[meta][i] = max(segN[meta][2*i], segN[meta][2*i+1]);
        }
    }

    unordered_set<ll> s;

    ll res = 0;
    for (int i = 1; i < n-1; i++) {
        for (int j = 1; j < m-1; j++) {
            ll left = j, right = j, top = i, bottom = i;
            ll ref = a[i][j];

            ll low = 0, high = j;
            while (low < high) {
                ll mid = (low + high + 1) / 2;
                if (segMaxM(mid, high, i) <= ref) {
                    high = mid-1;
                }
                else {
                    low = mid;
                }
            }
            left = low+1;
            low = j, high = m-1;
            while (low < high) {
                ll mid = (low + high) / 2;
                if (segMaxM(low, mid, i) <= ref) {
                    low = mid+1;
                }
                else {
                    high = mid;
                }
            }
            right = high-1;

            low = 0, high = i;
            while (low < high) {
                ll mid = (low + high + 1) / 2;
                if (segMaxN(mid, high, j) <= ref) {
                    high = mid-1;
                }
                else {
                    low = mid;
                }
            }
            top = low+1;
            low = i, high = n-1;
            while (low < high) {
                ll mid = (low + high) / 2;
                if (segMaxN(low, mid, j) <= ref) {
                    low = mid+1;
                }
                else {
                    high = mid;
                }
            }
            bottom = high-1;

            ll hash = (left << 48) | (right << 32) | (top << 16) | bottom;
            if (s.count(hash)) continue;
            s.insert(hash);

            ll lN = bottom-top+1, lM = right-left+1;
            bool poss = 1;
            for (int meta = top; meta < top+lN && poss; meta++) {
                ll border = min(a[meta][left-1], a[meta][left+lM]);
                if (border <= segMaxM(left, left+lM-1, meta)) {
                    poss = 0;
                }
            }
            for (int meta = left; meta < left+lM && poss; meta++) {
                ll border = min(a[top-1][meta], a[top+lN][meta]);
                if (border <= segMaxN(top, top+lN-1, meta)) {
                    poss = 0;
                }
            }
            res += poss;
        }
    }
    return res;
}

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