oj.uz

Submission #1072622

# Submission time Handle Problem Language Result Execution time Memory
1072622 2024-08-24T00:24:16 Z HorizonWest Soccer Stadium (IOI23_soccer) C++17
77.5 / 100
 4345 ms 1013116 KB 
#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
#include <cassert>
using namespace std;

const int Max = 3001, Inf = 1e9, TLE = 3e6;

#define ll unsigned long long

int lg[Max], cnt; 

struct SPTMIN
{
    vector <vector <int>> spt; 

    int query(int i, int j){
        int x = lg[j-i+1];
        return min(spt[i][x], spt[j - (1LL << x) + 1][x]);
    }

    SPTMIN(vector <int> v)
    {
        int n = v.size();
        spt.assign(n + 1, vector <int> (lg[n] + 1, Inf));

        for(int j = 0; j < lg[n]+1; j++)
        {
            for(int i = 0; i < n; i++){
                if(j == 0){
                    spt[i][j] = v[i];
                    continue;
                }
                spt[i][j] = spt[i][j-1];
                if(i + (1LL << (j-1)) < n) spt[i][j] = min(spt[i][j-1], spt[i + (1LL << (j-1))][j-1]);
            }
        }
    }
};

struct SPTMAX
{
    vector <vector <int>> spt; 

    int query(int i, int j){
        int x = lg[j-i+1];
        return max(spt[i][x], spt[j - (1LL << x) + 1][x]);
    }

    SPTMAX(vector <int> v)
    {
        int n = v.size();
        spt.assign(n + 1, vector <int> (lg[n] + 1, 0));

        for(int j = 0; j < lg[n]+1; j++)
        {
            for(int i = 0; i < n; i++){
                if(j == 0){
                    spt[i][j] = v[i];
                    continue;
                }
                spt[i][j] = spt[i][j-1];
                if(i + (1LL << (j-1)) < n) spt[i][j] = max(spt[i][j-1], spt[i + (1LL << (j-1))][j-1]);
            }
        }
    }
};

int rnd(){
  	return abs(int(rand() ^ (rand() << 3LL) ^ (rand() << 6LL)));
}

int biggest_stadium(int n, std::vector<std::vector<int>> f)
{
    vector <vector<int>> A(n, vector <int> (n, 0)),
        B(n, vector <int> (n, 0)),
        C(n, vector <int> (n, 0)),
        D(n, vector <int> (n, 0)), 
        T(n, vector <int> (n, 0)); 

    vector <SPTMIN> sp1;
    vector <SPTMAX> sp2;

    cnt = 0;

    for(int i = 1; i <= n; i++){
        lg[i] = log2(i);
    }

    for(int i = 0; i < n; i++)
    {
        int last = -1; 
        for(int j = 0; j < n; j++){
            if(f[i][j] == 1) last = j; 
            A[i][j] = last;
        }   

        last = n;
        for(int j = n-1; j >= 0; j--){
            T[i][j] = last;
            if(f[i][j] == 1) {      
                if(j != n-1 && last == j+1){
                    T[i][j] = T[i][j+1];
                }else T[i][j] = j;
                last = j;
            } 
            B[i][j] = last;
        }     
    }

    for(int i = 0; i < n; i++)
    {
        int last = -1; 
        for(int j = 0; j < n; j++){
            if(f[j][i] == 1) last = j; 
            C[j][i] = last+1;
        }   

        last = n;
        for(int j = n-1; j >= 0; j--){
            if(f[j][i] == 1) last = j; 
            D[j][i] = last-1;
        }     
    }

    for(int i = 0; i < n; i++)
    {
        sp1.push_back(SPTMIN(D[i]));
        sp2.push_back(SPTMAX(C[i]));
    }
    
    //return 0;

    //vector <vector<vector<int>>> dp1(n + 1, vector <vector<int>> 
    //    (n + 1, vector <int> (n + 1, -1)));

    //vector <vector<vector<int>>> dp2(n + 1, vector <vector<int>> 
    //    (n + 1, vector <int> (n + 1, -1)));

    unordered_map <ll, int> dp; 

    auto F = [&](auto F, int i, int j, int a, int b, int c, int d) -> int 
    {   cnt++;

        long long x = ((ll) b) + (((ll) c) << 11LL) + (((ll) d) << 22LL) + (((ll) j) << 33LL) 
                               + (((ll) i) << 44LL) + (((ll) a) << 55LL);
        
        if(dp[x] != 0) return dp[x];
        dp[x] = (b - a + 1); 
        if(i != j) dp[x] += (d - c + 1);

        int mx = 0;

        if(i != 0)
        {
            for(int k = a; k <= b; k++) if(f[i-1][k] == 0)
            {
                int l1 = max(A[i-1][k]+1, a), r1 = min(B[i-1][k]-1, b);
                int l2 = max(c, l1), r2 =  min(d, r1);

                int ni = sp2[i].query(l1, r1), d = abs(ni - i) - 1, t = (r1 - l1 + 1);

                mx = max(mx, F(F, ni, j, l1, r1, l2, r2) - (r2 - l2 + 1) + d * t);

                k = r1;
            } else k = T[i-1][k];
        }

        if(j != n-1)
        {
            for(int k = c; k <= d; k++) if(f[j+1][k] == 0)
            {
                int l2 = max(A[j+1][k]+1, c), r2 = min(B[j+1][k]-1, d);
                int l1 = max(a, l2), r1 =  min(b, r2);

                int nj = sp1[j].query(l2, r2), d = abs(nj - j) - 1, t = (r2 - l2 + 1);

                mx = max(mx, F(F, i, nj, l1, r1, l2, r2) - (r1 - l1 + 1) + d * t);

                k = r2;
            } else k = T[j+1][k];
        }

        return dp[x] = (dp[x] + mx);
    };      
    
    int ans = 0; 
  	
  	srand(time(NULL));
  	vector <pair<int, pair<int, int>>> fx; 
  
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(f[i][j] == 1) continue; 
            int l = A[i][j]+1, r = B[i][j]-1;

            int ni = sp2[i].query(j, j);
            int nj = sp1[i].query(j, j);

            int d = r-l+1, h = (nj - ni + 1);
            fx.push_back({ max(d, h), { i, j }});
        }
    }
  	
    sort(fx.begin(), fx.end());

  	while (fx.size() > 0)
    {
        pair<int, int> u = fx.back().second; fx.pop_back();
        int i = u.first, j = u.second; 
        
        if(f[i][j] == 1) continue; 
        
        int l = A[i][j]+1, r = B[i][j]-1;

        ans = max(ans, F(F, i, i, l, r, l, r));

        if(n > 500 && cnt > TLE) {
            break;
        }
    }

    int mod = fx.size(); cnt = 0;
    

    for(int i = 0; i < (int) fx.size(); i++){
        int x = rnd() % mod;
        swap(fx[i], fx[x]);
    }

    while (fx.size() > 0)
    {
        pair<int, int> u = fx.back().second; fx.pop_back();
        int i = u.first, j = u.second; 
        
        if(f[i][j] == 1) continue; 
        
        int l = A[i][j]+1, r = B[i][j]-1;

        ans = max(ans, F(F, i, i, l, r, l, r));

        if(n > 500 && cnt > TLE) {
            break;
        }
    }

    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 428 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 3 ms 2396 KB ok
8 Correct 68 ms 47268 KB ok
9 Correct 1213 ms 853508 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 344 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 0 ms 440 KB ok
6 Correct 1 ms 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 344 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 1 ms 440 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 344 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 440 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 0 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 344 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 1 ms 440 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 344 KB ok
16 Correct 1 ms 348 KB ok
17 Correct 0 ms 348 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 1 ms 436 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 344 KB ok
26 Correct 0 ms 348 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 428 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 440 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 1 ms 440 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 1 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 1 ms 436 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 344 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 1 ms 616 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 1 ms 344 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 1 ms 600 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 1 ms 348 KB ok
38 Correct 0 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 1 ms 348 KB ok
41 Correct 1 ms 604 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 428 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 344 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 0 ms 440 KB ok
9 Correct 1 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 344 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 1 ms 440 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 1 ms 348 KB ok
19 Correct 0 ms 348 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 1 ms 436 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 344 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 1 ms 348 KB ok
30 Correct 1 ms 616 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 1 ms 344 KB ok
33 Correct 1 ms 348 KB ok
34 Correct 0 ms 348 KB ok
35 Correct 1 ms 600 KB ok
36 Correct 0 ms 348 KB ok
37 Correct 1 ms 348 KB ok
38 Correct 0 ms 348 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 1 ms 348 KB ok
41 Correct 1 ms 604 KB ok
42 Correct 227 ms 59068 KB ok
43 Correct 184 ms 57284 KB ok
44 Correct 283 ms 65212 KB ok
45 Correct 261 ms 65460 KB ok
46 Correct 252 ms 65216 KB ok
47 Correct 81 ms 46604 KB ok
48 Correct 93 ms 49348 KB ok
49 Correct 104 ms 48884 KB ok
50 Correct 118 ms 58048 KB ok
51 Correct 128 ms 55228 KB ok
52 Correct 67 ms 45076 KB ok
53 Correct 69 ms 43808 KB ok
54 Correct 63 ms 44880 KB ok
55 Correct 80 ms 46288 KB ok
56 Correct 68 ms 45000 KB ok
57 Correct 126 ms 55508 KB ok
58 Correct 121 ms 55576 KB ok
59 Correct 129 ms 55488 KB ok

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 428 KB ok
5 Correct 0 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 1 ms 348 KB ok
8 Correct 3 ms 2396 KB ok
9 Correct 68 ms 47268 KB ok
10 Correct 1213 ms 853508 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 440 KB ok
14 Correct 1 ms 348 KB ok
15 Correct 0 ms 348 KB ok
16 Correct 0 ms 348 KB ok
17 Correct 0 ms 344 KB ok
18 Correct 0 ms 348 KB ok
19 Correct 1 ms 440 KB ok
20 Correct 0 ms 348 KB ok
21 Correct 0 ms 348 KB ok
22 Correct 0 ms 344 KB ok
23 Correct 1 ms 348 KB ok
24 Correct 0 ms 348 KB ok
25 Correct 0 ms 348 KB ok
26 Correct 0 ms 348 KB ok
27 Correct 0 ms 348 KB ok
28 Correct 0 ms 348 KB ok
29 Correct 1 ms 436 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 0 ms 344 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 348 KB ok
35 Correct 1 ms 616 KB ok
36 Correct 1 ms 604 KB ok
37 Correct 1 ms 344 KB ok
38 Correct 1 ms 348 KB ok
39 Correct 0 ms 348 KB ok
40 Correct 1 ms 600 KB ok
41 Correct 0 ms 348 KB ok
42 Correct 1 ms 348 KB ok
43 Correct 0 ms 348 KB ok
44 Correct 1 ms 348 KB ok
45 Correct 1 ms 348 KB ok
46 Correct 1 ms 604 KB ok
47 Correct 227 ms 59068 KB ok
48 Correct 184 ms 57284 KB ok
49 Correct 283 ms 65212 KB ok
50 Correct 261 ms 65460 KB ok
51 Correct 252 ms 65216 KB ok
52 Correct 81 ms 46604 KB ok
53 Correct 93 ms 49348 KB ok
54 Correct 104 ms 48884 KB ok
55 Correct 118 ms 58048 KB ok
56 Correct 128 ms 55228 KB ok
57 Correct 67 ms 45076 KB ok
58 Correct 69 ms 43808 KB ok
59 Correct 63 ms 44880 KB ok
60 Correct 80 ms 46288 KB ok
61 Correct 68 ms 45000 KB ok
62 Correct 126 ms 55508 KB ok
63 Correct 121 ms 55576 KB ok
64 Correct 129 ms 55488 KB ok
65 Correct 4345 ms 1007072 KB ok
66 Correct 1802 ms 870316 KB ok
67 Correct 1134 ms 828092 KB ok
68 Partially correct 3929 ms 964068 KB partial
69 Correct 4240 ms 1011736 KB ok
70 Correct 4302 ms 1012024 KB ok
71 Correct 3824 ms 958396 KB ok
72 Correct 1644 ms 859320 KB ok
73 Correct 2323 ms 883624 KB ok
74 Correct 2673 ms 907720 KB ok
75 Correct 2291 ms 883572 KB ok
76 Correct 1798 ms 953320 KB ok
77 Correct 2037 ms 952212 KB ok
78 Correct 2766 ms 949876 KB ok
79 Correct 1088 ms 816644 KB ok
80 Correct 1118 ms 816828 KB ok
81 Correct 1242 ms 830160 KB ok
82 Correct 1798 ms 862900 KB ok
83 Correct 1714 ms 853940 KB ok
84 Correct 1061 ms 819764 KB ok
85 Correct 956 ms 811456 KB ok
86 Correct 1166 ms 830772 KB ok
87 Correct 1261 ms 830644 KB ok
88 Correct 1261 ms 836732 KB ok
89 Correct 1600 ms 854244 KB ok
90 Correct 1368 ms 855348 KB ok
91 Correct 1354 ms 854424 KB ok
92 Correct 1262 ms 821768 KB ok
93 Correct 1327 ms 828700 KB ok
94 Correct 1025 ms 813264 KB ok
95 Correct 1020 ms 811976 KB ok
96 Correct 991 ms 811260 KB ok
97 Correct 941 ms 810460 KB ok
98 Correct 930 ms 808132 KB ok
99 Correct 3167 ms 947984 KB ok
100 Correct 2879 ms 1013116 KB ok
101 Correct 2803 ms 966420 KB ok
102 Correct 3088 ms 1009020 KB ok
103 Correct 2516 ms 961788 KB ok
104 Correct 2425 ms 960908 KB ok
105 Correct 2416 ms 959428 KB ok
106 Correct 2601 ms 957460 KB ok
107 Correct 2900 ms 1010576 KB ok
108 Correct 3428 ms 942188 KB ok
109 Correct 3727 ms 949812 KB ok