oj.uz

Submission #1065893

# Submission time Handle Problem Language Result Execution time Memory
1065893 2024-08-19T12:39:39 Z GrindMachine Soccer Stadium (IOI23_soccer) C++17
100 / 100
 3202 ms 1070192 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://blog.brucemerry.org.za/2023/11/ioi-2023-day-1.html

*/

const int MOD = 1e9 + 7;
const int N = 2e3 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "soccer.h"

template<typename T>
struct sparse_table {
    /*============================*/

    T merge(T a, T b) {
        return max(a,b);
    }

    /*============================*/

    vector<vector<T>> table;
    vector<int> bin_log;
    int LOG = 0;

    sparse_table() {

    }

    sparse_table(vector<T> &a, int n) {
        while ((1 << LOG) <= n) LOG++;

        table = vector<vector<T>>(n, vector<T>(LOG));
        bin_log = vector<int>(n + 1);

        rep(i, n) table[i][0] = a[i];

        rep1(j, LOG - 1) {
            rep(i, n) {
                int jump = 1 << (j - 1);
                if (i + jump >= n) {
                    break;
                }

                table[i][j] = merge(table[i][j - 1], table[i + jump][j - 1]);
            }
        }

        bin_log[1] = 0;
        for (int i = 2; i <= n; ++i) {
            bin_log[i] = bin_log[i / 2] + 1;
        }
    }

    T query(int l, int r) {
        int len = r - l + 1;
        int k = bin_log[len];

        T val1 = table[l][k];
        T val2 = table[r - (1 << k) + 1][k];

        return merge(val1, val2);
    }
};

int mnl[N][N], mxr[N][N], mnu[N][N];
sparse_table<int> st1[N], st2[N];

int extendl(int i, int j, int c){
    // int mx = -inf1;
    // for(int r = i; r <= j; ++r){
    //     amax(mx,mnl[r][c]);
    // }
    // return mx;

    return st1[c].query(i,j);
}

int extendr(int i, int j, int c){
    // int mn = inf1;
    // for(int r = i; r <= j; ++r){
    //     amin(mn,mxr[r][c]);
    // }
    // return mn;

    return -st2[c].query(i,j);
}

const vector<ll> mul = {34828472,4838748374,894587283};
typedef unsigned long long ull;

struct hsh{
    const ull RANDOM = mt19937_64(chrono::steady_clock::now().time_since_epoch().count())();
    ull operator()(const array<int,3> &a) const {
        ull val = a[0]*mul[0]+a[1]*mul[1]+a[2]*mul[2];
        val ^= RANDOM;
        return val;
    }
};

int n;
gp_hash_table<array<int,3>,int,hsh> mp;

int go(int i, int j, int l){
    if(i > j) return 0;

    l = extendl(i,j,l);
    int r = extendr(i,j,l);
    array<int,3> ar = {i,j,l};
    if(mp.find(ar) != mp.end()) return mp[ar];

    int len = r-l+1;

    // shrink j
    int ans = len+go(i,j-1,l);

    // shrink i till l expansion possible
    if(l-1){
        int p = mnu[j][l-1];
        amax(ans,len*(p-i)+go(p,j,l));
    }

    // shrink i till r expansion possible
    if(r+1 <= n){
        int p = mnu[j][r+1];
        amax(ans,len*(p-i)+go(p,j,l));
    }

    return mp[ar] = ans;
}

int biggest_stadium(int n_, std::vector<std::vector<int>> A)
{
    n = n_;

    int a[n+5][n+5];
    memset(a,0,sizeof a);
    rep1(i,n) rep1(j,n) a[i][j] = A[i-1][j-1];

    rep1(i,n) mnl[i][0] = 1;
    rep1(i,n){
        rep1(j,n){
            if(!a[i][j]){
                mnl[i][j] = mnl[i][j-1];
            }
            else{
                mnl[i][j] = j+1;
            }
        }
    }

    rep1(i,n) mxr[i][n+1] = n;
    rev(j,n,1){
        rep1(i,n){
            if(!a[i][j]){
                mxr[i][j] = mxr[i][j+1];
            }
            else{
                mxr[i][j] = j-1;
            }
        }
    }

    rep1(j,n){
        vector<int> b(n+5);
        rep1(i,n) b[i] = mnl[i][j];
        st1[j] = sparse_table<int>(b,n+1);
    }

    rep1(j,n){
        vector<int> b(n+5);
        rep1(i,n) b[i] = -mxr[i][j];
        st2[j] = sparse_table<int>(b,n+1);
    }

    rep1(j,n) mnu[0][j] = 1;
    rep1(i,n){
        rep1(j,n){
            if(!a[i][j]){
                mnu[i][j] = mnu[i-1][j];
            }
            else{
                mnu[i][j] = i+1;
            }
        }
    }

    int ans = 0;
    vector<int> lx(n+5);

    rep1(i,n){
        rep1(j,n) lx[j] = 1;

        stack<int> stk;
        rev(j,n,1){
            while(!stk.empty() and mnu[i][j] > mnu[i][stk.top()]){
                int k = stk.top();
                lx[k] = j+1;
                stk.pop();
            }
            stk.push(j);
        }

        rep1(j,n){
            amax(ans,go(mnu[i][j],i,lx[j]));
        }
    }

    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB ok
2 Correct 0 ms 604 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 0 ms 604 KB ok
5 Correct 0 ms 604 KB ok
6 Correct 0 ms 604 KB ok
7 Correct 3 ms 5212 KB ok
8 Correct 59 ms 50772 KB ok
9 Correct 1031 ms 823392 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB ok
2 Correct 0 ms 604 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 0 ms 604 KB ok
5 Correct 0 ms 604 KB ok
6 Correct 1 ms 2652 KB ok
7 Correct 0 ms 604 KB ok
8 Correct 1 ms 600 KB ok
9 Correct 0 ms 600 KB ok
10 Correct 0 ms 604 KB ok
11 Correct 0 ms 604 KB ok
12 Correct 1 ms 604 KB ok
13 Correct 1 ms 600 KB ok
14 Correct 1 ms 600 KB ok
15 Correct 0 ms 604 KB ok
16 Correct 1 ms 604 KB ok
17 Correct 1 ms 860 KB ok
18 Correct 0 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 1 ms 604 KB ok
21 Correct 1 ms 604 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 0 ms 604 KB ok
26 Correct 0 ms 2652 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 0 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 1 ms 1116 KB ok
31 Correct 1 ms 1116 KB ok
32 Correct 1 ms 1116 KB ok
33 Correct 1 ms 1116 KB ok
34 Correct 1 ms 2908 KB ok
35 Correct 1 ms 1116 KB ok
36 Correct 1 ms 1116 KB ok
37 Correct 1 ms 1116 KB ok
38 Correct 1 ms 1116 KB ok
39 Correct 1 ms 1116 KB ok
40 Correct 1 ms 1116 KB ok
41 Correct 1 ms 1116 KB ok
42 Correct 127 ms 66236 KB ok
43 Correct 113 ms 66188 KB ok
44 Correct 137 ms 66512 KB ok
45 Correct 136 ms 66236 KB ok
46 Correct 127 ms 66228 KB ok
47 Correct 61 ms 51248 KB ok
48 Correct 83 ms 54684 KB ok
49 Correct 68 ms 54728 KB ok
50 Correct 90 ms 58560 KB ok
51 Correct 93 ms 58816 KB ok
52 Correct 60 ms 52812 KB ok
53 Correct 57 ms 51852 KB ok
54 Correct 60 ms 51720 KB ok
55 Correct 64 ms 52812 KB ok
56 Correct 59 ms 50772 KB ok
57 Correct 80 ms 58568 KB ok
58 Correct 83 ms 66240 KB ok
59 Correct 86 ms 66236 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB ok
2 Correct 0 ms 604 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 0 ms 604 KB ok
5 Correct 0 ms 604 KB ok
6 Correct 0 ms 604 KB ok
7 Correct 0 ms 604 KB ok
8 Correct 3 ms 5212 KB ok
9 Correct 59 ms 50772 KB ok
10 Correct 1031 ms 823392 KB ok
11 Correct 1 ms 2652 KB ok
12 Correct 0 ms 604 KB ok
13 Correct 1 ms 600 KB ok
14 Correct 0 ms 600 KB ok
15 Correct 0 ms 604 KB ok
16 Correct 0 ms 604 KB ok
17 Correct 1 ms 604 KB ok
18 Correct 1 ms 600 KB ok
19 Correct 1 ms 600 KB ok
20 Correct 0 ms 604 KB ok
21 Correct 1 ms 604 KB ok
22 Correct 1 ms 860 KB ok
23 Correct 0 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 1 ms 604 KB ok
26 Correct 1 ms 604 KB ok
27 Correct 0 ms 604 KB ok
28 Correct 0 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 0 ms 604 KB ok
31 Correct 0 ms 2652 KB ok
32 Correct 0 ms 604 KB ok
33 Correct 0 ms 604 KB ok
34 Correct 0 ms 604 KB ok
35 Correct 1 ms 1116 KB ok
36 Correct 1 ms 1116 KB ok
37 Correct 1 ms 1116 KB ok
38 Correct 1 ms 1116 KB ok
39 Correct 1 ms 2908 KB ok
40 Correct 1 ms 1116 KB ok
41 Correct 1 ms 1116 KB ok
42 Correct 1 ms 1116 KB ok
43 Correct 1 ms 1116 KB ok
44 Correct 1 ms 1116 KB ok
45 Correct 1 ms 1116 KB ok
46 Correct 1 ms 1116 KB ok
47 Correct 127 ms 66236 KB ok
48 Correct 113 ms 66188 KB ok
49 Correct 137 ms 66512 KB ok
50 Correct 136 ms 66236 KB ok
51 Correct 127 ms 66228 KB ok
52 Correct 61 ms 51248 KB ok
53 Correct 83 ms 54684 KB ok
54 Correct 68 ms 54728 KB ok
55 Correct 90 ms 58560 KB ok
56 Correct 93 ms 58816 KB ok
57 Correct 60 ms 52812 KB ok
58 Correct 57 ms 51852 KB ok
59 Correct 60 ms 51720 KB ok
60 Correct 64 ms 52812 KB ok
61 Correct 59 ms 50772 KB ok
62 Correct 80 ms 58568 KB ok
63 Correct 83 ms 66240 KB ok
64 Correct 86 ms 66236 KB ok
65 Correct 2437 ms 1068972 KB ok
66 Correct 1414 ms 885020 KB ok
67 Correct 1134 ms 854200 KB ok
68 Correct 2724 ms 1069680 KB ok
69 Correct 3202 ms 1069672 KB ok
70 Correct 2770 ms 1069672 KB ok
71 Correct 2560 ms 1069672 KB ok
72 Correct 1032 ms 831164 KB ok
73 Correct 1358 ms 885024 KB ok
74 Correct 1294 ms 884988 KB ok
75 Correct 1352 ms 885128 KB ok
76 Correct 2061 ms 946532 KB ok
77 Correct 1998 ms 946532 KB ok
78 Correct 1665 ms 946676 KB ok
79 Correct 966 ms 838836 KB ok
80 Correct 976 ms 838840 KB ok
81 Correct 943 ms 838848 KB ok
82 Correct 1141 ms 884996 KB ok
83 Correct 1259 ms 884876 KB ok
84 Correct 929 ms 838768 KB ok
85 Correct 954 ms 831004 KB ok
86 Correct 987 ms 839088 KB ok
87 Correct 983 ms 838692 KB ok
88 Correct 963 ms 823376 KB ok
89 Correct 1026 ms 824536 KB ok
90 Correct 983 ms 827328 KB ok
91 Correct 1045 ms 831184 KB ok
92 Correct 1049 ms 838816 KB ok
93 Correct 1104 ms 854276 KB ok
94 Correct 959 ms 831024 KB ok
95 Correct 945 ms 827168 KB ok
96 Correct 972 ms 825416 KB ok
97 Correct 946 ms 825420 KB ok
98 Correct 1157 ms 824432 KB ok
99 Correct 2086 ms 1069660 KB ok
100 Correct 1378 ms 946732 KB ok
101 Correct 2282 ms 946548 KB ok
102 Correct 2394 ms 946688 KB ok
103 Correct 1516 ms 1070192 KB ok
104 Correct 2462 ms 1069672 KB ok
105 Correct 2803 ms 1069728 KB ok
106 Correct 1632 ms 1069932 KB ok
107 Correct 1529 ms 1069924 KB ok
108 Correct 1409 ms 946528 KB ok
109 Correct 1557 ms 946532 KB ok