oj.uz

Submission #1065884

# Submission time Handle Problem Language Result Execution time Memory
1065884 2024-08-19T12:34:12 Z GrindMachine Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 1017208 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);
}

int n;
map<array<int,3>,int> 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.count(ar)) 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 1 ms 604 KB ok
2 Correct 0 ms 604 KB ok
3 Correct 1 ms 604 KB ok
4 Correct 0 ms 604 KB ok
5 Correct 1 ms 2656 KB ok
6 Correct 1 ms 604 KB ok
7 Correct 4 ms 5016 KB ok
8 Correct 71 ms 50256 KB ok
9 Correct 1172 ms 823424 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB ok
2 Correct 0 ms 604 KB ok
3 Correct 1 ms 2648 KB ok
4 Correct 1 ms 600 KB ok
5 Correct 1 ms 600 KB ok
6 Correct 0 ms 672 KB ok
7 Correct 1 ms 2652 KB ok
8 Correct 0 ms 604 KB ok
9 Correct 0 ms 604 KB ok
10 Correct 0 ms 604 KB ok
11 Correct 1 ms 604 KB ok
12 Correct 0 ms 604 KB ok
13 Correct 0 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 1 ms 604 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 1 ms 2648 KB ok
5 Correct 1 ms 600 KB ok
6 Correct 1 ms 600 KB ok
7 Correct 0 ms 672 KB ok
8 Correct 1 ms 2652 KB ok
9 Correct 0 ms 604 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 0 ms 604 KB ok
14 Correct 0 ms 604 KB ok
15 Correct 1 ms 600 KB ok
16 Correct 1 ms 604 KB ok
17 Correct 0 ms 604 KB ok
18 Correct 1 ms 2652 KB ok
19 Correct 1 ms 604 KB ok
20 Correct 1 ms 600 KB ok
21 Correct 0 ms 604 KB ok
22 Correct 0 ms 604 KB ok
23 Correct 1 ms 604 KB ok
24 Correct 1 ms 604 KB ok
25 Correct 1 ms 604 KB ok
26 Correct 1 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 1 ms 604 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 604 KB ok
6 Correct 1 ms 2648 KB ok
7 Correct 1 ms 600 KB ok
8 Correct 1 ms 600 KB ok
9 Correct 0 ms 672 KB ok
10 Correct 1 ms 2652 KB ok
11 Correct 0 ms 604 KB ok
12 Correct 0 ms 604 KB ok
13 Correct 0 ms 604 KB ok
14 Correct 1 ms 604 KB ok
15 Correct 0 ms 604 KB ok
16 Correct 0 ms 604 KB ok
17 Correct 1 ms 600 KB ok
18 Correct 1 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 1 ms 2652 KB ok
21 Correct 1 ms 604 KB ok
22 Correct 1 ms 600 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 1 ms 604 KB ok
28 Correct 1 ms 604 KB ok
29 Correct 1 ms 856 KB ok
30 Correct 2 ms 1116 KB ok
31 Correct 1 ms 1176 KB ok
32 Correct 1 ms 1112 KB ok
33 Correct 1 ms 1116 KB ok
34 Correct 2 ms 2904 KB ok
35 Correct 1 ms 1368 KB ok
36 Correct 1 ms 1116 KB ok
37 Correct 1 ms 2908 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 1 ms 604 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 604 KB ok
6 Correct 1 ms 2648 KB ok
7 Correct 1 ms 600 KB ok
8 Correct 1 ms 600 KB ok
9 Correct 0 ms 672 KB ok
10 Correct 1 ms 2652 KB ok
11 Correct 0 ms 604 KB ok
12 Correct 0 ms 604 KB ok
13 Correct 0 ms 604 KB ok
14 Correct 1 ms 604 KB ok
15 Correct 0 ms 604 KB ok
16 Correct 0 ms 604 KB ok
17 Correct 1 ms 600 KB ok
18 Correct 1 ms 604 KB ok
19 Correct 0 ms 604 KB ok
20 Correct 1 ms 2652 KB ok
21 Correct 1 ms 604 KB ok
22 Correct 1 ms 600 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 1 ms 604 KB ok
28 Correct 1 ms 604 KB ok
29 Correct 1 ms 856 KB ok
30 Correct 2 ms 1116 KB ok
31 Correct 1 ms 1176 KB ok
32 Correct 1 ms 1112 KB ok
33 Correct 1 ms 1116 KB ok
34 Correct 2 ms 2904 KB ok
35 Correct 1 ms 1368 KB ok
36 Correct 1 ms 1116 KB ok
37 Correct 1 ms 2908 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 223 ms 62168 KB ok
43 Correct 185 ms 60500 KB ok
44 Correct 340 ms 64340 KB ok
45 Correct 290 ms 62888 KB ok
46 Correct 258 ms 64084 KB ok
47 Correct 77 ms 51080 KB ok
48 Correct 99 ms 53328 KB ok
49 Correct 113 ms 53128 KB ok
50 Correct 161 ms 58544 KB ok
51 Correct 215 ms 57940 KB ok
52 Correct 82 ms 52564 KB ok
53 Correct 61 ms 51280 KB ok
54 Correct 64 ms 51648 KB ok
55 Correct 81 ms 52696 KB ok
56 Correct 58 ms 50628 KB ok
57 Correct 168 ms 58652 KB ok
58 Correct 174 ms 59220 KB ok
59 Correct 219 ms 59732 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB ok
2 Correct 1 ms 604 KB ok
3 Correct 0 ms 604 KB ok
4 Correct 1 ms 604 KB ok
5 Correct 0 ms 604 KB ok
6 Correct 1 ms 2656 KB ok
7 Correct 1 ms 604 KB ok
8 Correct 4 ms 5016 KB ok
9 Correct 71 ms 50256 KB ok
10 Correct 1172 ms 823424 KB ok
11 Correct 1 ms 2648 KB ok
12 Correct 1 ms 600 KB ok
13 Correct 1 ms 600 KB ok
14 Correct 0 ms 672 KB ok
15 Correct 1 ms 2652 KB ok
16 Correct 0 ms 604 KB ok
17 Correct 0 ms 604 KB ok
18 Correct 0 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 1 ms 600 KB ok
23 Correct 1 ms 604 KB ok
24 Correct 0 ms 604 KB ok
25 Correct 1 ms 2652 KB ok
26 Correct 1 ms 604 KB ok
27 Correct 1 ms 600 KB ok
28 Correct 0 ms 604 KB ok
29 Correct 0 ms 604 KB ok
30 Correct 1 ms 604 KB ok
31 Correct 1 ms 604 KB ok
32 Correct 1 ms 604 KB ok
33 Correct 1 ms 604 KB ok
34 Correct 1 ms 856 KB ok
35 Correct 2 ms 1116 KB ok
36 Correct 1 ms 1176 KB ok
37 Correct 1 ms 1112 KB ok
38 Correct 1 ms 1116 KB ok
39 Correct 2 ms 2904 KB ok
40 Correct 1 ms 1368 KB ok
41 Correct 1 ms 1116 KB ok
42 Correct 1 ms 2908 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 223 ms 62168 KB ok
48 Correct 185 ms 60500 KB ok
49 Correct 340 ms 64340 KB ok
50 Correct 290 ms 62888 KB ok
51 Correct 258 ms 64084 KB ok
52 Correct 77 ms 51080 KB ok
53 Correct 99 ms 53328 KB ok
54 Correct 113 ms 53128 KB ok
55 Correct 161 ms 58544 KB ok
56 Correct 215 ms 57940 KB ok
57 Correct 82 ms 52564 KB ok
58 Correct 61 ms 51280 KB ok
59 Correct 64 ms 51648 KB ok
60 Correct 81 ms 52696 KB ok
61 Correct 58 ms 50628 KB ok
62 Correct 168 ms 58652 KB ok
63 Correct 174 ms 59220 KB ok
64 Correct 219 ms 59732 KB ok
65 Execution timed out 4535 ms 1017208 KB Time limit exceeded
66 Halted 0 ms 0 KB -