oj.uz

Submission #172011

# Submission time Handle Problem Language Result Execution time Memory
172011 2019-12-30T20:05:38 Z jacynkaa Rectangles (IOI19_rect) C++14
50 / 100
 3031 ms 649852 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 = 2502; //UWAGA

vector<int> dol[MAXN][MAXN];
vector<pair<short, short>> R[MAXN][MAXN];
vector<pair<short, short>> 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
            }
            dol[i][j].resize(0);
            dol[i][j].shrink_to_fit();
        }
    }
}

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;
}

const int rozmiar = (1 << 12);
int DA[2 * rozmiar];
// value[i] += v
void dodaj(int i, int v = 1)
{
    for (; i < MAXN; i |= i + 1)
        DA[i] += v;
}
// Returns value[0] + value[1] + ... + value[i]
int get(int i)
{
    int s = 0;
    while (i >= 0)
    {
        s += DA[i];
        i = (i & (i + 1)) - 1;
    }
    return s;
}

void clear()
{
    rep(i, rozmiar * 2)
        DA[i] = 0;
}

void solve(int i, int j)
{
    //s   cerr << i << " " << j << endl;
    if (R[i + 1][j].size() * D[i][j + 1].size() <= 1000)
    {
        for (auto &A : D[i][j + 1])
            for (auto &B : R[i + 1][j])
                if (B.nd >= A.st && A.nd >= B.st)
                    ans++;
        return;
    }
    for (auto &B : D[i][j + 1])
        swap(B.st, B.nd);
    sort(all(R[i + 1][j]), greater<pair<short, short>>());
    sort(all(D[i][j + 1]), greater<pair<short, short>>());
    /*
    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())
        {
            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
        {
            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)
            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;
}

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:66:5: note: in expansion of macro 'rep'
     rep(i, Q.size())
     ^~~
rect.cpp: In function 'void solve(int, int)':
rect.cpp:140: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:140: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:143:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (l == R[i + 1][j].size())
             ~~^~~~~~~~~~~~~~~~~~~~~
rect.cpp:149: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 406 ms 441412 KB Output is correct
2 Correct 396 ms 441648 KB Output is correct
3 Correct 401 ms 441644 KB Output is correct
4 Correct 406 ms 441596 KB Output is correct
5 Correct 396 ms 441464 KB Output is correct
6 Correct 396 ms 441608 KB Output is correct
7 Correct 398 ms 441592 KB Output is correct
8 Correct 394 ms 441704 KB Output is correct
9 Correct 399 ms 441596 KB Output is correct
10 Correct 430 ms 441524 KB Output is correct
11 Correct 398 ms 441720 KB Output is correct
12 Correct 395 ms 441592 KB Output is correct
13 Correct 399 ms 441384 KB Output is correct
14 Correct 414 ms 441336 KB Output is correct
15 Correct 393 ms 441464 KB Output is correct
16 Correct 404 ms 441396 KB Output is correct
17 Correct 393 ms 441404 KB Output is correct
18 Correct 442 ms 441292 KB Output is correct
19 Correct 396 ms 441564 KB Output is correct
20 Correct 405 ms 441548 KB Output is correct
21 Correct 396 ms 441520 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 441412 KB Output is correct
2 Correct 396 ms 441648 KB Output is correct
3 Correct 401 ms 441644 KB Output is correct
4 Correct 406 ms 441596 KB Output is correct
5 Correct 396 ms 441464 KB Output is correct
6 Correct 396 ms 441608 KB Output is correct
7 Correct 398 ms 441592 KB Output is correct
8 Correct 394 ms 441704 KB Output is correct
9 Correct 399 ms 441596 KB Output is correct
10 Correct 430 ms 441524 KB Output is correct
11 Correct 398 ms 441720 KB Output is correct
12 Correct 395 ms 441592 KB Output is correct
13 Correct 399 ms 441384 KB Output is correct
14 Correct 414 ms 441336 KB Output is correct
15 Correct 393 ms 441464 KB Output is correct
16 Correct 404 ms 441396 KB Output is correct
17 Correct 401 ms 442224 KB Output is correct
18 Correct 402 ms 442236 KB Output is correct
19 Correct 414 ms 442400 KB Output is correct
20 Correct 415 ms 441964 KB Output is correct
21 Correct 418 ms 442020 KB Output is correct
22 Correct 401 ms 441976 KB Output is correct
23 Correct 397 ms 442104 KB Output is correct
24 Correct 395 ms 441884 KB Output is correct
25 Correct 393 ms 441404 KB Output is correct
26 Correct 442 ms 441292 KB Output is correct
27 Correct 396 ms 441564 KB Output is correct
28 Correct 405 ms 441548 KB Output is correct
29 Correct 396 ms 441520 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 441412 KB Output is correct
2 Correct 396 ms 441648 KB Output is correct
3 Correct 401 ms 441644 KB Output is correct
4 Correct 406 ms 441596 KB Output is correct
5 Correct 396 ms 441464 KB Output is correct
6 Correct 396 ms 441608 KB Output is correct
7 Correct 398 ms 441592 KB Output is correct
8 Correct 394 ms 441704 KB Output is correct
9 Correct 399 ms 441596 KB Output is correct
10 Correct 430 ms 441524 KB Output is correct
11 Correct 398 ms 441720 KB Output is correct
12 Correct 395 ms 441592 KB Output is correct
13 Correct 399 ms 441384 KB Output is correct
14 Correct 414 ms 441336 KB Output is correct
15 Correct 393 ms 441464 KB Output is correct
16 Correct 404 ms 441396 KB Output is correct
17 Correct 401 ms 442224 KB Output is correct
18 Correct 402 ms 442236 KB Output is correct
19 Correct 414 ms 442400 KB Output is correct
20 Correct 415 ms 441964 KB Output is correct
21 Correct 418 ms 442020 KB Output is correct
22 Correct 401 ms 441976 KB Output is correct
23 Correct 397 ms 442104 KB Output is correct
24 Correct 395 ms 441884 KB Output is correct
25 Correct 418 ms 445504 KB Output is correct
26 Correct 415 ms 445500 KB Output is correct
27 Correct 440 ms 445560 KB Output is correct
28 Correct 412 ms 443844 KB Output is correct
29 Correct 423 ms 444376 KB Output is correct
30 Correct 422 ms 444408 KB Output is correct
31 Correct 426 ms 444412 KB Output is correct
32 Correct 422 ms 444408 KB Output is correct
33 Correct 393 ms 441404 KB Output is correct
34 Correct 442 ms 441292 KB Output is correct
35 Correct 396 ms 441564 KB Output is correct
36 Correct 405 ms 441548 KB Output is correct
37 Correct 396 ms 441520 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 441412 KB Output is correct
2 Correct 396 ms 441648 KB Output is correct
3 Correct 401 ms 441644 KB Output is correct
4 Correct 406 ms 441596 KB Output is correct
5 Correct 396 ms 441464 KB Output is correct
6 Correct 396 ms 441608 KB Output is correct
7 Correct 398 ms 441592 KB Output is correct
8 Correct 394 ms 441704 KB Output is correct
9 Correct 399 ms 441596 KB Output is correct
10 Correct 430 ms 441524 KB Output is correct
11 Correct 398 ms 441720 KB Output is correct
12 Correct 395 ms 441592 KB Output is correct
13 Correct 399 ms 441384 KB Output is correct
14 Correct 414 ms 441336 KB Output is correct
15 Correct 393 ms 441464 KB Output is correct
16 Correct 404 ms 441396 KB Output is correct
17 Correct 401 ms 442224 KB Output is correct
18 Correct 402 ms 442236 KB Output is correct
19 Correct 414 ms 442400 KB Output is correct
20 Correct 415 ms 441964 KB Output is correct
21 Correct 418 ms 442020 KB Output is correct
22 Correct 401 ms 441976 KB Output is correct
23 Correct 397 ms 442104 KB Output is correct
24 Correct 395 ms 441884 KB Output is correct
25 Correct 418 ms 445504 KB Output is correct
26 Correct 415 ms 445500 KB Output is correct
27 Correct 440 ms 445560 KB Output is correct
28 Correct 412 ms 443844 KB Output is correct
29 Correct 423 ms 444376 KB Output is correct
30 Correct 422 ms 444408 KB Output is correct
31 Correct 426 ms 444412 KB Output is correct
32 Correct 422 ms 444408 KB Output is correct
33 Correct 638 ms 476292 KB Output is correct
34 Correct 578 ms 463296 KB Output is correct
35 Correct 569 ms 469432 KB Output is correct
36 Incorrect 496 ms 456656 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 442048 KB Output is correct
2 Correct 463 ms 441956 KB Output is correct
3 Correct 438 ms 441556 KB Output is correct
4 Correct 400 ms 441472 KB Output is correct
5 Correct 409 ms 441868 KB Output is correct
6 Correct 407 ms 441720 KB Output is correct
7 Correct 409 ms 441804 KB Output is correct
8 Correct 411 ms 441784 KB Output is correct
9 Correct 405 ms 441820 KB Output is correct
10 Correct 408 ms 441464 KB Output is correct
11 Correct 406 ms 441720 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 441464 KB Output is correct
2 Correct 1559 ms 537568 KB Output is correct
3 Correct 3009 ms 647736 KB Output is correct
4 Correct 3031 ms 649852 KB Output is correct
5 Correct 3025 ms 649564 KB Output is correct
6 Correct 825 ms 483864 KB Output is correct
7 Correct 1217 ms 523512 KB Output is correct
8 Correct 1250 ms 527384 KB Output is correct
9 Correct 393 ms 441404 KB Output is correct
10 Correct 442 ms 441292 KB Output is correct
11 Correct 396 ms 441564 KB Output is correct
12 Correct 405 ms 441548 KB Output is correct
13 Correct 396 ms 441520 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 441412 KB Output is correct
2 Correct 396 ms 441648 KB Output is correct
3 Correct 401 ms 441644 KB Output is correct
4 Correct 406 ms 441596 KB Output is correct
5 Correct 396 ms 441464 KB Output is correct
6 Correct 396 ms 441608 KB Output is correct
7 Correct 398 ms 441592 KB Output is correct
8 Correct 394 ms 441704 KB Output is correct
9 Correct 399 ms 441596 KB Output is correct
10 Correct 430 ms 441524 KB Output is correct
11 Correct 398 ms 441720 KB Output is correct
12 Correct 395 ms 441592 KB Output is correct
13 Correct 399 ms 441384 KB Output is correct
14 Correct 414 ms 441336 KB Output is correct
15 Correct 393 ms 441464 KB Output is correct
16 Correct 404 ms 441396 KB Output is correct
17 Correct 401 ms 442224 KB Output is correct
18 Correct 402 ms 442236 KB Output is correct
19 Correct 414 ms 442400 KB Output is correct
20 Correct 415 ms 441964 KB Output is correct
21 Correct 418 ms 442020 KB Output is correct
22 Correct 401 ms 441976 KB Output is correct
23 Correct 397 ms 442104 KB Output is correct
24 Correct 395 ms 441884 KB Output is correct
25 Correct 418 ms 445504 KB Output is correct
26 Correct 415 ms 445500 KB Output is correct
27 Correct 440 ms 445560 KB Output is correct
28 Correct 412 ms 443844 KB Output is correct
29 Correct 423 ms 444376 KB Output is correct
30 Correct 422 ms 444408 KB Output is correct
31 Correct 426 ms 444412 KB Output is correct
32 Correct 422 ms 444408 KB Output is correct
33 Correct 638 ms 476292 KB Output is correct
34 Correct 578 ms 463296 KB Output is correct
35 Correct 569 ms 469432 KB Output is correct
36 Incorrect 496 ms 456656 KB Output isn't correct
37 Halted 0 ms 0 KB -