oj.uz

Submission #1110424

# Submission time Handle Problem Language Result Execution time Memory
1110424 2024-11-09T12:02:18 Z jerzyk Soccer Stadium (IOI23_soccer) C++17
100 / 100
 2647 ms 798068 KB 
#include <bits/stdc++.h>
#include "soccer.h"

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 = 2'007;
int XDN;
int tab[N][N], il[N][N], nxt[N][N];
vector<pair<int, int>> ed[N * N * 4];

map<pair<pair<int, int>, pair<int, int>>, int> num;
pair<pair<int, int>, pair<int, int>> pos[N * N * 4];
int dp[N * N * 4], wch[N * N * 4];

int spt[N][N][11];

void Cnt(int n)
{
    for(int i = 1; i <= n; ++i)
        nxt[i][n + 1] = n + 1;
    for(int i = 1; i <= n; ++i)
        for(int j = n; j >= 1; --j)
        {
            nxt[i][j] = nxt[i][j + 1];
            il[i][j] = il[i][j + 1] + 1;
            if(tab[i][j] == 0) nxt[i][j] = j;
            else il[i][j] = 0;
            spt[i][j][0] = il[i][j];
        }
    for(int i = n; i >= 1; --i)
        for(int j = 1; j <= n; ++j)
            for(int l = 1; i + (1<<l) - 1 <= n; ++l)
                spt[i][j][l] = min(spt[i][j][l - 1], spt[i + (1<<(l - 1))][j][l - 1]);
}

int Min(int i1, int i2, int j)
{
    int d = (i2 - i1 + 1);
    int l = 31 - __builtin_clz(d);
    return min(spt[i1][j][l], spt[i2 - (1<<l) + 1][j][l]);
}

int FU(int i, int j, int x)
{
    int p = 1, k = i, s;
    while(p < k)
    {
        s = (p + k) / 2;
        if(Min(s, i, j) >= x)
            k = s;
        else
            p = s + 1;
    }
    return p;
}

int FD(int i, int j, int x)
{
    int p = i, k = XDN, s;
    while(p < k)
    {
        s = (p + k + 1) / 2;
        if(Min(i, s, j) >= x)
            p = s;
        else
            k = s - 1;
    }
    return p;
}

int GenG(int n)
{
    int cnt = 0, v;
    queue<int> q;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            if((j != 1 && tab[i][j - 1] == 0) || tab[i][j] == 1) continue;
            int u = FU(i, j, il[i][j]), d = FD(i, j, il[i][j]);
            pair<pair<int, int>, pair<int, int>> wsp = make_pair(make_pair(u, j), make_pair(d, j + il[i][j] - 1));
            if(num.find(wsp) != num.end()) continue;
            ++cnt;
            num[wsp] = cnt; pos[cnt] = wsp;
            q.push(cnt);
            ed[0].pb(make_pair(cnt, (d - u + 1) * il[i][j]));
        }
    //cerr << "XDD\n";
    while(q.size() > 0)
    {
        v = q.front(); q.pop();
        //cerr << "Gen: " << v << " " << pos[v].st.st << " " << pos[v].st.nd << " " << pos[v].nd.st << " " << pos[v].nd.nd << "\n";
        for(int r = 0; r < 2; ++r)
        {
            //cerr << r << "\n";
            int i1 = pos[v].st.st, i2 = pos[v].nd.st;
            int cr = i1 - 1;
            int j = pos[v].st.nd;
            if(r == 1)
                cr = i2 + 1;

            j = nxt[cr][j];
            while(j <= pos[v].nd.nd && cr != 0 && cr != n + 1)
            {
                //cerr << "B " << j << "\n";
                int dis = min(il[cr][j], pos[v].nd.nd - j + 1);
                int u = FU(i1, j, dis), d = FD(i2, j, dis);
                pair<pair<int, int>, pair<int, int>> wsp = make_pair(make_pair(u, j), make_pair(d, j + dis - 1));
                //cerr << "Ne: " << wsp.st.st << " " << wsp.st.nd << " " << wsp.nd.st << " " << wsp.nd.nd << "\n";
                int ne;
                if(num.find(wsp) != num.end())
                    ne = num[wsp];
                else
                {
                    ++cnt; num[wsp] = cnt;
                    pos[cnt] = wsp;
                    ne = cnt;
                    q.push(cnt);
                }
                //cerr << ne << "\n";
                ed[v].pb(make_pair(ne, (i1 - u + d - i2) * dis));
                j += il[cr][j]; j = nxt[cr][j];
            }
            //cerr << "E\n";
        }
    }
    return cnt;
}

void Tsort(int n)
{
    int v;
    queue<int> q;
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j < (int)ed[i].size(); ++j)
            ++wch[ed[i][j].st];
    for(int i = 0; i <= n; ++i)
        if(wch[i] == 0)
            q.push(i);
    while(q.size() > 0)
    {
        v = q.front(); q.pop();
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            dp[ed[v][i].st] = max(dp[ed[v][i].st], dp[v] + ed[v][i].nd);
            --wch[ed[v][i].st];
            if(wch[ed[v][i].st] == 0)
                q.push(ed[v][i].st);
        }
    }
}

int biggest_stadium(int _N, vector<vector<int>> _F)
{
    int n = _N, m;
    XDN = n;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            tab[i][j] = _F[i - 1][j - 1];
    Cnt(n);
    m = GenG(n);
    Tsort(m);
    int ans = 0;
    for(int i = 1; i <= m; ++i)
        ans = max(ans, dp[i]);
        
    return ans;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 380488 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 380332 KB ok
2 Correct 117 ms 380488 KB ok
3 Correct 124 ms 380488 KB ok
4 Correct 127 ms 380488 KB ok
5 Correct 127 ms 380484 KB ok
6 Correct 129 ms 380548 KB ok
7 Correct 133 ms 382536 KB ok
8 Correct 155 ms 404304 KB ok
9 Correct 571 ms 634020 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 380332 KB ok
2 Correct 117 ms 380488 KB ok
3 Correct 132 ms 380488 KB ok
4 Correct 141 ms 380508 KB ok
5 Correct 138 ms 380488 KB ok
6 Correct 146 ms 380488 KB ok
7 Correct 140 ms 380488 KB ok
8 Correct 153 ms 380480 KB ok
9 Correct 153 ms 380488 KB ok
10 Correct 145 ms 380464 KB ok
11 Correct 153 ms 380488 KB ok
12 Correct 167 ms 380668 KB ok
13 Correct 168 ms 380360 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 380488 KB ok
2 Correct 116 ms 380332 KB ok
3 Correct 117 ms 380488 KB ok
4 Correct 132 ms 380488 KB ok
5 Correct 141 ms 380508 KB ok
6 Correct 138 ms 380488 KB ok
7 Correct 146 ms 380488 KB ok
8 Correct 140 ms 380488 KB ok
9 Correct 153 ms 380480 KB ok
10 Correct 153 ms 380488 KB ok
11 Correct 145 ms 380464 KB ok
12 Correct 153 ms 380488 KB ok
13 Correct 167 ms 380668 KB ok
14 Correct 168 ms 380360 KB ok
15 Correct 153 ms 380488 KB ok
16 Correct 147 ms 380428 KB ok
17 Correct 150 ms 380452 KB ok
18 Correct 151 ms 380488 KB ok
19 Correct 148 ms 380400 KB ok
20 Correct 160 ms 380488 KB ok
21 Correct 176 ms 380488 KB ok
22 Correct 164 ms 380624 KB ok
23 Correct 172 ms 380488 KB ok
24 Correct 169 ms 380528 KB ok
25 Correct 165 ms 380396 KB ok
26 Correct 173 ms 380480 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 380488 KB ok
2 Correct 116 ms 380332 KB ok
3 Correct 117 ms 380488 KB ok
4 Correct 124 ms 380488 KB ok
5 Correct 127 ms 380488 KB ok
6 Correct 132 ms 380488 KB ok
7 Correct 141 ms 380508 KB ok
8 Correct 138 ms 380488 KB ok
9 Correct 146 ms 380488 KB ok
10 Correct 140 ms 380488 KB ok
11 Correct 153 ms 380480 KB ok
12 Correct 153 ms 380488 KB ok
13 Correct 145 ms 380464 KB ok
14 Correct 153 ms 380488 KB ok
15 Correct 167 ms 380668 KB ok
16 Correct 168 ms 380360 KB ok
17 Correct 153 ms 380488 KB ok
18 Correct 147 ms 380428 KB ok
19 Correct 150 ms 380452 KB ok
20 Correct 151 ms 380488 KB ok
21 Correct 148 ms 380400 KB ok
22 Correct 160 ms 380488 KB ok
23 Correct 176 ms 380488 KB ok
24 Correct 164 ms 380624 KB ok
25 Correct 172 ms 380488 KB ok
26 Correct 169 ms 380528 KB ok
27 Correct 165 ms 380396 KB ok
28 Correct 173 ms 380480 KB ok
29 Correct 167 ms 380440 KB ok
30 Correct 170 ms 380828 KB ok
31 Correct 167 ms 381000 KB ok
32 Correct 158 ms 381000 KB ok
33 Correct 168 ms 381000 KB ok
34 Correct 165 ms 380928 KB ok
35 Correct 153 ms 381000 KB ok
36 Correct 151 ms 381000 KB ok
37 Correct 159 ms 380968 KB ok
38 Correct 161 ms 381000 KB ok
39 Correct 159 ms 381008 KB ok
40 Correct 152 ms 380820 KB ok
41 Correct 143 ms 380944 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 380488 KB ok
2 Correct 116 ms 380332 KB ok
3 Correct 117 ms 380488 KB ok
4 Correct 124 ms 380488 KB ok
5 Correct 127 ms 380488 KB ok
6 Correct 132 ms 380488 KB ok
7 Correct 141 ms 380508 KB ok
8 Correct 138 ms 380488 KB ok
9 Correct 146 ms 380488 KB ok
10 Correct 140 ms 380488 KB ok
11 Correct 153 ms 380480 KB ok
12 Correct 153 ms 380488 KB ok
13 Correct 145 ms 380464 KB ok
14 Correct 153 ms 380488 KB ok
15 Correct 167 ms 380668 KB ok
16 Correct 168 ms 380360 KB ok
17 Correct 153 ms 380488 KB ok
18 Correct 147 ms 380428 KB ok
19 Correct 150 ms 380452 KB ok
20 Correct 151 ms 380488 KB ok
21 Correct 148 ms 380400 KB ok
22 Correct 160 ms 380488 KB ok
23 Correct 176 ms 380488 KB ok
24 Correct 164 ms 380624 KB ok
25 Correct 172 ms 380488 KB ok
26 Correct 169 ms 380528 KB ok
27 Correct 165 ms 380396 KB ok
28 Correct 173 ms 380480 KB ok
29 Correct 167 ms 380440 KB ok
30 Correct 170 ms 380828 KB ok
31 Correct 167 ms 381000 KB ok
32 Correct 158 ms 381000 KB ok
33 Correct 168 ms 381000 KB ok
34 Correct 165 ms 380928 KB ok
35 Correct 153 ms 381000 KB ok
36 Correct 151 ms 381000 KB ok
37 Correct 159 ms 380968 KB ok
38 Correct 161 ms 381000 KB ok
39 Correct 159 ms 381008 KB ok
40 Correct 152 ms 380820 KB ok
41 Correct 143 ms 380944 KB ok
42 Correct 261 ms 411264 KB ok
43 Correct 275 ms 412096 KB ok
44 Correct 206 ms 406088 KB ok
45 Correct 217 ms 405320 KB ok
46 Correct 243 ms 408908 KB ok
47 Correct 196 ms 404296 KB ok
48 Correct 230 ms 405724 KB ok
49 Correct 183 ms 404296 KB ok
50 Correct 212 ms 405320 KB ok
51 Correct 209 ms 406212 KB ok
52 Correct 188 ms 404296 KB ok
53 Correct 186 ms 404296 KB ok
54 Correct 178 ms 404360 KB ok
55 Correct 202 ms 406344 KB ok
56 Correct 192 ms 404296 KB ok
57 Correct 230 ms 411720 KB ok
58 Correct 221 ms 414980 KB ok
59 Correct 222 ms 413768 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 380488 KB ok
2 Correct 116 ms 380332 KB ok
3 Correct 117 ms 380488 KB ok
4 Correct 124 ms 380488 KB ok
5 Correct 127 ms 380488 KB ok
6 Correct 127 ms 380484 KB ok
7 Correct 129 ms 380548 KB ok
8 Correct 133 ms 382536 KB ok
9 Correct 155 ms 404304 KB ok
10 Correct 571 ms 634020 KB ok
11 Correct 132 ms 380488 KB ok
12 Correct 141 ms 380508 KB ok
13 Correct 138 ms 380488 KB ok
14 Correct 146 ms 380488 KB ok
15 Correct 140 ms 380488 KB ok
16 Correct 153 ms 380480 KB ok
17 Correct 153 ms 380488 KB ok
18 Correct 145 ms 380464 KB ok
19 Correct 153 ms 380488 KB ok
20 Correct 167 ms 380668 KB ok
21 Correct 168 ms 380360 KB ok
22 Correct 153 ms 380488 KB ok
23 Correct 147 ms 380428 KB ok
24 Correct 150 ms 380452 KB ok
25 Correct 151 ms 380488 KB ok
26 Correct 148 ms 380400 KB ok
27 Correct 160 ms 380488 KB ok
28 Correct 176 ms 380488 KB ok
29 Correct 164 ms 380624 KB ok
30 Correct 172 ms 380488 KB ok
31 Correct 169 ms 380528 KB ok
32 Correct 165 ms 380396 KB ok
33 Correct 173 ms 380480 KB ok
34 Correct 167 ms 380440 KB ok
35 Correct 170 ms 380828 KB ok
36 Correct 167 ms 381000 KB ok
37 Correct 158 ms 381000 KB ok
38 Correct 168 ms 381000 KB ok
39 Correct 165 ms 380928 KB ok
40 Correct 153 ms 381000 KB ok
41 Correct 151 ms 381000 KB ok
42 Correct 159 ms 380968 KB ok
43 Correct 161 ms 381000 KB ok
44 Correct 159 ms 381008 KB ok
45 Correct 152 ms 380820 KB ok
46 Correct 143 ms 380944 KB ok
47 Correct 261 ms 411264 KB ok
48 Correct 275 ms 412096 KB ok
49 Correct 206 ms 406088 KB ok
50 Correct 217 ms 405320 KB ok
51 Correct 243 ms 408908 KB ok
52 Correct 196 ms 404296 KB ok
53 Correct 230 ms 405724 KB ok
54 Correct 183 ms 404296 KB ok
55 Correct 212 ms 405320 KB ok
56 Correct 209 ms 406212 KB ok
57 Correct 188 ms 404296 KB ok
58 Correct 186 ms 404296 KB ok
59 Correct 178 ms 404360 KB ok
60 Correct 202 ms 406344 KB ok
61 Correct 192 ms 404296 KB ok
62 Correct 230 ms 411720 KB ok
63 Correct 221 ms 414980 KB ok
64 Correct 222 ms 413768 KB ok
65 Correct 2647 ms 740992 KB ok
66 Correct 1397 ms 710648 KB ok
67 Correct 779 ms 666784 KB ok
68 Correct 674 ms 639048 KB ok
69 Correct 1287 ms 665280 KB ok
70 Correct 1849 ms 683988 KB ok
71 Correct 696 ms 634676 KB ok
72 Correct 614 ms 631880 KB ok
73 Correct 597 ms 632068 KB ok
74 Correct 611 ms 634016 KB ok
75 Correct 613 ms 632016 KB ok
76 Correct 1215 ms 648008 KB ok
77 Correct 1233 ms 657848 KB ok
78 Correct 692 ms 661176 KB ok
79 Correct 669 ms 648896 KB ok
80 Correct 683 ms 648640 KB ok
81 Correct 663 ms 647244 KB ok
82 Correct 786 ms 652984 KB ok
83 Correct 1115 ms 675512 KB ok
84 Correct 594 ms 639932 KB ok
85 Correct 565 ms 639816 KB ok
86 Correct 580 ms 640064 KB ok
87 Correct 568 ms 641608 KB ok
88 Correct 532 ms 639816 KB ok
89 Correct 588 ms 639644 KB ok
90 Correct 595 ms 639688 KB ok
91 Correct 590 ms 639844 KB ok
92 Correct 807 ms 659832 KB ok
93 Correct 834 ms 663264 KB ok
94 Correct 642 ms 647356 KB ok
95 Correct 613 ms 643772 KB ok
96 Correct 591 ms 642500 KB ok
97 Correct 592 ms 641732 KB ok
98 Correct 605 ms 642580 KB ok
99 Correct 2364 ms 770716 KB ok
100 Correct 1415 ms 758596 KB ok
101 Correct 1429 ms 748272 KB ok
102 Correct 1501 ms 759828 KB ok
103 Correct 1731 ms 777444 KB ok
104 Correct 1844 ms 785004 KB ok
105 Correct 1933 ms 790360 KB ok
106 Correct 1843 ms 798068 KB ok
107 Correct 1889 ms 794952 KB ok
108 Correct 853 ms 649840 KB ok
109 Correct 844 ms 649844 KB ok