Submission #222924

#	Time	Username	Problem	Language	Result	Execution time	Memory
222924		MrDomino	Rectangles (IOI19_rect)	C++14	Compilation error	0 ms	0 KiB

rect

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

using namespace std;

typedef long long ll;

class RMQ
{
private:
    int n;
    vector<int> lg;
    vector<vector<int>> rmq;
public:
    RMQ(vector<int> a)
    {
        n = (int) a.size();
        lg.resize(n + 1, 0);
        for (int i = 2; i <= n; i++)
        {
            lg[i] = 1 + lg[i / 2];
        }
        rmq.resize(lg[n] + 1);
        for (int k = 0; k < (int) rmq.size(); k++)
        {
            rmq[k].resize(n);
        }
        for (int i = 0; i < n; i++)
        {
            rmq[0][i] = a[i];
        }
        for (int k = 1; k < (int) rmq.size(); k++)
        {
            for (int i = 0; i + (1 << k) - 1 < n; i++)
            {
                rmq[k][i] = max(rmq[k - 1][i], rmq[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
    int get(int l, int r)
    {
        int k = lg[r - l + 1];
        return max(rmq[k][l], rmq[k][r - (1 << k) + 1]);
    }
};

long long count_rectangles(vector<vector<int>> a)
{
    ll sol = 0;
    int n = (int) a.size();
    int m = (int) a[0].size();
    vector<vector<bool>> good(m);
    vector<RMQ> rmq;
    for (int i = 0; i < n; i++)
    {
        rmq.push_back(RMQ(a[i]));
    }
    for (int i = 0; i < m; i++)
    {
        good[i].resize(m);
    }
    for (int r1 = 1; r1 < n - 1; r1++)
    {
        for (int i = 0; i < m; i++)
        {
            for (int j = i; j < m; j++)
            {
                good[i][j] = 1;
            }
        }
        vector<int> mx(m);
        for (int r2 = r1; r2 < n - 1; r2++)
        {
            for (int j = 0; j < m; j++)
            {
                mx[j] = max(mx[j], a[r2][j]);
            }
            for (int i = 0; i < m; i++)
            {
                for (int j = i; j < m; j++)
                {
                    if (rmq[r2].get(i, j) >= min(a[r2][i - 1], a[r2][j + 1]))
                    {
                        good[i][j] = 0;
                    }
                }
            }
            vector<bool> ok(m);
            for (int j = 0; j < m; j++)
            {
                ok[j] = (mx[j] < min(a[r1 - 1][j], a[r2 + 1][j]));
            }
            for (int c1 = 1; c1 < m - 1; c1++)
            {
                if (ok[c1])
                {
                    for (int c2 = c1; c2 < m - 1; c2++)
                    {
                        if (ok[c2] == 0)
                        {
                            break;
                        }
                        if (good[c1][c2])
                        {
                            sol++;
                        }
                    }
                }
            }
        }
    }
    return sol;
}
int main()
{
    vector<vector<int>> a(6);
    a[0] = {4, 8, 7, 5, 6};
    a[1] = {7, 4, 10, 3, 5};
    a[2] = {9, 7, 20, 14, 2};
    a[3] = {9, 14, 7, 5, 6};
    a[4] = {5, 7, 5, 2, 7};
    a[5] = {4, 5, 13, 5, 6};
    cout << count_rectangles(a) << "\n";
}

Compilation message (stderr)

/tmp/cclYVe1X.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccR96cJI.o:rect.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status