oj.uz

Submission #172012

# Submission time Handle Problem Language Result Execution time Memory
172012 2019-12-30T20:10:12 Z jacynkaa Rectangles (IOI19_rect) C++14
50 / 100
 3021 ms 639596 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 < 2 * rozmiar; 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 441388 KB Output is correct
2 Correct 406 ms 441592 KB Output is correct
3 Correct 401 ms 441508 KB Output is correct
4 Correct 407 ms 441644 KB Output is correct
5 Correct 401 ms 441440 KB Output is correct
6 Correct 406 ms 441468 KB Output is correct
7 Correct 403 ms 441464 KB Output is correct
8 Correct 406 ms 441464 KB Output is correct
9 Correct 405 ms 441576 KB Output is correct
10 Correct 457 ms 441592 KB Output is correct
11 Correct 404 ms 441592 KB Output is correct
12 Correct 402 ms 441592 KB Output is correct
13 Correct 410 ms 441444 KB Output is correct
14 Correct 406 ms 441464 KB Output is correct
15 Correct 413 ms 441336 KB Output is correct
16 Correct 402 ms 441336 KB Output is correct
17 Correct 404 ms 441340 KB Output is correct
18 Correct 398 ms 441336 KB Output is correct
19 Correct 406 ms 441504 KB Output is correct
20 Correct 403 ms 441436 KB Output is correct
21 Correct 400 ms 441372 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 441388 KB Output is correct
2 Correct 406 ms 441592 KB Output is correct
3 Correct 401 ms 441508 KB Output is correct
4 Correct 407 ms 441644 KB Output is correct
5 Correct 401 ms 441440 KB Output is correct
6 Correct 406 ms 441468 KB Output is correct
7 Correct 403 ms 441464 KB Output is correct
8 Correct 406 ms 441464 KB Output is correct
9 Correct 405 ms 441576 KB Output is correct
10 Correct 457 ms 441592 KB Output is correct
11 Correct 404 ms 441592 KB Output is correct
12 Correct 402 ms 441592 KB Output is correct
13 Correct 410 ms 441444 KB Output is correct
14 Correct 406 ms 441464 KB Output is correct
15 Correct 413 ms 441336 KB Output is correct
16 Correct 402 ms 441336 KB Output is correct
17 Correct 407 ms 442228 KB Output is correct
18 Correct 409 ms 442368 KB Output is correct
19 Correct 449 ms 442236 KB Output is correct
20 Correct 405 ms 441956 KB Output is correct
21 Correct 404 ms 442104 KB Output is correct
22 Correct 408 ms 442052 KB Output is correct
23 Correct 431 ms 442076 KB Output is correct
24 Correct 436 ms 442040 KB Output is correct
25 Correct 404 ms 441340 KB Output is correct
26 Correct 398 ms 441336 KB Output is correct
27 Correct 406 ms 441504 KB Output is correct
28 Correct 403 ms 441436 KB Output is correct
29 Correct 400 ms 441372 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 441388 KB Output is correct
2 Correct 406 ms 441592 KB Output is correct
3 Correct 401 ms 441508 KB Output is correct
4 Correct 407 ms 441644 KB Output is correct
5 Correct 401 ms 441440 KB Output is correct
6 Correct 406 ms 441468 KB Output is correct
7 Correct 403 ms 441464 KB Output is correct
8 Correct 406 ms 441464 KB Output is correct
9 Correct 405 ms 441576 KB Output is correct
10 Correct 457 ms 441592 KB Output is correct
11 Correct 404 ms 441592 KB Output is correct
12 Correct 402 ms 441592 KB Output is correct
13 Correct 410 ms 441444 KB Output is correct
14 Correct 406 ms 441464 KB Output is correct
15 Correct 413 ms 441336 KB Output is correct
16 Correct 402 ms 441336 KB Output is correct
17 Correct 407 ms 442228 KB Output is correct
18 Correct 409 ms 442368 KB Output is correct
19 Correct 449 ms 442236 KB Output is correct
20 Correct 405 ms 441956 KB Output is correct
21 Correct 404 ms 442104 KB Output is correct
22 Correct 408 ms 442052 KB Output is correct
23 Correct 431 ms 442076 KB Output is correct
24 Correct 436 ms 442040 KB Output is correct
25 Correct 471 ms 445436 KB Output is correct
26 Correct 483 ms 445284 KB Output is correct
27 Correct 429 ms 445436 KB Output is correct
28 Correct 442 ms 443788 KB Output is correct
29 Correct 439 ms 444252 KB Output is correct
30 Correct 485 ms 444536 KB Output is correct
31 Correct 458 ms 444536 KB Output is correct
32 Correct 430 ms 444436 KB Output is correct
33 Correct 404 ms 441340 KB Output is correct
34 Correct 398 ms 441336 KB Output is correct
35 Correct 406 ms 441504 KB Output is correct
36 Correct 403 ms 441436 KB Output is correct
37 Correct 400 ms 441372 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 441388 KB Output is correct
2 Correct 406 ms 441592 KB Output is correct
3 Correct 401 ms 441508 KB Output is correct
4 Correct 407 ms 441644 KB Output is correct
5 Correct 401 ms 441440 KB Output is correct
6 Correct 406 ms 441468 KB Output is correct
7 Correct 403 ms 441464 KB Output is correct
8 Correct 406 ms 441464 KB Output is correct
9 Correct 405 ms 441576 KB Output is correct
10 Correct 457 ms 441592 KB Output is correct
11 Correct 404 ms 441592 KB Output is correct
12 Correct 402 ms 441592 KB Output is correct
13 Correct 410 ms 441444 KB Output is correct
14 Correct 406 ms 441464 KB Output is correct
15 Correct 413 ms 441336 KB Output is correct
16 Correct 402 ms 441336 KB Output is correct
17 Correct 407 ms 442228 KB Output is correct
18 Correct 409 ms 442368 KB Output is correct
19 Correct 449 ms 442236 KB Output is correct
20 Correct 405 ms 441956 KB Output is correct
21 Correct 404 ms 442104 KB Output is correct
22 Correct 408 ms 442052 KB Output is correct
23 Correct 431 ms 442076 KB Output is correct
24 Correct 436 ms 442040 KB Output is correct
25 Correct 471 ms 445436 KB Output is correct
26 Correct 483 ms 445284 KB Output is correct
27 Correct 429 ms 445436 KB Output is correct
28 Correct 442 ms 443788 KB Output is correct
29 Correct 439 ms 444252 KB Output is correct
30 Correct 485 ms 444536 KB Output is correct
31 Correct 458 ms 444536 KB Output is correct
32 Correct 430 ms 444436 KB Output is correct
33 Correct 641 ms 476260 KB Output is correct
34 Correct 562 ms 463148 KB Output is correct
35 Correct 578 ms 469524 KB Output is correct
36 Incorrect 508 ms 456688 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 419 ms 442000 KB Output is correct
2 Correct 411 ms 441976 KB Output is correct
3 Correct 414 ms 441540 KB Output is correct
4 Correct 399 ms 441488 KB Output is correct
5 Correct 409 ms 441720 KB Output is correct
6 Correct 410 ms 441756 KB Output is correct
7 Correct 413 ms 441848 KB Output is correct
8 Correct 411 ms 441748 KB Output is correct
9 Correct 412 ms 441964 KB Output is correct
10 Correct 411 ms 441724 KB Output is correct
11 Correct 412 ms 441736 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 441596 KB Output is correct
2 Correct 1562 ms 537952 KB Output is correct
3 Correct 3005 ms 638972 KB Output is correct
4 Correct 3015 ms 639596 KB Output is correct
5 Correct 3021 ms 639480 KB Output is correct
6 Correct 792 ms 478456 KB Output is correct
7 Correct 1203 ms 512880 KB Output is correct
8 Correct 1241 ms 515932 KB Output is correct
9 Correct 404 ms 441340 KB Output is correct
10 Correct 398 ms 441336 KB Output is correct
11 Correct 406 ms 441504 KB Output is correct
12 Correct 403 ms 441436 KB Output is correct
13 Correct 400 ms 441372 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 441388 KB Output is correct
2 Correct 406 ms 441592 KB Output is correct
3 Correct 401 ms 441508 KB Output is correct
4 Correct 407 ms 441644 KB Output is correct
5 Correct 401 ms 441440 KB Output is correct
6 Correct 406 ms 441468 KB Output is correct
7 Correct 403 ms 441464 KB Output is correct
8 Correct 406 ms 441464 KB Output is correct
9 Correct 405 ms 441576 KB Output is correct
10 Correct 457 ms 441592 KB Output is correct
11 Correct 404 ms 441592 KB Output is correct
12 Correct 402 ms 441592 KB Output is correct
13 Correct 410 ms 441444 KB Output is correct
14 Correct 406 ms 441464 KB Output is correct
15 Correct 413 ms 441336 KB Output is correct
16 Correct 402 ms 441336 KB Output is correct
17 Correct 407 ms 442228 KB Output is correct
18 Correct 409 ms 442368 KB Output is correct
19 Correct 449 ms 442236 KB Output is correct
20 Correct 405 ms 441956 KB Output is correct
21 Correct 404 ms 442104 KB Output is correct
22 Correct 408 ms 442052 KB Output is correct
23 Correct 431 ms 442076 KB Output is correct
24 Correct 436 ms 442040 KB Output is correct
25 Correct 471 ms 445436 KB Output is correct
26 Correct 483 ms 445284 KB Output is correct
27 Correct 429 ms 445436 KB Output is correct
28 Correct 442 ms 443788 KB Output is correct
29 Correct 439 ms 444252 KB Output is correct
30 Correct 485 ms 444536 KB Output is correct
31 Correct 458 ms 444536 KB Output is correct
32 Correct 430 ms 444436 KB Output is correct
33 Correct 641 ms 476260 KB Output is correct
34 Correct 562 ms 463148 KB Output is correct
35 Correct 578 ms 469524 KB Output is correct
36 Incorrect 508 ms 456688 KB Output isn't correct
37 Halted 0 ms 0 KB -