Submission #1071245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071245		j_vdd16	Rectangles (IOI19_rect)	C++17	72 / 100	5055 ms	1048576 KiB

rect

#include "rect.h"

#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define ll long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

struct MSTree {
    int n, N;
    vvi tree;

    MSTree() = default;
    MSTree(const vvi& values, int sz) {
        n = sz;
        N = 1;
        while (N < n) N *= 2;

        tree = vvi(2 * N);
        loop(i, values.size()) {
            for (int j : values[i]) {
                tree[N + j].push_back(i); 
            }
        }

        for (int i = N - 1; i >= 1; i--) {
            tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
        }
    }

    vi merge(const vi& a, const vi& b) {
        int idx1 = 0, idx2 = 0;
        vi out;
        while (idx1 < a.size() && idx2 < b.size()) {
            if (a[idx1] < b[idx2]) {
                idx1++;
            }
            else if (a[idx1] > b[idx2]) {
                idx2++;
            }
            else {
                out.push_back(a[idx1]);
                idx1++;
                idx2++;
            }
        }

        return out;
    }

    vi getRange(int l, int r, int i = 1, int tl = 0, int tr = -1) {
        if (tr == -1) {
            tr = N;
        }

        if (tr <= l || tl >= r) {
            cout << "ERROR" << endl;
            return {};
        }

        if (tl >= l && tr <= r) {
            return tree[i];
        }

        int tm = (tl + tr) / 2;
        if (tm >= r) {
            return getRange(l, r, i * 2, tl, tm);
        }
        if (tm <= l) {
            return getRange(l, r, i * 2 + 1, tm, tr);
        }
        return merge(getRange(l, r, i * 2, tl, tm), getRange(l, r, i * 2 + 1, tm, tr));
    }
};

long long count_rectangles(vvi a) {
	int n = a.size();
    int m = a[0].size();

    vector<vvi> validRows(m, vvi(m));
    for (int i = 1; i < n - 1; i++) {
        map<int, vi, greater<int>> values;
        loop(j, m) {
            values[a[i][j]].push_back(j);
        }

        map<int, int> rec;
        for (auto [val, vec] : values) {
            loop(idx, vec.size()) {
                if (rec.size() == 0) {
                    rec[vec[idx]] = val;
                    continue;
                }

                auto next = rec.upper_bound(vec[idx]);
                if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
                    validRows[vec[idx]][next->first].push_back(i);
                }

                if (next != rec.begin()) {
                    next--;
                    if (vec[idx] - next->first > 1) {
                        validRows[next->first][vec[idx]].push_back(i);
                    }
                }

                rec[vec[idx]] = val;
            }
        }
    }
    vector<vvi> validCols(n, vvi(n));
    for (int j = 1; j < m - 1; j++) {
        map<int, vi, greater<int>> values;
        loop(i, n) {
            values[a[i][j]].push_back(i);
        }
        
        map<int, int> rec;
        for (auto [val, vec] : values) {
            loop(idx, vec.size()) {
                if (rec.size() == 0) {
                    rec[vec[idx]] = val;
                    continue;
                }

                auto next = rec.upper_bound(vec[idx]);
                if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
                    validCols[vec[idx]][next->first].push_back(j);
                }

                if (next != rec.begin()) {
                    next--;
                    if (vec[idx] - next->first > 1) {
                        validCols[next->first][vec[idx]].push_back(j);
                    }
                }

                rec[vec[idx]] = val;
            }
        }
    }

    vector<MSTree> trees(n);
    loop(i, n) {
        trees[i] = MSTree(validCols[i], m);
        validCols[i].clear();
    }

    //bottleneck
    ll result = 0;
    for (int j1 = 0; j1 < m; j1++) {
        for (int j2 = j1 + 2; j2 < m; j2++) {
            const auto& valid = validRows[j1][j2];

            int furthest = -1;
            loop(idx, valid.size()) {
                //this happens O(n * m) times

                if (furthest < idx) {
                    furthest = idx;
                    while (furthest < valid.size() - 1 && valid[furthest + 1] == valid[furthest] + 1) {
                        furthest++;
                    }
                }

                vi validIndices = trees[valid[idx] - 1].getRange(j1 + 1, j2 - 1 + 1);
                auto upp = --upper_bound(all(validIndices), valid[furthest] + 1);
                int extra = upp - validIndices.begin() + 1;

                result += extra;

                // for (int idx2 = idx; idx2 <= furthest; idx2++) {
                //     const auto& relevantCols = validCols[valid[idx] - 1][valid[idx2] + 1];
                //     auto start = lower_bound(all(relevantCols), j1 + 1);
                //     auto end = lower_bound(all(relevantCols), j2 - 1);

                //     if (start != relevantCols.end() && end != relevantCols.end() && *start == j1 + 1 && *end == j2 - 1 && (end - start) == j2 - j1 - 2) {   
                //         result++;
                //     }
                // }
            }
        }
    }

    return result;
}

Compilation message (stderr)

rect.cpp: In constructor 'MSTree::MSTree(const vvi&, int)':
rect.cpp:20:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
rect.cpp:45:9: note: in expansion of macro 'loop'
   45 |         loop(i, values.size()) {
      |         ^~~~
rect.cpp: In member function 'vi MSTree::merge(const vi&, const vi&)':
rect.cpp:59:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         while (idx1 < a.size() && idx2 < b.size()) {
      |                ~~~~~^~~~~~~~~~
rect.cpp:59:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         while (idx1 < a.size() && idx2 < b.size()) {
      |                                   ~~~~~^~~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(vvi)':
rect.cpp:20:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
rect.cpp:114:13: note: in expansion of macro 'loop'
  114 |             loop(idx, vec.size()) {
      |             ^~~~
rect.cpp:121:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |                 if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
      |                                           ~~~~^~~~~~~~~~~~~~~~~
rect.cpp:20:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
rect.cpp:145:13: note: in expansion of macro 'loop'
  145 |             loop(idx, vec.size()) {
      |             ^~~~
rect.cpp:152:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |                 if (next != rec.end() && (idx == vec.size() - 1 || vec[idx + 1] > next->first) && next->first - vec[idx] > 1) {
      |                                           ~~~~^~~~~~~~~~~~~~~~~
rect.cpp:20:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define loop(X, N) for(int X = 0; X < (N); X++)
      |                                     ^
rect.cpp:181:13: note: in expansion of macro 'loop'
  181 |             loop(idx, valid.size()) {
      |             ^~~~
rect.cpp:186:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  186 |                     while (furthest < valid.size() - 1 && valid[furthest + 1] == valid[furthest] + 1) {
      |                            ~~~~~~~~~^~~~~~~~~~~~~~~~~~

• 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