oj.uz

Submission #1072631

# Submission time Handle Problem Language Result Execution time Memory
1072631 2024-08-24T00:32:41 Z HorizonWest Soccer Stadium (IOI23_soccer) C++17
77.5 / 100
 3574 ms 941956 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 = 2e6;

#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 0 ms 348 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB ok
2 Correct 0 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 KB ok
5 Correct 1 ms 348 KB ok
6 Correct 0 ms 348 KB ok
7 Correct 3 ms 2396 KB ok
8 Correct 72 ms 45916 KB ok
9 Correct 1463 ms 850548 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 348 KB ok
6 Correct 0 ms 348 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 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 1 ms 348 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 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 348 KB ok
7 Correct 0 ms 348 KB ok
8 Correct 1 ms 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 0 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 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 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 348 KB ok
23 Correct 0 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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 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 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 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 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 1 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 0 ms 344 KB ok
30 Correct 1 ms 604 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 344 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 1 ms 424 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 1 ms 344 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 0 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 0 ms 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 KB ok
4 Correct 0 ms 348 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 348 KB ok
9 Correct 0 ms 348 KB ok
10 Correct 1 ms 348 KB ok
11 Correct 0 ms 348 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 0 ms 348 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 0 ms 348 KB ok
23 Correct 0 ms 348 KB ok
24 Correct 1 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 0 ms 344 KB ok
30 Correct 1 ms 604 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 1 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 1 ms 344 KB ok
35 Correct 1 ms 348 KB ok
36 Correct 1 ms 424 KB ok
37 Correct 0 ms 348 KB ok
38 Correct 1 ms 344 KB ok
39 Correct 1 ms 348 KB ok
40 Correct 0 ms 348 KB ok
41 Correct 1 ms 604 KB ok
42 Correct 241 ms 58556 KB ok
43 Correct 208 ms 56776 KB ok
44 Correct 266 ms 64964 KB ok
45 Correct 272 ms 64892 KB ok
46 Correct 247 ms 64704 KB ok
47 Correct 78 ms 47048 KB ok
48 Correct 90 ms 48836 KB ok
49 Correct 94 ms 47340 KB ok
50 Correct 116 ms 57280 KB ok
51 Correct 136 ms 54892 KB ok
52 Correct 68 ms 44552 KB ok
53 Correct 57 ms 43284 KB ok
54 Correct 73 ms 44372 KB ok
55 Correct 93 ms 45776 KB ok
56 Correct 66 ms 44652 KB ok
57 Correct 131 ms 55236 KB ok
58 Correct 122 ms 55008 KB ok
59 Correct 123 ms 55108 KB ok

Subtask #6
7.5 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok
2 Correct 1 ms 348 KB ok
3 Correct 0 ms 348 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 0 ms 348 KB ok
8 Correct 3 ms 2396 KB ok
9 Correct 72 ms 45916 KB ok
10 Correct 1463 ms 850548 KB ok
11 Correct 0 ms 344 KB ok
12 Correct 0 ms 348 KB ok
13 Correct 0 ms 348 KB ok
14 Correct 0 ms 348 KB ok
15 Correct 1 ms 348 KB ok
16 Correct 0 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 1 ms 348 KB ok
22 Correct 0 ms 348 KB ok
23 Correct 0 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 348 KB ok
30 Correct 0 ms 348 KB ok
31 Correct 0 ms 348 KB ok
32 Correct 0 ms 348 KB ok
33 Correct 0 ms 348 KB ok
34 Correct 0 ms 344 KB ok
35 Correct 1 ms 604 KB ok
36 Correct 1 ms 604 KB ok
37 Correct 1 ms 348 KB ok
38 Correct 0 ms 348 KB ok
39 Correct 1 ms 344 KB ok
40 Correct 1 ms 348 KB ok
41 Correct 1 ms 424 KB ok
42 Correct 0 ms 348 KB ok
43 Correct 1 ms 344 KB ok
44 Correct 1 ms 348 KB ok
45 Correct 0 ms 348 KB ok
46 Correct 1 ms 604 KB ok
47 Correct 241 ms 58556 KB ok
48 Correct 208 ms 56776 KB ok
49 Correct 266 ms 64964 KB ok
50 Correct 272 ms 64892 KB ok
51 Correct 247 ms 64704 KB ok
52 Correct 78 ms 47048 KB ok
53 Correct 90 ms 48836 KB ok
54 Correct 94 ms 47340 KB ok
55 Correct 116 ms 57280 KB ok
56 Correct 136 ms 54892 KB ok
57 Correct 68 ms 44552 KB ok
58 Correct 57 ms 43284 KB ok
59 Correct 73 ms 44372 KB ok
60 Correct 93 ms 45776 KB ok
61 Correct 66 ms 44652 KB ok
62 Correct 131 ms 55236 KB ok
63 Correct 122 ms 55008 KB ok
64 Correct 123 ms 55108 KB ok
65 Correct 3325 ms 933100 KB ok
66 Correct 2182 ms 870688 KB ok
67 Correct 1282 ms 828052 KB ok
68 Partially correct 3574 ms 932856 KB partial
69 Partially correct 3438 ms 935988 KB partial
70 Correct 3431 ms 940144 KB ok
71 Correct 3151 ms 934292 KB ok
72 Correct 1807 ms 860292 KB ok
73 Correct 2610 ms 886584 KB ok
74 Correct 2685 ms 910652 KB ok
75 Correct 2440 ms 886716 KB ok
76 Correct 1803 ms 924704 KB ok
77 Partially correct 1926 ms 920052 KB partial
78 Correct 2660 ms 932156 KB ok
79 Correct 1198 ms 817100 KB ok
80 Correct 1121 ms 817560 KB ok
81 Correct 1367 ms 831192 KB ok
82 Correct 2216 ms 863248 KB ok
83 Correct 1840 ms 855000 KB ok
84 Correct 1106 ms 820204 KB ok
85 Correct 1040 ms 811856 KB ok
86 Correct 1200 ms 830556 KB ok
87 Correct 1331 ms 832512 KB ok
88 Correct 1345 ms 836408 KB ok
89 Correct 1812 ms 854700 KB ok
90 Correct 1455 ms 854844 KB ok
91 Correct 1602 ms 855472 KB ok
92 Correct 1242 ms 822176 KB ok
93 Correct 1491 ms 828856 KB ok
94 Correct 1156 ms 814012 KB ok
95 Correct 1084 ms 812464 KB ok
96 Correct 1022 ms 811460 KB ok
97 Correct 1043 ms 811560 KB ok
98 Correct 1044 ms 807572 KB ok
99 Correct 2692 ms 925268 KB ok
100 Correct 2519 ms 937696 KB ok
101 Correct 2586 ms 936144 KB ok
102 Correct 2405 ms 936764 KB ok
103 Correct 2393 ms 936448 KB ok
104 Correct 2327 ms 936860 KB ok
105 Correct 2201 ms 934496 KB ok
106 Correct 2479 ms 934820 KB ok
107 Correct 2436 ms 941956 KB ok
108 Correct 3350 ms 925372 KB ok
109 Correct 3368 ms 927388 KB ok