Submission #418249

#	Time	Username	Problem	Language	Result	Execution time	Memory
418249		Peti	Rectangles (IOI19_rect)	C++14	72 / 100	3640 ms	1048580 KiB

rect

#include <bits/stdc++.h>

using namespace std;

const int maxn = 2505, INF = (int)1e9;
int n, m;

int Y1[maxn][maxn], Y2[maxn][maxn], X1[maxn][maxn], X2[maxn][maxn];
vector<bool> jo;

struct adat{
    int l, r, x, ind;
    adat(){}
    adat(int l, int r, int x, int ind) : l(l), r(r), x(x), ind(ind) {}
};

void calc_elott(vector<vector<int>> &a, function<bool(int, int)> comp){
    for(int i = 0; i < n; i++){
        Y1[i][0] = -1;
        for(int j = 1; j < m; j++){
            Y1[i][j] = j-1;
            while(Y1[i][j] >= 0 && comp(a[i][Y1[i][j]], a[i][j]))
                Y1[i][j] = Y1[i][Y1[i][j]];
        }
        Y2[i][m-1] = m;
        for(int j = m-2; j >= 0; j--){
            Y2[i][j] = j+1;
            while(Y2[i][j] < m && comp(a[i][Y2[i][j]], a[i][j]))
                Y2[i][j] = Y2[i][Y2[i][j]];
        }
    }
    for(int i = 0; i < m; i++){
        X1[0][i] = -1;
        for(int j = 1; j < n; j++){
            X1[j][i] = j-1;
            while(X1[j][i] >= 0 && comp(a[X1[j][i]][i], a[j][i]))
                X1[j][i] = X1[X1[j][i]][i];
        }
        X2[n-1][i] = n;
        for(int j = n-2; j >= 0; j--){
            X2[j][i] = j+1;
            while(X2[j][i] < n && comp(a[X2[j][i]][i], a[j][i]))
                X2[j][i] = X2[X2[j][i]][i];
        }
    }
}

vector<adat> U[maxn+1], D[maxn+1], L[maxn+1], R[maxn+1];

pair<int, int> sor[maxn+2];
void ell(int t[], vector<adat> &ints, int n, function<bool(int, int)> comp){
    vector<vector<adat>> vh(n);
    for(adat &d : ints)
        vh[d.r].push_back(d);
    int x = 0;
    for(int i = 0; i < n; i++){
        while(x > 0 && comp(t[i], sor[x-1].second))
            x--;
        sor[x++] = make_pair(i, t[i]);
        for(adat &d : vh[i])
            if(comp(lower_bound(sor, sor+x, make_pair(d.l, -INF))->second, d.x))
                jo[d.ind] = false;
    }
}

vector<pair<int, int>> sarok[maxn][maxn];
bool volt[maxn][maxn] = {};

long long count_rectangles(std::vector<std::vector<int>> a){
    n = (int)a.size();
    m = (int)a[0].size();
    calc_elott(a, [](int a, int b){ return a <= b; });

    int ind = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            int x1 = X1[i][j], x2 = X2[i][j], y1 = Y1[i][j], y2 = Y2[i][j];
            if(x1 != -1 && y1 != -1 && x2 != n && y2 != m)
                sarok[x1][y1].emplace_back(x2, y2);
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            for(pair<int, int> &p : sarok[i][j]){
                int x1 = i, y1 = j, x2 = p.first, y2 = p.second;
                if(volt[x2][y2]) continue;
                volt[x2][y2] = true;
                U[x1].emplace_back(y1+1, y2-1, x2, ind);
                D[x2].emplace_back(y1+1, y2-1, x1, ind);
                L[y1].emplace_back(x1+1, x2-1, y2, ind);
                R[y2].emplace_back(x1+1, x2-1, y1, ind);
                jo.push_back(true);
                ind++;
            }
            for(pair<int, int> &p : sarok[i][j])
                volt[p.first][p.second] = false;
        }
    }

    calc_elott(a, [](int a, int b){ return a < b; });

    for(int i = 0; i < maxn; i++){
        for(int j = i+1; j < maxn; j++){
            swap(Y1[i][j], Y1[j][i]);
            swap(Y2[i][j], Y2[j][i]);
        }
    }


    for(int i = 0; i < n; i++){
        ell(X1[i], D[i], m, [](int a, int b){return a > b;});
        ell(X2[i], U[i], m, [](int a, int b){return a < b;});
    }
    for(int i = 0; i < m; i++){
        ell(Y1[i], R[i], n, [](int a, int b){return a > b;});
        ell(Y2[i], L[i], n, [](int a, int b){return a < b;});
    }

    return accumulate(jo.begin(), jo.end(), 0);
}

• 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