oj.uz

Submission #474969

# Submission time Handle Problem Language Result Execution time Memory
474969 2021-09-20T11:45:20 Z Lam_lai_cuoc_doi Rectangles (IOI19_rect) C++17
100 / 100
 4133 ms 965092 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 2.5e3 + 5;

struct FenwickTree
{
    ll a[N];
    int n;
    FenwickTree()
    {
        memset(a, 0, sizeof a);
    }
    void Update(int p, ll v)
    {
        for (; p <= n; p += p & -p)
            a[p] += v;
    }
    ll Get(int p)
    {
        ll ans(0);
        for (; p > 0; p -= p & -p)
            ans += a[p];
        return ans;
    }
} f;

#define fi first
#define se second

int m, n;
vector<pair<int, int>> bycol[N][N], byrow[N][N];
vector<int> tmp[N][N];
int l[N], r[N];

void Prepare(const vector<vector<int>> &a, const int &m, const int &n, vector<pair<int, int>> by[N][N], bool rotated)
{
    for (int i = 0; i < m; ++i)
    {
        vector<int> s;
        s.reserve(n);

        for (int j = 0; j < n; ++j)
        {
            while (!s.empty() && a[i][s.back()] <= a[i][j])
                s.pop_back();
            l[j] = s.empty() ? -1 : s.back();
            s.emplace_back(j);
        }

        s.clear();

        for (int j = n - 1; ~j; --j)
        {
            while (!s.empty() && a[i][s.back()] <= a[i][j])
                s.pop_back();
            r[j] = s.empty() ? n : s.back();
            s.emplace_back(j);
        }

        for (int j = 0; j < n; ++j)
            tmp[l[j] + 1][r[j] - 1].emplace_back(i);
    }

    for (int i = 0; i < n; ++i)
        for (int j = i; j < n; ++j)
        {
            for (int u = 0, v = 1; u < (int)tmp[i][j].size(); ++u)
            {
                v = u + 1;
                while (v < (int)tmp[i][j].size() && tmp[i][j][v] - tmp[i][j][v - 1] <= 1)
                    ++v;
                //cerr << i << " " << j << " " << tmp[i][j][u] << " " << tmp[i][j][v - 1] << " is:\n";

                for (int z = tmp[i][j][u]; z <= tmp[i][j][v - 1]; ++z)
                {

                    int x1 = z, x2 = i;
                    int y1 = j, y2 = min(tmp[i][j][v - 1], m - 2);

                    if (rotated)
                    {
                        swap(x1, x2);
                        swap(y1, y2);
                    }

                    by[x1][x2].emplace_back(y1, y2);
                    //cerr << x1 << " " << x2 << " " << y1 << " " << y2 << "\n";
                }

                u = v - 1;
            }
            tmp[i][j].clear();
        }
}

bool com(const pair<int, int> &x, const pair<int, int> &y)
{
    return x.second > y.second || (x.second == y.second && x.first < y.first);
}

ll count_rectangles(vector<vector<int>> a)
{
    m = a.size();
    n = a[0].size();
    f.n = n;

    vector<vector<int>> b(n, vector<int>(m));

    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            b[j][i] = a[i][j];

    Prepare(a, m, n, byrow, 0);
    Prepare(b, n, m, bycol, 1);

    ll ans(0);
    /*for (int i = 1; i < m - 1; ++i)
        for (int j = 1; j < n - 1; ++j)
            for (int u = 0; u < (int)byrow[i][j].size(); ++u)
                cout << i << " " << j << " " << byrow[i][j][u].se << " " << byrow[i][j][u].fi << "\n";

    cout << f.Get(2) << "---\n";*/

    for (int i = 1; i < m - 1; ++i)
        for (int j = 1; j < n - 1; ++j)
        {
            sort(byrow[i][j].begin(), byrow[i][j].end(), com);
            sort(bycol[i][j].begin(), bycol[i][j].end(), com);

            int v(0);
            for (int u = 0; u < (int)bycol[i][j].size(); ++u)
            {
                //cout << i << " " << j << " " << bycol[i][j][u].se << " " << bycol[i][j][u].fi << ":\n";
                while (v < (int)byrow[i][j].size() && byrow[i][j][v].se >= bycol[i][j][u].se)
                {
                    f.Update(byrow[i][j][v].first + 1, 1);
                    //cout << byrow[i][j][v].second << " " << byrow[i][j][v].first << "\n";
                    ++v;
                }

                ans += f.Get(bycol[i][j][u].first + 1);
                //cout << ans << "\n";
            }

            while (v > 0)
            {
                --v;
                f.Update(byrow[i][j][v].first + 1, -1);
            }
        }

    return ans;
}

void Read()
{
    int m, n;
    cin >> m >> n;
    vector<vector<int>> a(m, vector<int>(n));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> a[i][j];
    cout << count_rectangles(a);
}

void Solve()
{
}

Compilation message

rect.cpp: In function 'void read(T&)':
rect.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 442372 KB Output is correct
2 Correct 235 ms 442492 KB Output is correct
3 Correct 240 ms 442476 KB Output is correct
4 Correct 230 ms 442412 KB Output is correct
5 Correct 262 ms 442384 KB Output is correct
6 Correct 239 ms 442376 KB Output is correct
7 Correct 232 ms 442464 KB Output is correct
8 Correct 234 ms 442292 KB Output is correct
9 Correct 237 ms 442436 KB Output is correct
10 Correct 237 ms 442436 KB Output is correct
11 Correct 236 ms 442436 KB Output is correct
12 Correct 231 ms 442528 KB Output is correct
13 Correct 232 ms 442308 KB Output is correct
14 Correct 229 ms 442308 KB Output is correct
15 Correct 231 ms 442340 KB Output is correct
16 Correct 233 ms 442428 KB Output is correct
17 Correct 232 ms 442272 KB Output is correct
18 Correct 237 ms 442356 KB Output is correct
19 Correct 233 ms 442412 KB Output is correct
20 Correct 233 ms 442392 KB Output is correct
21 Correct 232 ms 442352 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 442372 KB Output is correct
2 Correct 235 ms 442492 KB Output is correct
3 Correct 240 ms 442476 KB Output is correct
4 Correct 230 ms 442412 KB Output is correct
5 Correct 262 ms 442384 KB Output is correct
6 Correct 239 ms 442376 KB Output is correct
7 Correct 232 ms 442464 KB Output is correct
8 Correct 234 ms 442292 KB Output is correct
9 Correct 237 ms 442436 KB Output is correct
10 Correct 237 ms 442436 KB Output is correct
11 Correct 236 ms 442436 KB Output is correct
12 Correct 231 ms 442528 KB Output is correct
13 Correct 232 ms 442308 KB Output is correct
14 Correct 229 ms 442308 KB Output is correct
15 Correct 231 ms 442340 KB Output is correct
16 Correct 233 ms 442428 KB Output is correct
17 Correct 232 ms 442272 KB Output is correct
18 Correct 237 ms 442356 KB Output is correct
19 Correct 233 ms 442412 KB Output is correct
20 Correct 233 ms 442392 KB Output is correct
21 Correct 232 ms 442352 KB Output is correct
22 Correct 232 ms 442932 KB Output is correct
23 Correct 232 ms 442948 KB Output is correct
24 Correct 232 ms 442900 KB Output is correct
25 Correct 234 ms 442560 KB Output is correct
26 Correct 233 ms 442716 KB Output is correct
27 Correct 237 ms 442692 KB Output is correct
28 Correct 233 ms 442756 KB Output is correct
29 Correct 231 ms 442492 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 442372 KB Output is correct
2 Correct 235 ms 442492 KB Output is correct
3 Correct 240 ms 442476 KB Output is correct
4 Correct 230 ms 442412 KB Output is correct
5 Correct 262 ms 442384 KB Output is correct
6 Correct 239 ms 442376 KB Output is correct
7 Correct 232 ms 442464 KB Output is correct
8 Correct 234 ms 442292 KB Output is correct
9 Correct 237 ms 442436 KB Output is correct
10 Correct 237 ms 442436 KB Output is correct
11 Correct 236 ms 442436 KB Output is correct
12 Correct 231 ms 442528 KB Output is correct
13 Correct 232 ms 442308 KB Output is correct
14 Correct 229 ms 442308 KB Output is correct
15 Correct 231 ms 442340 KB Output is correct
16 Correct 233 ms 442428 KB Output is correct
17 Correct 232 ms 442932 KB Output is correct
18 Correct 232 ms 442948 KB Output is correct
19 Correct 232 ms 442900 KB Output is correct
20 Correct 234 ms 442560 KB Output is correct
21 Correct 233 ms 442716 KB Output is correct
22 Correct 237 ms 442692 KB Output is correct
23 Correct 233 ms 442756 KB Output is correct
24 Correct 231 ms 442492 KB Output is correct
25 Correct 232 ms 442272 KB Output is correct
26 Correct 237 ms 442356 KB Output is correct
27 Correct 233 ms 442412 KB Output is correct
28 Correct 233 ms 442392 KB Output is correct
29 Correct 232 ms 442352 KB Output is correct
30 Correct 245 ms 445788 KB Output is correct
31 Correct 242 ms 445992 KB Output is correct
32 Correct 245 ms 445916 KB Output is correct
33 Correct 246 ms 443992 KB Output is correct
34 Correct 244 ms 444824 KB Output is correct
35 Correct 250 ms 445052 KB Output is correct
36 Correct 250 ms 444892 KB Output is correct
37 Correct 247 ms 444844 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 442372 KB Output is correct
2 Correct 235 ms 442492 KB Output is correct
3 Correct 240 ms 442476 KB Output is correct
4 Correct 230 ms 442412 KB Output is correct
5 Correct 262 ms 442384 KB Output is correct
6 Correct 239 ms 442376 KB Output is correct
7 Correct 232 ms 442464 KB Output is correct
8 Correct 234 ms 442292 KB Output is correct
9 Correct 237 ms 442436 KB Output is correct
10 Correct 237 ms 442436 KB Output is correct
11 Correct 236 ms 442436 KB Output is correct
12 Correct 231 ms 442528 KB Output is correct
13 Correct 232 ms 442308 KB Output is correct
14 Correct 229 ms 442308 KB Output is correct
15 Correct 231 ms 442340 KB Output is correct
16 Correct 233 ms 442428 KB Output is correct
17 Correct 232 ms 442932 KB Output is correct
18 Correct 232 ms 442948 KB Output is correct
19 Correct 232 ms 442900 KB Output is correct
20 Correct 234 ms 442560 KB Output is correct
21 Correct 233 ms 442716 KB Output is correct
22 Correct 237 ms 442692 KB Output is correct
23 Correct 233 ms 442756 KB Output is correct
24 Correct 231 ms 442492 KB Output is correct
25 Correct 245 ms 445788 KB Output is correct
26 Correct 242 ms 445992 KB Output is correct
27 Correct 245 ms 445916 KB Output is correct
28 Correct 246 ms 443992 KB Output is correct
29 Correct 244 ms 444824 KB Output is correct
30 Correct 250 ms 445052 KB Output is correct
31 Correct 250 ms 444892 KB Output is correct
32 Correct 247 ms 444844 KB Output is correct
33 Correct 232 ms 442272 KB Output is correct
34 Correct 237 ms 442356 KB Output is correct
35 Correct 233 ms 442412 KB Output is correct
36 Correct 233 ms 442392 KB Output is correct
37 Correct 232 ms 442352 KB Output is correct
38 Correct 401 ms 481552 KB Output is correct
39 Correct 389 ms 483020 KB Output is correct
40 Correct 380 ms 482884 KB Output is correct
41 Correct 384 ms 481604 KB Output is correct
42 Correct 438 ms 484884 KB Output is correct
43 Correct 380 ms 487772 KB Output is correct
44 Correct 374 ms 485188 KB Output is correct
45 Correct 370 ms 485388 KB Output is correct
46 Correct 335 ms 459452 KB Output is correct
47 Correct 352 ms 462428 KB Output is correct
48 Correct 467 ms 472040 KB Output is correct
49 Correct 489 ms 474252 KB Output is correct
50 Correct 376 ms 458956 KB Output is correct
51 Correct 350 ms 458992 KB Output is correct
52 Correct 449 ms 471688 KB Output is correct
53 Correct 469 ms 472852 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 443208 KB Output is correct
2 Correct 270 ms 442928 KB Output is correct
3 Correct 254 ms 442692 KB Output is correct
4 Correct 233 ms 442336 KB Output is correct
5 Correct 252 ms 443272 KB Output is correct
6 Correct 255 ms 443076 KB Output is correct
7 Correct 263 ms 443076 KB Output is correct
8 Correct 257 ms 443128 KB Output is correct
9 Correct 258 ms 443060 KB Output is correct
10 Correct 249 ms 442724 KB Output is correct
11 Correct 253 ms 442948 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 442272 KB Output is correct
2 Correct 237 ms 442356 KB Output is correct
3 Correct 233 ms 442412 KB Output is correct
4 Correct 233 ms 442392 KB Output is correct
5 Correct 232 ms 442352 KB Output is correct
6 Correct 235 ms 442284 KB Output is correct
7 Correct 884 ms 551148 KB Output is correct
8 Correct 1725 ms 669832 KB Output is correct
9 Correct 1681 ms 670988 KB Output is correct
10 Correct 1675 ms 658744 KB Output is correct
11 Correct 460 ms 517636 KB Output is correct
12 Correct 678 ms 596836 KB Output is correct
13 Correct 709 ms 607576 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 442372 KB Output is correct
2 Correct 235 ms 442492 KB Output is correct
3 Correct 240 ms 442476 KB Output is correct
4 Correct 230 ms 442412 KB Output is correct
5 Correct 262 ms 442384 KB Output is correct
6 Correct 239 ms 442376 KB Output is correct
7 Correct 232 ms 442464 KB Output is correct
8 Correct 234 ms 442292 KB Output is correct
9 Correct 237 ms 442436 KB Output is correct
10 Correct 237 ms 442436 KB Output is correct
11 Correct 236 ms 442436 KB Output is correct
12 Correct 231 ms 442528 KB Output is correct
13 Correct 232 ms 442308 KB Output is correct
14 Correct 229 ms 442308 KB Output is correct
15 Correct 231 ms 442340 KB Output is correct
16 Correct 233 ms 442428 KB Output is correct
17 Correct 232 ms 442932 KB Output is correct
18 Correct 232 ms 442948 KB Output is correct
19 Correct 232 ms 442900 KB Output is correct
20 Correct 234 ms 442560 KB Output is correct
21 Correct 233 ms 442716 KB Output is correct
22 Correct 237 ms 442692 KB Output is correct
23 Correct 233 ms 442756 KB Output is correct
24 Correct 231 ms 442492 KB Output is correct
25 Correct 245 ms 445788 KB Output is correct
26 Correct 242 ms 445992 KB Output is correct
27 Correct 245 ms 445916 KB Output is correct
28 Correct 246 ms 443992 KB Output is correct
29 Correct 244 ms 444824 KB Output is correct
30 Correct 250 ms 445052 KB Output is correct
31 Correct 250 ms 444892 KB Output is correct
32 Correct 247 ms 444844 KB Output is correct
33 Correct 401 ms 481552 KB Output is correct
34 Correct 389 ms 483020 KB Output is correct
35 Correct 380 ms 482884 KB Output is correct
36 Correct 384 ms 481604 KB Output is correct
37 Correct 438 ms 484884 KB Output is correct
38 Correct 380 ms 487772 KB Output is correct
39 Correct 374 ms 485188 KB Output is correct
40 Correct 370 ms 485388 KB Output is correct
41 Correct 335 ms 459452 KB Output is correct
42 Correct 352 ms 462428 KB Output is correct
43 Correct 467 ms 472040 KB Output is correct
44 Correct 489 ms 474252 KB Output is correct
45 Correct 376 ms 458956 KB Output is correct
46 Correct 350 ms 458992 KB Output is correct
47 Correct 449 ms 471688 KB Output is correct
48 Correct 469 ms 472852 KB Output is correct
49 Correct 254 ms 443208 KB Output is correct
50 Correct 270 ms 442928 KB Output is correct
51 Correct 254 ms 442692 KB Output is correct
52 Correct 233 ms 442336 KB Output is correct
53 Correct 252 ms 443272 KB Output is correct
54 Correct 255 ms 443076 KB Output is correct
55 Correct 263 ms 443076 KB Output is correct
56 Correct 257 ms 443128 KB Output is correct
57 Correct 258 ms 443060 KB Output is correct
58 Correct 249 ms 442724 KB Output is correct
59 Correct 253 ms 442948 KB Output is correct
60 Correct 235 ms 442284 KB Output is correct
61 Correct 884 ms 551148 KB Output is correct
62 Correct 1725 ms 669832 KB Output is correct
63 Correct 1681 ms 670988 KB Output is correct
64 Correct 1675 ms 658744 KB Output is correct
65 Correct 460 ms 517636 KB Output is correct
66 Correct 678 ms 596836 KB Output is correct
67 Correct 709 ms 607576 KB Output is correct
68 Correct 232 ms 442272 KB Output is correct
69 Correct 237 ms 442356 KB Output is correct
70 Correct 233 ms 442412 KB Output is correct
71 Correct 233 ms 442392 KB Output is correct
72 Correct 232 ms 442352 KB Output is correct
73 Correct 2847 ms 920712 KB Output is correct
74 Correct 2741 ms 916324 KB Output is correct
75 Correct 3088 ms 916364 KB Output is correct
76 Correct 2621 ms 897568 KB Output is correct
77 Correct 3207 ms 965092 KB Output is correct
78 Correct 2496 ms 672708 KB Output is correct
79 Correct 2666 ms 676632 KB Output is correct
80 Correct 4098 ms 812720 KB Output is correct
81 Correct 2582 ms 673484 KB Output is correct
82 Correct 3453 ms 744112 KB Output is correct
83 Correct 4133 ms 813940 KB Output is correct
84 Correct 2249 ms 652848 KB Output is correct
85 Correct 3723 ms 799132 KB Output is correct
86 Correct 3569 ms 788696 KB Output is correct
87 Correct 1922 ms 775812 KB Output is correct
88 Correct 3191 ms 964384 KB Output is correct
89 Correct 3240 ms 960916 KB Output is correct
90 Correct 3308 ms 958364 KB Output is correct