oj.uz

Submission #145394

# Submission time Handle Problem Language Result Execution time Memory
145394 2019-08-19T19:29:49 Z jacynkaa Rectangles (IOI19_rect) C++14
59 / 100
 5000 ms 760728 KB 
#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> 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

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:72:5: note: in expansion of macro 'rep'
     rep(j, Q.size())
     ^~~
rect.cpp:79: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:175: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:175: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:178:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (l == R[i + 1][j].size())
             ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:184:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (k == D[i][j + 1].size())
             ~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 589852 KB Output is correct
2 Correct 534 ms 590116 KB Output is correct
3 Correct 531 ms 589944 KB Output is correct
4 Correct 532 ms 590044 KB Output is correct
5 Correct 539 ms 589904 KB Output is correct
6 Correct 569 ms 589936 KB Output is correct
7 Correct 592 ms 590016 KB Output is correct
8 Correct 550 ms 589944 KB Output is correct
9 Correct 532 ms 589944 KB Output is correct
10 Correct 533 ms 589984 KB Output is correct
11 Correct 546 ms 589952 KB Output is correct
12 Correct 535 ms 589944 KB Output is correct
13 Correct 532 ms 589816 KB Output is correct
14 Correct 539 ms 589816 KB Output is correct
15 Correct 536 ms 589816 KB Output is correct
16 Correct 535 ms 589764 KB Output is correct
17 Correct 541 ms 589684 KB Output is correct
18 Correct 574 ms 589776 KB Output is correct
19 Correct 551 ms 590084 KB Output is correct
20 Correct 538 ms 589996 KB Output is correct
21 Correct 537 ms 589756 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 589852 KB Output is correct
2 Correct 534 ms 590116 KB Output is correct
3 Correct 531 ms 589944 KB Output is correct
4 Correct 532 ms 590044 KB Output is correct
5 Correct 539 ms 589904 KB Output is correct
6 Correct 569 ms 589936 KB Output is correct
7 Correct 592 ms 590016 KB Output is correct
8 Correct 550 ms 589944 KB Output is correct
9 Correct 532 ms 589944 KB Output is correct
10 Correct 533 ms 589984 KB Output is correct
11 Correct 546 ms 589952 KB Output is correct
12 Correct 535 ms 589944 KB Output is correct
13 Correct 532 ms 589816 KB Output is correct
14 Correct 539 ms 589816 KB Output is correct
15 Correct 536 ms 589816 KB Output is correct
16 Correct 535 ms 589764 KB Output is correct
17 Correct 556 ms 591056 KB Output is correct
18 Correct 553 ms 591040 KB Output is correct
19 Correct 540 ms 591072 KB Output is correct
20 Correct 541 ms 590436 KB Output is correct
21 Correct 560 ms 590672 KB Output is correct
22 Correct 546 ms 590744 KB Output is correct
23 Correct 554 ms 590840 KB Output is correct
24 Correct 552 ms 590456 KB Output is correct
25 Correct 541 ms 589684 KB Output is correct
26 Correct 574 ms 589776 KB Output is correct
27 Correct 551 ms 590084 KB Output is correct
28 Correct 538 ms 589996 KB Output is correct
29 Correct 537 ms 589756 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 589852 KB Output is correct
2 Correct 534 ms 590116 KB Output is correct
3 Correct 531 ms 589944 KB Output is correct
4 Correct 532 ms 590044 KB Output is correct
5 Correct 539 ms 589904 KB Output is correct
6 Correct 569 ms 589936 KB Output is correct
7 Correct 592 ms 590016 KB Output is correct
8 Correct 550 ms 589944 KB Output is correct
9 Correct 532 ms 589944 KB Output is correct
10 Correct 533 ms 589984 KB Output is correct
11 Correct 546 ms 589952 KB Output is correct
12 Correct 535 ms 589944 KB Output is correct
13 Correct 532 ms 589816 KB Output is correct
14 Correct 539 ms 589816 KB Output is correct
15 Correct 536 ms 589816 KB Output is correct
16 Correct 535 ms 589764 KB Output is correct
17 Correct 556 ms 591056 KB Output is correct
18 Correct 553 ms 591040 KB Output is correct
19 Correct 540 ms 591072 KB Output is correct
20 Correct 541 ms 590436 KB Output is correct
21 Correct 560 ms 590672 KB Output is correct
22 Correct 546 ms 590744 KB Output is correct
23 Correct 554 ms 590840 KB Output is correct
24 Correct 552 ms 590456 KB Output is correct
25 Correct 590 ms 596324 KB Output is correct
26 Correct 582 ms 596232 KB Output is correct
27 Correct 587 ms 596588 KB Output is correct
28 Correct 581 ms 592888 KB Output is correct
29 Correct 599 ms 593984 KB Output is correct
30 Correct 613 ms 594040 KB Output is correct
31 Correct 596 ms 594036 KB Output is correct
32 Correct 618 ms 594040 KB Output is correct
33 Correct 541 ms 589684 KB Output is correct
34 Correct 574 ms 589776 KB Output is correct
35 Correct 551 ms 590084 KB Output is correct
36 Correct 538 ms 589996 KB Output is correct
37 Correct 537 ms 589756 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 589852 KB Output is correct
2 Correct 534 ms 590116 KB Output is correct
3 Correct 531 ms 589944 KB Output is correct
4 Correct 532 ms 590044 KB Output is correct
5 Correct 539 ms 589904 KB Output is correct
6 Correct 569 ms 589936 KB Output is correct
7 Correct 592 ms 590016 KB Output is correct
8 Correct 550 ms 589944 KB Output is correct
9 Correct 532 ms 589944 KB Output is correct
10 Correct 533 ms 589984 KB Output is correct
11 Correct 546 ms 589952 KB Output is correct
12 Correct 535 ms 589944 KB Output is correct
13 Correct 532 ms 589816 KB Output is correct
14 Correct 539 ms 589816 KB Output is correct
15 Correct 536 ms 589816 KB Output is correct
16 Correct 535 ms 589764 KB Output is correct
17 Correct 556 ms 591056 KB Output is correct
18 Correct 553 ms 591040 KB Output is correct
19 Correct 540 ms 591072 KB Output is correct
20 Correct 541 ms 590436 KB Output is correct
21 Correct 560 ms 590672 KB Output is correct
22 Correct 546 ms 590744 KB Output is correct
23 Correct 554 ms 590840 KB Output is correct
24 Correct 552 ms 590456 KB Output is correct
25 Correct 590 ms 596324 KB Output is correct
26 Correct 582 ms 596232 KB Output is correct
27 Correct 587 ms 596588 KB Output is correct
28 Correct 581 ms 592888 KB Output is correct
29 Correct 599 ms 593984 KB Output is correct
30 Correct 613 ms 594040 KB Output is correct
31 Correct 596 ms 594036 KB Output is correct
32 Correct 618 ms 594040 KB Output is correct
33 Correct 1028 ms 632204 KB Output is correct
34 Correct 980 ms 620604 KB Output is correct
35 Correct 943 ms 620760 KB Output is correct
36 Correct 865 ms 609292 KB Output is correct
37 Correct 1257 ms 662864 KB Output is correct
38 Correct 1249 ms 662760 KB Output is correct
39 Correct 1267 ms 663352 KB Output is correct
40 Correct 1366 ms 658592 KB Output is correct
41 Correct 978 ms 614608 KB Output is correct
42 Correct 1069 ms 619872 KB Output is correct
43 Correct 1303 ms 633520 KB Output is correct
44 Correct 1295 ms 635640 KB Output is correct
45 Correct 941 ms 614276 KB Output is correct
46 Correct 902 ms 612576 KB Output is correct
47 Correct 1255 ms 632076 KB Output is correct
48 Correct 1267 ms 633012 KB Output is correct
49 Correct 541 ms 589684 KB Output is correct
50 Correct 574 ms 589776 KB Output is correct
51 Correct 551 ms 590084 KB Output is correct
52 Correct 538 ms 589996 KB Output is correct
53 Correct 537 ms 589756 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 590652 KB Output is correct
2 Correct 544 ms 590428 KB Output is correct
3 Correct 546 ms 590072 KB Output is correct
4 Correct 540 ms 589788 KB Output is correct
5 Correct 549 ms 590456 KB Output is correct
6 Correct 596 ms 590324 KB Output is correct
7 Correct 623 ms 590328 KB Output is correct
8 Correct 553 ms 590180 KB Output is correct
9 Correct 633 ms 590304 KB Output is correct
10 Correct 575 ms 590072 KB Output is correct
11 Correct 621 ms 590204 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 589868 KB Output is correct
2 Correct 3251 ms 719704 KB Output is correct
3 Execution timed out 5123 ms 760728 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 589852 KB Output is correct
2 Correct 534 ms 590116 KB Output is correct
3 Correct 531 ms 589944 KB Output is correct
4 Correct 532 ms 590044 KB Output is correct
5 Correct 539 ms 589904 KB Output is correct
6 Correct 569 ms 589936 KB Output is correct
7 Correct 592 ms 590016 KB Output is correct
8 Correct 550 ms 589944 KB Output is correct
9 Correct 532 ms 589944 KB Output is correct
10 Correct 533 ms 589984 KB Output is correct
11 Correct 546 ms 589952 KB Output is correct
12 Correct 535 ms 589944 KB Output is correct
13 Correct 532 ms 589816 KB Output is correct
14 Correct 539 ms 589816 KB Output is correct
15 Correct 536 ms 589816 KB Output is correct
16 Correct 535 ms 589764 KB Output is correct
17 Correct 556 ms 591056 KB Output is correct
18 Correct 553 ms 591040 KB Output is correct
19 Correct 540 ms 591072 KB Output is correct
20 Correct 541 ms 590436 KB Output is correct
21 Correct 560 ms 590672 KB Output is correct
22 Correct 546 ms 590744 KB Output is correct
23 Correct 554 ms 590840 KB Output is correct
24 Correct 552 ms 590456 KB Output is correct
25 Correct 590 ms 596324 KB Output is correct
26 Correct 582 ms 596232 KB Output is correct
27 Correct 587 ms 596588 KB Output is correct
28 Correct 581 ms 592888 KB Output is correct
29 Correct 599 ms 593984 KB Output is correct
30 Correct 613 ms 594040 KB Output is correct
31 Correct 596 ms 594036 KB Output is correct
32 Correct 618 ms 594040 KB Output is correct
33 Correct 1028 ms 632204 KB Output is correct
34 Correct 980 ms 620604 KB Output is correct
35 Correct 943 ms 620760 KB Output is correct
36 Correct 865 ms 609292 KB Output is correct
37 Correct 1257 ms 662864 KB Output is correct
38 Correct 1249 ms 662760 KB Output is correct
39 Correct 1267 ms 663352 KB Output is correct
40 Correct 1366 ms 658592 KB Output is correct
41 Correct 978 ms 614608 KB Output is correct
42 Correct 1069 ms 619872 KB Output is correct
43 Correct 1303 ms 633520 KB Output is correct
44 Correct 1295 ms 635640 KB Output is correct
45 Correct 941 ms 614276 KB Output is correct
46 Correct 902 ms 612576 KB Output is correct
47 Correct 1255 ms 632076 KB Output is correct
48 Correct 1267 ms 633012 KB Output is correct
49 Correct 576 ms 590652 KB Output is correct
50 Correct 544 ms 590428 KB Output is correct
51 Correct 546 ms 590072 KB Output is correct
52 Correct 540 ms 589788 KB Output is correct
53 Correct 549 ms 590456 KB Output is correct
54 Correct 596 ms 590324 KB Output is correct
55 Correct 623 ms 590328 KB Output is correct
56 Correct 553 ms 590180 KB Output is correct
57 Correct 633 ms 590304 KB Output is correct
58 Correct 575 ms 590072 KB Output is correct
59 Correct 621 ms 590204 KB Output is correct
60 Correct 547 ms 589868 KB Output is correct
61 Correct 3251 ms 719704 KB Output is correct
62 Execution timed out 5123 ms 760728 KB Time limit exceeded
63 Halted 0 ms 0 KB -