Submission #422928

#	Time	Username	Problem	Language	Result	Execution time	Memory
422928		TryMax	Rectangles (IOI19_rect)	C++17	37 / 100	939 ms	1048580 KiB

rect

#include "rect.h"
#include "bits/stdc++.h"

using namespace std;

const int N = 1e5 + 10, inf = 1e9 + 10;

//vector<vector<int>> a;
vector<vector<vector<bool>>> up, l;
vector<vector<vector<short int>>> ud, lr;

long long count_rectangles(vector<vector<int>> a){
    int n = a.size();
    int m = a[0].size();
    l.resize(n);
    for(int i = 0; i < n; ++i){
        l[i].resize(m);
        for(int j = 0; j < m; ++j)
            l[i][j].resize(m);
    }
    lr.resize(m);
    for(int i = 0; i < m; ++i){
        lr[i].resize(m);
        for(int j = 0; j < m; ++j)
            lr[i][j].resize(n);
    }
    up.resize(m);
    for(int i = 0; i < m; ++i){
        up[i].resize(n);
        for(int j = 0; j < n; ++j)
            up[i][j].resize(n);
    }
    ud.resize(n);
    for(int i = 0; i < n; ++i){
        ud[i].resize(n);
        for(int j = 0; j < n; ++j)
            ud[i][j].resize(m);
    }
    for(int i = 1; i < n; ++i){
        for(int j = 1; j < m - 1; ++j){
            int maxel = -inf, f = a[i][j - 1];
            for(int q = j; q < m - 1; ++q){
                maxel = max(maxel, a[i][q]);
                if(maxel < f && maxel < a[i][q + 1])
                    l[i][j][q] = 1;
            }
//            cout << l[i][j][m - 3] << " ";
        }
//        cout << endl;
    }
    for(int i = 1; i < m - 1; ++i)
        for(int j = i; j < m - 1; ++j)
            for(int q = 1; q < n - 1; ++q)
                lr[i][j][q] = lr[i][j][q - 1] + l[q][i][j];
    for(int i = 1; i < m; ++i){
        for(int j = 1; j < n - 1; ++j){
            int maxel = -inf, f = a[j - 1][i];
            for(int q = j; q < n - 1; ++q){
                maxel = max(maxel, a[q][i]);
                if(maxel < f && maxel < a[q + 1][i])
                    up[i][j][q] = 1;
            }
        }
    }
//    cout << up[1][1][1] << " " << up[2][1][1] << endl;
    for(int i = 1; i < n - 1; ++i)
        for(int j = i; j < n - 1; ++j)
            for(int q = 1; q < m - 1; ++q){
                ud[i][j][q] = ud[i][j][q - 1] + up[q][i][j];
//                cout << i << " " << j << " " << q << " " << ud[i][j][q - 1] << " " << ud[i][j][q] << " " << up[q][i][j] << endl;
            }
//    cout << ud[1][1][1] << endl;
//    cout << ud[1][1][2] << endl;
    int ans = 0;
    for(int i = 1; i < n - 1; ++i)
        for(int j = 1; j < m - 1; ++j)
            for(int i1 = i; i1 < n - 1; ++i1)
                for(int j1 = j; j1 < m - 1; ++j1){
//                    if(i == 1 && j == 1 && i1 == 1 && j1 == 2){
//                        cout << lr[j][j1][i1] - lr[j][j1][i - 1] << " " << ud[i][i1][j1] - ud[i][i1][j - 1] << endl;
//                    }
                    if(lr[j][j1][i1] - lr[j][j1][i - 1] == i1 - i + 1 &&
                    ud[i][i1][j1] - ud[i][i1][j - 1] == j1 - j + 1)
                        ++ans;
                }
    return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6

3 4
14 7 3 6
7 5 2 7
5 13 5 6
*/

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