Submission #1191424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191424		Mans21	Rectangles (IOI19_rect)	C++20	72 / 100	3466 ms	1106360 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#define ent '\n'

using namespace std;

const int maxn = 2512;

vector<short> gx[maxn][maxn], gy[maxn][maxn];
vector<pair<short, short>> cnt[maxn][maxn];
short lx[maxn][maxn], rx[maxn][maxn];
int t[maxn];
int n, m;

void upd(int i, int x) {
    for(; i >= 0; i = (i & (i + 1)) - 1) {
        t[i] += x;
    }
}

int get(int i) {
    int ans = 0;
    for(; i < maxn; i |= (i + 1)) {
        ans += t[i];
    }
    return ans;
}

long long count_rectangles(vector<vector<int>> a) {
    n = (int)a.size(), m = (int)a[0].size();


    for(int j = 0; j < m; j++) {
        stack<int> s;
        for(int i = 0; i < n; i++) {
            while(!s.empty() && a[s.top()][j] < a[i][j]) {
                s.pop();
            }
            lx[i][j] = -1;
            if(!s.empty()) {
                lx[i][j] = s.top();
                gy[s.top()][j].push_back(i);
            }
            s.push(i);
        }
        while(!s.empty()) {
            s.pop();
        }

        for(int i = n - 1; i >= 0; i--) {
            while(!s.empty() && a[s.top()][j] < a[i][j]) {
                s.pop();
            }
            rx[i][j] = n;
            if(!s.empty()) {
                rx[i][j] = s.top();
                if(lx[s.top()][j] != i) gy[i][j].push_back(s.top());
            }
            s.push(i);
        }
    }

    auto checkX = [&] (int i, int l, int r) -> bool {
        if(l > r || l < 0 || r >= m | i < 0 || i >= n) return false;

        return (rx[i][l] == r || lx[i][r] == l);
    };

    auto checkY = [&](int j, int l, int r) {
        if(l > r || l < 0 || r >= n || j < 0 || j >= m) return false;

        return (rx[l][j] == r || lx[r][j] == l);
    };


    long long ans = 0;

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            sort(gy[i][j].begin(), gy[i][j].end());
        }
    }

    for(int i = 0; i < n; i++) {
        stack<int> s;
        for(int j = 0; j < m; j++) {
            while(!s.empty() && a[i][s.top()] < a[i][j]) {
                s.pop();
            }
            lx[i][j] = -1;
            if(!s.empty()) {
                lx[i][j] = s.top();
                gx[i][s.top()].push_back(j);
            }
            s.push(j);
        }
        while(!s.empty()) {
            s.pop();
        }

        for(int j = m - 1; j >= 0; j--) {
            while(!s.empty() && a[i][s.top()] < a[i][j]) {
                s.pop();
            }
            rx[i][j] = m;
            if(!s.empty()) {
                rx[i][j] = s.top();
                if(lx[i][s.top()] != j) gx[i][j].push_back(s.top());
            }
            s.push(j);
        }
    }

    for(int i = 0; i < n; i++) {
        for(int l = 0; l < m; l++) {
            for(int r : gx[i][l]) {
                if(r - l <= 1) continue;

                if(checkX(i - 1, l, r)) {
                    continue;
                }

                int ptr = i;
                while(ptr + 1 < n && checkX(ptr + 1, l, r)) {
                    ptr++;
                }

                for(int x = i - 1; x < ptr; x++) {
                    int pos = upper_bound(gy[x][l + 1].begin(), gy[x][l + 1].end(), ptr + 1) - gy[x][l + 1].begin() - 1;
                    if(pos >= 0) {
                        cnt[x][l + 1].push_back({pos, r - 1});
                    }
                }
            }
        }
    }

    for(int j = 0; j < m; j++) {
        stack<int> s;
        for(int i = 0; i < n; i++) {
            gx[i][j] = vector<short> (gy[i][j].size(), -1);
            while(!s.empty() && a[s.top()][j] < a[i][j]) {
                s.pop();
            }
            lx[i][j] = -1;
            if(!s.empty()) {
                lx[i][j] = s.top();
            }
            s.push(i);
        }
        while(!s.empty()) {
            s.pop();
        }

        for(int i = n - 1; i >= 0; i--) {
            while(!s.empty() && a[s.top()][j] < a[i][j]) {
                s.pop();
            }
            rx[i][j] = n;
            if(!s.empty()) {
                rx[i][j] = s.top();
            }
            s.push(i);
        }
    }

    for(int j = 0; j < m; j++) {
        for(int l = 0; l < n; l++) {
            for(int r : gy[l][j]) {
                if(r - l <= 1) continue;

                if(checkY(j - 1, l, r)) {
                    continue;
                }

                int ptr = j;
                while(ptr + 1 < m && checkY(ptr + 1, l, r)) {
                    ptr++;
                }

                for(int x = j; x <= ptr; x++) {
                    int pos = lower_bound(gy[l][x].begin(), gy[l][x].end(), r) - gy[l][x].begin();
                    gx[l][x][pos] = ptr;
                }
            }
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            sort(cnt[i][j].begin(), cnt[i][j].end());
            for(int pos = 0, ptr = 0; pos < gy[i][j].size(); pos++) {
                upd(gx[i][j][pos], 1);
                while(ptr < cnt[i][j].size() && cnt[i][j][ptr].first == pos) {
                    ans += get(cnt[i][j][ptr].second);
                    ptr++;
                }
            }
            for(int pos : gx[i][j]) {
                upd(pos, -1);
            }
        }
    }

    return ans;
}

• 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: 0 / 28