Submission #145401

#	Time	Username	Problem	Language	Result	Execution time	Memory
145401		jacynkaa	Rectangles (IOI19_rect)	C++14	59 / 100	5140 ms	761396 KiB

rect

#include <bits/stdc++.h>
#include <math.h>
#include <chrono>
using namespace std;
#define mp make_pair
#define st first
#define nd second
#define pii pair<int, int>
#define pb push_back
#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> prawo[MAXN][MAXN];
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;

vector<pair<pii, pii>> odp;

void wypisz()
{
    sort(all(odp));
    for (auto a : odp)
    {
        cerr << a.st.st << " " << a.st.nd << " " << a.nd.st << " " << a.nd.nd << endl;
    }
}

void wypelnij2prawo()
{
    rep(j, m)
    {
        vector<pii> X(max(m, n) + 10, {-1, -1});
        for (int i = n - 1; i >= 0; i--)
            for (int a : prawo[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(max(m, n) + 10, {-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<pii> X;
    rep(j, Q.size())
        X.pb({Q[j], j});
    vector<vector<int>> P(Q.size());
    sort(all(X));
    reverse(all(X));
    set<pii> S;
    int j = 0;
    while (j < Q.size())
    {
        int k = j;

        while (k + 1 < m && X[j].st == X[k + 1].st)
            k++;
        for (int l = j; l <= k; l++)
        {
            // cerr << X[l].nd << " " << X[l].st << endl;
            S.insert({X[l].nd, X[l].st});
        }
        for (int l = j; l <= k; l++)
        {
            auto r = S.find({X[l].nd, X[l].st});
            auto q = (r == S.begin()) ? r : next(r, -1);
            auto s = (next(r, 1) == S.end()) ? r : next(r, 1);

            //   cerr << q->st << " " << r->st << " " << s->st << endl;

            if (r->st - q->st - 1 > 0) //popraawic!!!!
            {
                P[q->st].pb(r->st - q->st - 1);
                //cerr << q->st << " ech1 " << r->st << endl;
            }

            if (s->st - r->st - 1 > 0 && s->nd != r->nd)
            {
                P[r->st].pb(s->st - r->st - 1);
                //cerr << s->st << " ech2 " << r->st << endl;
            }
        }
        j = k + 1;
    }
    return P;
}

const int rozmiar = (1 << 12);
int ile[3 * rozmiar];
vector<int> zap;

void dodaj(int x)
{
    x += rozmiar;
    while (x > 0)
    {
        zap.pb(x);
        ile[x]++;
        x /= 2;
    }
}
int get(int x)
{
    int p = rozmiar;
    int q = rozmiar + x;
    int wynik = 0;
    while (p <= q)
    {
        if (q % 2 == 0)
        {
            wynik += ile[q];
            q--;
        }
        p /= 2;
        q /= 2;
    }
    //what(wynik);
    return wynik;
}
void clear()
{
    for (int a : zap)
        ile[a] = 0;
    zap.clear();
}

void solve(int i, int j)
{
    //s   cerr << i << " " << j << endl;
    if (R[i + 1][j].size() == 0 || D[i][j + 1].size() == 0)
        return;
    for (auto &B : D[i][j + 1])
        swap(B.st, B.nd);
    sort(all(R[i + 1][j]), greater<pii>());
    sort(all(D[i][j + 1]), greater<pii>());
    /*
    cerr << "obecne tutaj::" << endl;
    for (auto A : D[i][j + 1])
        cerr << A.st << " " << A.nd << endl;
    cerr << endl;
    for (auto A : R[i + 1][j])
        cerr << A.st << " " << A.nd << endl;
    cerr << "koniec" << endl;
*/
    int k = 0;
    int l = 0;

    while (l != R[i + 1][j].size() || k != D[i][j + 1].size())
    {

        if (l == R[i + 1][j].size())
        {
            dodaj(D[i][j + 1][k].nd);
            k++;
            continue;
        }
        if (k == D[i][j + 1].size())
        {
            ans += get(R[i + 1][j][l].nd);
            l++;
            continue;
        }
        if (R[i + 1][j][l].st <= D[i][j + 1][k].st)
        {
            dodaj(D[i][j + 1][k].nd);
            k++;
            continue;
        }
        else
        {
            ans += get(R[i + 1][j][l].nd);
            l++;
            continue;
        }
    }
    clear();
}

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)
            prawo[i][j] = X[j];
    }
    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];
    }
    wypelnij2prawo();
    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:12:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i = 0; i < (n); ++i)
                                     ^
rect.cpp:69:5: note: in expansion of macro 'rep'
     rep(j, Q.size())
     ^~~
rect.cpp:76:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (j < Q.size())
            ~~^~~~~~~~~~
rect.cpp: In function 'void solve(int, int)':
rect.cpp:172:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (l != R[i + 1][j].size() || k != D[i][j + 1].size())
            ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:172:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (l != R[i + 1][j].size() || k != D[i][j + 1].size())
                                       ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:175:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (l == R[i + 1][j].size())
             ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:181:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (k == D[i][j + 1].size())
             ~~^~~~~~~~~~~~~~~~~~~~~

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