oj.uz

Submission #1064940

# Submission time Handle Problem Language Result Execution time Memory
1064940 2024-08-18T19:47:25 Z jerzyk Rectangles (IOI19_rect) C++17
100 / 100
 2728 ms 719848 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 2500 + 7;
const int NN = 1<<12;
int drz[2 * NN];

int tab[N][N];
vector<int> intr[N][N];
vector<pair<int, int>> que[N][N];
bool czy[N];
long long answer = 0;

void Add(int v, int x)
{
    v += NN;
    while(v > 0)
        {drz[v] += x; v /= 2;}
}

int Query(int a, int b)
{
    a += NN - 1; b += NN + 1;
    int ans = 0;
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0) ans += drz[a + 1];
        if(b % 2 == 1) ans += drz[b - 1];
        a /= 2; b /= 2;
    }
    return ans;
}

void CntR(int n, int m)
{
    for(int i = 1; i <= n; ++i)
    {
        vector<pair<int, int>> kol;
        for(int j = m; j >= 1; --j)
        {
            while((int)kol.size() > 0 && kol.back().st <= tab[i][j])
                kol.pop_back();
            int xd = tab[i][j];
            //cerr << "R: " << i << " " << j << "\n";
            for(int k = kol.size() - 1; k >= 0 && tab[i][j - 1] > xd; --k)
            {
                intr[i][j].pb(kol[k].nd - 1);
                //cerr << kol[k].nd - 1 << " ";
                xd = max(xd, kol[k].st);
            }
            //cout << "\n";
            kol.pb(make_pair(tab[i][j], j));
        }
    }
    for(int j = 1; j <= m; ++j)
    {
        vector<pair<int, int>> akt;
        for(int i = j; i <= m; ++i)
            akt.pb(make_pair(i, 1));
        for(int i = 1; i <= n; ++i)
        {
            vector<pair<int, int>> nxt;
            int k = 0;
            //cerr << "DP: " << i << " " << j << "\n";
            for(int l = 0; l < (int)intr[i][j].size(); ++l)
            {
                while(k < (int)akt.size() && akt[k].st < intr[i][j][l])
                    ++k;
                if(k < (int)akt.size() && akt[k].st == intr[i][j][l])
                {
                    nxt.pb(akt[k]);
                    ++k;
                }else
                    nxt.pb(make_pair(intr[i][j][l], i));

                que[i][intr[i][j][l]].pb(make_pair(j, i - nxt.back().nd + 1));
                //cerr << nxt.back().st << " " << nxt.back().nd << "\n";
            }
            akt = nxt;
            intr[i][j].clear();
        }
    }
}

void CntL(int n, int m)
{
    for(int j = 1; j <= m; ++j)
    {
        vector<pair<int, int>> kol;
        for(int i = 1; i <= n; ++i)
        {
            while((int)kol.size() > 0 && kol.back().st <= tab[i][j])
                kol.pop_back();
            int xd = tab[i][j];
            //cerr << "U: " << i << " " << j << "\n";
            for(int k = kol.size() - 1; k >= 0 && tab[i + 1][j] > xd; --k)
            {
                intr[i][j].pb(kol[k].nd + 1);
                //cerr << kol[k].nd + 1 << "\n";
                xd = max(xd, kol[k].st);
            }
            sort(intr[i][j].begin(), intr[i][j].end());
            kol.pb(make_pair(tab[i][j], i));
        }
    }
    for(int i = 1; i <= n; ++i)
    {
        vector<pair<int, int>> akt;
        for(int j = i; j <= n; ++j)
            akt.pb(make_pair(j, 1));
        for(int j = 1; j <= m; ++j)
        {
            vector<pair<int, int>> nxt;
            int k = 0;
            //cerr << "DP: " << i << " " <<  j << "\n";
            for(int l = 0; l < (int)intr[i][j].size(); ++l)
            {
                while(k < (int)akt.size() && akt[k].st < intr[i][j][l])
                    ++k;
                if(k < (int)akt.size() && akt[k].st == intr[i][j][l])
                {
                    nxt.pb(make_pair(akt[k].nd, akt[k].st));
                    ++k;
                }else
                    nxt.pb(make_pair(j, intr[i][j][l]));
                //cerr << nxt.back().nd << " " << nxt.back().st << "\n";
            }
            akt = nxt;
            sort(akt.begin(), akt.end());
            int lim = akt.size();
            k = -1;
            //cout << "QUE: " << i << " " << j << "\n";
            for(int l = 0; l < (int)que[i][j].size(); ++l)
            {
                while(k < lim - 1 && akt[k + 1].st <= que[i][j][l].st)
                {
                    ++k;
                    Add(i - akt[k].nd + 1, 1);
                }
                answer += (ll)Query(1, que[i][j][l].nd);
                //for(int r = 0; r < lim; ++r)
                    //if(akt[r].st <= que[i][j][l].st && i - akt[r].nd + 1 <= que[i][j][l].nd)
                         //++answer;
            }
            for(k = k; k >= 0; --k)
                Add(i - akt[k].nd + 1, -1);

            for(int l = 0; l < (int)akt.size(); ++l)
                swap(akt[l].st, akt[l].nd);
            sort(akt.begin(), akt.end());
            intr[i][j].clear();
        }
    }
}

long long count_rectangles(vector<vector<int>> xd)
{
    int n = xd.size(), m = xd[0].size();
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            tab[i][j] = xd[i - 1][j - 1];
    CntR(n, m);
    CntL(n, m);
    return answer;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 295488 KB Output is correct
2 Correct 105 ms 295784 KB Output is correct
3 Correct 117 ms 295596 KB Output is correct
4 Correct 106 ms 295760 KB Output is correct
5 Correct 111 ms 295512 KB Output is correct
6 Correct 108 ms 295764 KB Output is correct
7 Correct 115 ms 295764 KB Output is correct
8 Correct 106 ms 295576 KB Output is correct
9 Correct 108 ms 295764 KB Output is correct
10 Correct 105 ms 295708 KB Output is correct
11 Correct 133 ms 295764 KB Output is correct
12 Correct 106 ms 295604 KB Output is correct
13 Correct 114 ms 295508 KB Output is correct
14 Correct 106 ms 295504 KB Output is correct
15 Correct 116 ms 295404 KB Output is correct
16 Correct 115 ms 295604 KB Output is correct
17 Correct 108 ms 295504 KB Output is correct
18 Correct 108 ms 295520 KB Output is correct
19 Correct 123 ms 295724 KB Output is correct
20 Correct 109 ms 295620 KB Output is correct
21 Correct 119 ms 295504 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 295488 KB Output is correct
2 Correct 105 ms 295784 KB Output is correct
3 Correct 117 ms 295596 KB Output is correct
4 Correct 106 ms 295760 KB Output is correct
5 Correct 111 ms 295512 KB Output is correct
6 Correct 108 ms 295764 KB Output is correct
7 Correct 115 ms 295764 KB Output is correct
8 Correct 106 ms 295576 KB Output is correct
9 Correct 108 ms 295764 KB Output is correct
10 Correct 105 ms 295708 KB Output is correct
11 Correct 133 ms 295764 KB Output is correct
12 Correct 106 ms 295604 KB Output is correct
13 Correct 114 ms 295508 KB Output is correct
14 Correct 106 ms 295504 KB Output is correct
15 Correct 116 ms 295404 KB Output is correct
16 Correct 115 ms 295604 KB Output is correct
17 Correct 108 ms 295504 KB Output is correct
18 Correct 108 ms 295520 KB Output is correct
19 Correct 123 ms 295724 KB Output is correct
20 Correct 109 ms 295620 KB Output is correct
21 Correct 119 ms 295504 KB Output is correct
22 Correct 107 ms 296308 KB Output is correct
23 Correct 111 ms 296276 KB Output is correct
24 Correct 109 ms 296276 KB Output is correct
25 Correct 114 ms 296080 KB Output is correct
26 Correct 113 ms 296076 KB Output is correct
27 Correct 115 ms 296268 KB Output is correct
28 Correct 108 ms 296272 KB Output is correct
29 Correct 112 ms 296020 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 295488 KB Output is correct
2 Correct 105 ms 295784 KB Output is correct
3 Correct 117 ms 295596 KB Output is correct
4 Correct 106 ms 295760 KB Output is correct
5 Correct 111 ms 295512 KB Output is correct
6 Correct 108 ms 295764 KB Output is correct
7 Correct 115 ms 295764 KB Output is correct
8 Correct 106 ms 295576 KB Output is correct
9 Correct 108 ms 295764 KB Output is correct
10 Correct 105 ms 295708 KB Output is correct
11 Correct 133 ms 295764 KB Output is correct
12 Correct 106 ms 295604 KB Output is correct
13 Correct 114 ms 295508 KB Output is correct
14 Correct 106 ms 295504 KB Output is correct
15 Correct 116 ms 295404 KB Output is correct
16 Correct 115 ms 295604 KB Output is correct
17 Correct 107 ms 296308 KB Output is correct
18 Correct 111 ms 296276 KB Output is correct
19 Correct 109 ms 296276 KB Output is correct
20 Correct 114 ms 296080 KB Output is correct
21 Correct 113 ms 296076 KB Output is correct
22 Correct 115 ms 296268 KB Output is correct
23 Correct 108 ms 296272 KB Output is correct
24 Correct 112 ms 296020 KB Output is correct
25 Correct 108 ms 295504 KB Output is correct
26 Correct 108 ms 295520 KB Output is correct
27 Correct 123 ms 295724 KB Output is correct
28 Correct 109 ms 295620 KB Output is correct
29 Correct 119 ms 295504 KB Output is correct
30 Correct 117 ms 298836 KB Output is correct
31 Correct 130 ms 298892 KB Output is correct
32 Correct 112 ms 298832 KB Output is correct
33 Correct 118 ms 297784 KB Output is correct
34 Correct 126 ms 298580 KB Output is correct
35 Correct 118 ms 298576 KB Output is correct
36 Correct 125 ms 298576 KB Output is correct
37 Correct 122 ms 298580 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 295488 KB Output is correct
2 Correct 105 ms 295784 KB Output is correct
3 Correct 117 ms 295596 KB Output is correct
4 Correct 106 ms 295760 KB Output is correct
5 Correct 111 ms 295512 KB Output is correct
6 Correct 108 ms 295764 KB Output is correct
7 Correct 115 ms 295764 KB Output is correct
8 Correct 106 ms 295576 KB Output is correct
9 Correct 108 ms 295764 KB Output is correct
10 Correct 105 ms 295708 KB Output is correct
11 Correct 133 ms 295764 KB Output is correct
12 Correct 106 ms 295604 KB Output is correct
13 Correct 114 ms 295508 KB Output is correct
14 Correct 106 ms 295504 KB Output is correct
15 Correct 116 ms 295404 KB Output is correct
16 Correct 115 ms 295604 KB Output is correct
17 Correct 107 ms 296308 KB Output is correct
18 Correct 111 ms 296276 KB Output is correct
19 Correct 109 ms 296276 KB Output is correct
20 Correct 114 ms 296080 KB Output is correct
21 Correct 113 ms 296076 KB Output is correct
22 Correct 115 ms 296268 KB Output is correct
23 Correct 108 ms 296272 KB Output is correct
24 Correct 112 ms 296020 KB Output is correct
25 Correct 117 ms 298836 KB Output is correct
26 Correct 130 ms 298892 KB Output is correct
27 Correct 112 ms 298832 KB Output is correct
28 Correct 118 ms 297784 KB Output is correct
29 Correct 126 ms 298580 KB Output is correct
30 Correct 118 ms 298576 KB Output is correct
31 Correct 125 ms 298576 KB Output is correct
32 Correct 122 ms 298580 KB Output is correct
33 Correct 108 ms 295504 KB Output is correct
34 Correct 108 ms 295520 KB Output is correct
35 Correct 123 ms 295724 KB Output is correct
36 Correct 109 ms 295620 KB Output is correct
37 Correct 119 ms 295504 KB Output is correct
38 Correct 177 ms 317844 KB Output is correct
39 Correct 195 ms 314980 KB Output is correct
40 Correct 183 ms 324056 KB Output is correct
41 Correct 172 ms 322640 KB Output is correct
42 Correct 200 ms 329716 KB Output is correct
43 Correct 207 ms 329592 KB Output is correct
44 Correct 198 ms 329940 KB Output is correct
45 Correct 206 ms 328076 KB Output is correct
46 Correct 184 ms 314504 KB Output is correct
47 Correct 202 ms 317232 KB Output is correct
48 Correct 285 ms 325048 KB Output is correct
49 Correct 297 ms 325972 KB Output is correct
50 Correct 197 ms 312336 KB Output is correct
51 Correct 199 ms 310984 KB Output is correct
52 Correct 280 ms 323772 KB Output is correct
53 Correct 264 ms 324432 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 296060 KB Output is correct
2 Correct 123 ms 296028 KB Output is correct
3 Correct 129 ms 295764 KB Output is correct
4 Correct 128 ms 295624 KB Output is correct
5 Correct 134 ms 296012 KB Output is correct
6 Correct 138 ms 295820 KB Output is correct
7 Correct 128 ms 295980 KB Output is correct
8 Correct 135 ms 295760 KB Output is correct
9 Correct 128 ms 295764 KB Output is correct
10 Correct 128 ms 295592 KB Output is correct
11 Correct 151 ms 295880 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 295504 KB Output is correct
2 Correct 108 ms 295520 KB Output is correct
3 Correct 123 ms 295724 KB Output is correct
4 Correct 109 ms 295620 KB Output is correct
5 Correct 119 ms 295504 KB Output is correct
6 Correct 115 ms 295528 KB Output is correct
7 Correct 593 ms 389272 KB Output is correct
8 Correct 1185 ms 496980 KB Output is correct
9 Correct 1214 ms 497752 KB Output is correct
10 Correct 1244 ms 497664 KB Output is correct
11 Correct 258 ms 335188 KB Output is correct
12 Correct 458 ms 372136 KB Output is correct
13 Correct 518 ms 375636 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 295488 KB Output is correct
2 Correct 105 ms 295784 KB Output is correct
3 Correct 117 ms 295596 KB Output is correct
4 Correct 106 ms 295760 KB Output is correct
5 Correct 111 ms 295512 KB Output is correct
6 Correct 108 ms 295764 KB Output is correct
7 Correct 115 ms 295764 KB Output is correct
8 Correct 106 ms 295576 KB Output is correct
9 Correct 108 ms 295764 KB Output is correct
10 Correct 105 ms 295708 KB Output is correct
11 Correct 133 ms 295764 KB Output is correct
12 Correct 106 ms 295604 KB Output is correct
13 Correct 114 ms 295508 KB Output is correct
14 Correct 106 ms 295504 KB Output is correct
15 Correct 116 ms 295404 KB Output is correct
16 Correct 115 ms 295604 KB Output is correct
17 Correct 107 ms 296308 KB Output is correct
18 Correct 111 ms 296276 KB Output is correct
19 Correct 109 ms 296276 KB Output is correct
20 Correct 114 ms 296080 KB Output is correct
21 Correct 113 ms 296076 KB Output is correct
22 Correct 115 ms 296268 KB Output is correct
23 Correct 108 ms 296272 KB Output is correct
24 Correct 112 ms 296020 KB Output is correct
25 Correct 117 ms 298836 KB Output is correct
26 Correct 130 ms 298892 KB Output is correct
27 Correct 112 ms 298832 KB Output is correct
28 Correct 118 ms 297784 KB Output is correct
29 Correct 126 ms 298580 KB Output is correct
30 Correct 118 ms 298576 KB Output is correct
31 Correct 125 ms 298576 KB Output is correct
32 Correct 122 ms 298580 KB Output is correct
33 Correct 177 ms 317844 KB Output is correct
34 Correct 195 ms 314980 KB Output is correct
35 Correct 183 ms 324056 KB Output is correct
36 Correct 172 ms 322640 KB Output is correct
37 Correct 200 ms 329716 KB Output is correct
38 Correct 207 ms 329592 KB Output is correct
39 Correct 198 ms 329940 KB Output is correct
40 Correct 206 ms 328076 KB Output is correct
41 Correct 184 ms 314504 KB Output is correct
42 Correct 202 ms 317232 KB Output is correct
43 Correct 285 ms 325048 KB Output is correct
44 Correct 297 ms 325972 KB Output is correct
45 Correct 197 ms 312336 KB Output is correct
46 Correct 199 ms 310984 KB Output is correct
47 Correct 280 ms 323772 KB Output is correct
48 Correct 264 ms 324432 KB Output is correct
49 Correct 133 ms 296060 KB Output is correct
50 Correct 123 ms 296028 KB Output is correct
51 Correct 129 ms 295764 KB Output is correct
52 Correct 128 ms 295624 KB Output is correct
53 Correct 134 ms 296012 KB Output is correct
54 Correct 138 ms 295820 KB Output is correct
55 Correct 128 ms 295980 KB Output is correct
56 Correct 135 ms 295760 KB Output is correct
57 Correct 128 ms 295764 KB Output is correct
58 Correct 128 ms 295592 KB Output is correct
59 Correct 151 ms 295880 KB Output is correct
60 Correct 115 ms 295528 KB Output is correct
61 Correct 593 ms 389272 KB Output is correct
62 Correct 1185 ms 496980 KB Output is correct
63 Correct 1214 ms 497752 KB Output is correct
64 Correct 1244 ms 497664 KB Output is correct
65 Correct 258 ms 335188 KB Output is correct
66 Correct 458 ms 372136 KB Output is correct
67 Correct 518 ms 375636 KB Output is correct
68 Correct 108 ms 295504 KB Output is correct
69 Correct 108 ms 295520 KB Output is correct
70 Correct 123 ms 295724 KB Output is correct
71 Correct 109 ms 295620 KB Output is correct
72 Correct 119 ms 295504 KB Output is correct
73 Correct 1249 ms 547460 KB Output is correct
74 Correct 984 ms 520484 KB Output is correct
75 Correct 1352 ms 633008 KB Output is correct
76 Correct 1255 ms 618204 KB Output is correct
77 Correct 1595 ms 710648 KB Output is correct
78 Correct 1525 ms 501808 KB Output is correct
79 Correct 1608 ms 532072 KB Output is correct
80 Correct 2491 ms 642420 KB Output is correct
81 Correct 1627 ms 519192 KB Output is correct
82 Correct 2177 ms 598396 KB Output is correct
83 Correct 2728 ms 667844 KB Output is correct
84 Correct 1573 ms 500896 KB Output is correct
85 Correct 2594 ms 651052 KB Output is correct
86 Correct 2566 ms 640188 KB Output is correct
87 Correct 1018 ms 558148 KB Output is correct
88 Correct 1611 ms 719560 KB Output is correct
89 Correct 1521 ms 719732 KB Output is correct
90 Correct 1605 ms 719848 KB Output is correct