Submission #145432

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

rect

#include <bits/stdc++.h>
#include <math.h>
#include <chrono>
using namespace std;
#pragma GCC optimize("-O3")
#define endl "\n"
#define mp make_pair
#define st first
#define nd second
#define pii pair<int, int>
#define pb push_back
#define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10) //cin.tie(0); cout.tie(0);
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FWD(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fwd(i, a, b) for (int i = (a); i < (b); ++i)
#define all(c) (c).begin(), (c).end()
#define what(x) cerr << #x << " is " << x << endl;

const int MAXN = 2505; //UWAGA

vector<int> dol[MAXN][MAXN];
vector<pii> R[MAXN][MAXN];
vector<pii> D[MAXN][MAXN];
int n, m;
int tab[MAXN][MAXN];
long long ans = 0;

void wypelnij2prawo()
{
    rep(j, m)
    {
        vector<pii> X(3e3, {-1, -1});
        for (int i = n - 1; i >= 0; i--)
            for (int a : dol[i][j])
            {
                X[a] = (X[a].st == i + 1) ? mp(i, X[a].nd + 1) : mp(i, 1);
                R[i][j].pb({a, X[a].nd}); //glebokosc i ile
            }
    }
}

void wypelnij2dol()
{
    rep(i, n)
    {
        vector<pii> X(3e3, {-1, -1});
        for (int j = m - 1; j >= 0; j--)
            for (int a : dol[i][j])
            {
                X[a] = (X[a].st == j + 1) ? mp(j, X[a].nd + 1) : mp(j, 1);
                D[i][j].pb({a, X[a].nd}); //glebokosc i ile
            }
    }
}

vector<vector<int>> wypelnij1(vector<int> &Q)
{

    vector<vector<int>> P(Q.size());
    stack<pii> S;
    rep(i, Q.size())
    {
        while (!S.empty() && S.top().st < Q[i])
            S.pop();
        if (!S.empty() && i - S.top().nd - 1 > 0)
            P[S.top().nd].pb(i - S.top().nd - 1);
        S.push(mp(Q[i], i));
    }
    while (!S.empty())
        S.pop();
    for (int i = Q.size() - 1; i >= 0; i--)
    {
        while (!S.empty() && S.top().st < Q[i])
            S.pop();
        if (!S.empty() && S.top().nd - i - 1 > 0 && S.top().st != Q[i])
            P[i].pb(S.top().nd - i - 1);
        S.push(mp(Q[i], i));
    }
    return P;
}

void solve(int i, int j)
{

    for (auto A : D[i][j + 1])
        for (auto B : R[i + 1][j])
            if (B.nd >= A.st && A.nd >= B.st)
                ans++;
}

long long count_rectangles(vector<vector<int32_t>> A)
{
    n = A.size();
    m = A[0].size();
    rep(i, n) rep(j, m) tab[i][j] = A[i][j];
    rep(i, n)
    {
        auto X = wypelnij1(A[i]);
        rep(j, m)
            dol[i][j] = X[j];
    }
    wypelnij2prawo();
    rep(j, m)
    {
        vector<int> Y;
        rep(i, n)
            Y.pb(tab[i][j]);
        auto X = wypelnij1(Y);
        rep(i, n)
            dol[i][j] = X[i];
    }
    wypelnij2dol();
    /* 
    cerr << "DOL" << endl;
    rep(i, n)
    {
        rep(j, m)
        {
            cerr << i << " " << j << "::  ";
            for (auto a : D[i][j])
                cerr << a.st << " " << a.nd << ", ";
            cerr << endl;
            // cout << a << "              /// ";
        }
        cerr << endl;
    }
    cerr << "PRAWO" << endl;
    rep(i, n)
    {
        rep(j, m)
        {
            cerr << i << " " << j << "::  ";
            for (auto a : R[i][j])
                cerr << a.st << " " << a.nd << ", ";
            // cout << a << "              /// ";
            cerr << endl;
        }
        cerr << endl;
    }
    */
    rep(i, n - 1) rep(j, m - 1) solve(i, j);
    return ans;
}

main()
{
    _upgrade;
    string S;
    cin >> S;
    int a, b;
    cin >> a >> b;
    vector<vector<int>> X(a, vector<int>(b));
    rep(i, a) rep(j, b) cin >> X[i][j];
    cout << count_rectangles(X)
         << endl;
    // wypisz();
}

Compilation message (stderr)

rect.cpp: In function 'std::vector<std::vector<int> > wypelnij1(std::vector<int>&)':
rect.cpp:15:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i = 0; i < (n); ++i)
                                     ^
rect.cpp:62:5: note: in expansion of macro 'rep'
     rep(i, Q.size())
     ^~~
rect.cpp: At global scope:
rect.cpp:146:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
/tmp/ccC11kCL.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc8dTdNx.o:rect.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status