oj.uz

Submission #840778

# Submission time Handle Problem Language Result Execution time Memory
840778 2023-08-31T16:57:52 Z PurpleCrayon Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 1102724 KB 
#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
 
#define ar array
#define sz(v) int(v.size())
typedef long long ll;
const int INF = 1e9+10;
const int M = 2e3+10;
 
struct Sparse {
    vector<vector<int>> sparse;
    Sparse() {}
    Sparse(vector<int>& v) {
        int n = v.size();
        sparse.push_back(v);
        for (int i = 1; (1 << i) <= n; i++) {
            sparse.push_back(vector<int>(n - (1 << i) + 1));
            for (int j = 0; j + (1 << i) <= n; j++) {
                sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j + (1 << (i-1))]);
            }
        }
    }
 
    int qry(int l, int r) {
        assert(l <= r);
        int b = 31 - __builtin_clz(r - l + 1);
        // cerr << "> " << l << ' ' << r << ''
        return min(sparse[b][l], sparse[b][r - (1 << b) + 1]);
    }
} ones[M], twos[M];
 
int get_cost(int i, int l, int r) {
    return max(0, ones[i].qry(l, r) + twos[i].qry(l, r) - 1);
}

#include<bits/extc++.h>

struct splitmix64_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}

	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

template <typename K, typename V, typename Hash = splitmix64_hash>
using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>;

template <typename K, typename Hash = splitmix64_hash>
using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>;

 
int cnt_l[M][M], cnt_r[M][M];
int store_up[M][M], store_down[M][M];
vector<pair<int, int>> impl[M][M], impr[M][M], has[M][M];
int dp[2 * M * M];
 
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
    for (int j = 0; j < N; j++) {
        int one = 0;
        for (int i = 0; i < N; i++) {
            one = F[i][j] ? 0 : one + 1;
            store_up[i][j] = one;
        }

        int two = 0;
        for (int i = N-1; i >= 0; i--) {
            two = F[i][j] ? 0 : two + 1;
            store_down[i][j] = two;
        }
    }

    for (int i = 0; i < N; i++) {
        vector<int> up(N), down(N);
        for (int j = 0; j < N; j++) {
            up[j] = store_up[i][j], down[j] = store_down[i][j];
            // while (i - up[j] >= 0 && !F[i - up[j]][j]) up[j]++;
            // while (i + down[j] < N && !F[i + down[j]][j]) down[j]++;
        }
 
        ones[i] = Sparse(up), twos[i] = Sparse(down);
    }
 
    int id = 0;
    auto add_imp = [&](int i, int l, int r) {
        has[l][r].emplace_back(i, id++);
        cnt_l[i][l]++, cnt_r[i][r]++;
    };
 
    for (int i = 0; i < N; i++) {
        vector<int> blocks{-1};
        for (int j = 0; j < N; j++) if (F[i][j])
            blocks.push_back(j);
        
        blocks.push_back(N);
 
        for (int j = 1; j < sz(blocks); j++) if (blocks[j] > blocks[j-1] + 1) {
            int l = blocks[j-1]+1, r = blocks[j]-1;
            for (int k = l; k <= r; k++) {
                add_imp(i, k, r);
                if (k != r) add_imp(i, l, k);
            }
        }
    }
 
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)
        impl[i][j].reserve(cnt_l[i][j]), impr[i][j].reserve(cnt_r[i][j]);

    for (int l = 0; l < N; l++) {
        for (int r = 0; r < N; r++) {
            for (auto [i, id] : has[l][r]) {
                impl[i][l].emplace_back(r, id);
                impr[i][r].emplace_back(l, id);
            }
        }
    }
 
    auto upd = [&](int ni, int l, int r, int x, int cur_cost) {
        if (ni < 0 || ni >= N) return;
        int nl = upper_bound(impr[ni][r].begin(), impr[ni][r].end(), make_pair(l, M)) - impr[ni][r].begin();
        if (nl < sz(impr[ni][r])) {
            int id = impr[ni][r][nl].second;
            nl = impr[ni][r][nl].first;
            dp[id] = max(dp[id], x + (get_cost(ni, nl, r) - cur_cost) * (r - nl + 1));
        }
 
        int nr = lower_bound(impl[ni][l].begin(), impl[ni][l].end(), make_pair(r, -1)) - impl[ni][l].begin() - 1;
        if (nr >= 0) {
            int id = impl[ni][l][nr].second;
            nr = impl[ni][l][nr].first;
            dp[id] = max(dp[id], x + (get_cost(ni, l, nr) - cur_cost) * (nr - l + 1));
        }
    };
 
    for (int l = 0; l < N; l++) {
        for (int r = N-1; r >= 0; r--) {
            for (auto [i, id] : has[l][r]) {
                int cur_cost = get_cost(i, l, r);
                int store = dp[id] = max(dp[id], cur_cost * (r - l + 1));
                // cerr << l << ' ' << r << ' ' << i << ' ' << dp[{i, l, r}] << endl;
 
                int top = i - ones[i].qry(l, r);
                int bot = i + twos[i].qry(l, r);
                upd(i, l, r, store, cur_cost);
                upd(top, l, r, store, cur_cost);
                upd(bot, l, r, store, cur_cost);
            }
        }
    }
 
    int ans = 0;
    for (auto& x : dp) ans = max(ans, x);
    // for (auto& [_, v] : dp) ans = max(ans, v);
    cerr << (double) clock() / CLOCKS_PER_SEC << endl;
    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 285084 KB ok
2 Correct 121 ms 285052 KB ok
3 Correct 120 ms 285244 KB ok
4 Correct 120 ms 285184 KB ok
5 Correct 120 ms 285092 KB ok
6 Correct 122 ms 285060 KB ok
7 Correct 141 ms 288476 KB ok
8 Correct 294 ms 340648 KB ok
9 Correct 3653 ms 1102724 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 285084 KB ok
2 Correct 121 ms 285052 KB ok
3 Correct 121 ms 285024 KB ok
4 Correct 121 ms 285040 KB ok
5 Correct 121 ms 285116 KB ok
6 Correct 128 ms 285128 KB ok
7 Correct 124 ms 285132 KB ok
8 Correct 126 ms 285036 KB ok
9 Correct 122 ms 285024 KB ok
10 Correct 123 ms 285136 KB ok
11 Correct 123 ms 285076 KB ok
12 Correct 126 ms 285088 KB ok
13 Correct 123 ms 285044 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 285068 KB ok
2 Correct 122 ms 285084 KB ok
3 Correct 121 ms 285052 KB ok
4 Correct 121 ms 285024 KB ok
5 Correct 121 ms 285040 KB ok
6 Correct 121 ms 285116 KB ok
7 Correct 128 ms 285128 KB ok
8 Correct 124 ms 285132 KB ok
9 Correct 126 ms 285036 KB ok
10 Correct 122 ms 285024 KB ok
11 Correct 123 ms 285136 KB ok
12 Correct 123 ms 285076 KB ok
13 Correct 126 ms 285088 KB ok
14 Correct 123 ms 285044 KB ok
15 Correct 122 ms 285132 KB ok
16 Correct 122 ms 285092 KB ok
17 Correct 125 ms 285132 KB ok
18 Correct 119 ms 285092 KB ok
19 Correct 121 ms 285132 KB ok
20 Correct 125 ms 285156 KB ok
21 Correct 120 ms 285160 KB ok
22 Correct 122 ms 285152 KB ok
23 Correct 123 ms 285076 KB ok
24 Correct 127 ms 285084 KB ok
25 Correct 123 ms 285188 KB ok
26 Correct 121 ms 285120 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 285068 KB ok
2 Correct 122 ms 285084 KB ok
3 Correct 121 ms 285052 KB ok
4 Correct 120 ms 285244 KB ok
5 Correct 120 ms 285184 KB ok
6 Correct 121 ms 285024 KB ok
7 Correct 121 ms 285040 KB ok
8 Correct 121 ms 285116 KB ok
9 Correct 128 ms 285128 KB ok
10 Correct 124 ms 285132 KB ok
11 Correct 126 ms 285036 KB ok
12 Correct 122 ms 285024 KB ok
13 Correct 123 ms 285136 KB ok
14 Correct 123 ms 285076 KB ok
15 Correct 126 ms 285088 KB ok
16 Correct 123 ms 285044 KB ok
17 Correct 122 ms 285132 KB ok
18 Correct 122 ms 285092 KB ok
19 Correct 125 ms 285132 KB ok
20 Correct 119 ms 285092 KB ok
21 Correct 121 ms 285132 KB ok
22 Correct 125 ms 285156 KB ok
23 Correct 120 ms 285160 KB ok
24 Correct 122 ms 285152 KB ok
25 Correct 123 ms 285076 KB ok
26 Correct 127 ms 285084 KB ok
27 Correct 123 ms 285188 KB ok
28 Correct 121 ms 285120 KB ok
29 Correct 139 ms 285132 KB ok
30 Correct 127 ms 285660 KB ok
31 Correct 120 ms 285644 KB ok
32 Correct 123 ms 285648 KB ok
33 Correct 120 ms 285572 KB ok
34 Correct 120 ms 285612 KB ok
35 Correct 120 ms 285516 KB ok
36 Correct 120 ms 285452 KB ok
37 Correct 132 ms 285472 KB ok
38 Correct 120 ms 285476 KB ok
39 Correct 121 ms 285512 KB ok
40 Correct 129 ms 285644 KB ok
41 Correct 123 ms 285668 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 285068 KB ok
2 Correct 122 ms 285084 KB ok
3 Correct 121 ms 285052 KB ok
4 Correct 120 ms 285244 KB ok
5 Correct 120 ms 285184 KB ok
6 Correct 121 ms 285024 KB ok
7 Correct 121 ms 285040 KB ok
8 Correct 121 ms 285116 KB ok
9 Correct 128 ms 285128 KB ok
10 Correct 124 ms 285132 KB ok
11 Correct 126 ms 285036 KB ok
12 Correct 122 ms 285024 KB ok
13 Correct 123 ms 285136 KB ok
14 Correct 123 ms 285076 KB ok
15 Correct 126 ms 285088 KB ok
16 Correct 123 ms 285044 KB ok
17 Correct 122 ms 285132 KB ok
18 Correct 122 ms 285092 KB ok
19 Correct 125 ms 285132 KB ok
20 Correct 119 ms 285092 KB ok
21 Correct 121 ms 285132 KB ok
22 Correct 125 ms 285156 KB ok
23 Correct 120 ms 285160 KB ok
24 Correct 122 ms 285152 KB ok
25 Correct 123 ms 285076 KB ok
26 Correct 127 ms 285084 KB ok
27 Correct 123 ms 285188 KB ok
28 Correct 121 ms 285120 KB ok
29 Correct 139 ms 285132 KB ok
30 Correct 127 ms 285660 KB ok
31 Correct 120 ms 285644 KB ok
32 Correct 123 ms 285648 KB ok
33 Correct 120 ms 285572 KB ok
34 Correct 120 ms 285612 KB ok
35 Correct 120 ms 285516 KB ok
36 Correct 120 ms 285452 KB ok
37 Correct 132 ms 285472 KB ok
38 Correct 120 ms 285476 KB ok
39 Correct 121 ms 285512 KB ok
40 Correct 129 ms 285644 KB ok
41 Correct 123 ms 285668 KB ok
42 Correct 307 ms 338636 KB ok
43 Correct 275 ms 334980 KB ok
44 Correct 382 ms 342968 KB ok
45 Correct 389 ms 343296 KB ok
46 Correct 357 ms 340940 KB ok
47 Correct 314 ms 340816 KB ok
48 Correct 248 ms 328884 KB ok
49 Correct 225 ms 329908 KB ok
50 Correct 267 ms 332668 KB ok
51 Correct 323 ms 338472 KB ok
52 Correct 168 ms 315676 KB ok
53 Correct 158 ms 312016 KB ok
54 Correct 192 ms 315880 KB ok
55 Correct 178 ms 319676 KB ok
56 Correct 203 ms 323608 KB ok
57 Correct 298 ms 343060 KB ok
58 Correct 313 ms 343272 KB ok
59 Correct 317 ms 343140 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 285068 KB ok
2 Correct 122 ms 285084 KB ok
3 Correct 121 ms 285052 KB ok
4 Correct 120 ms 285244 KB ok
5 Correct 120 ms 285184 KB ok
6 Correct 120 ms 285092 KB ok
7 Correct 122 ms 285060 KB ok
8 Correct 141 ms 288476 KB ok
9 Correct 294 ms 340648 KB ok
10 Correct 3653 ms 1102724 KB ok
11 Correct 121 ms 285024 KB ok
12 Correct 121 ms 285040 KB ok
13 Correct 121 ms 285116 KB ok
14 Correct 128 ms 285128 KB ok
15 Correct 124 ms 285132 KB ok
16 Correct 126 ms 285036 KB ok
17 Correct 122 ms 285024 KB ok
18 Correct 123 ms 285136 KB ok
19 Correct 123 ms 285076 KB ok
20 Correct 126 ms 285088 KB ok
21 Correct 123 ms 285044 KB ok
22 Correct 122 ms 285132 KB ok
23 Correct 122 ms 285092 KB ok
24 Correct 125 ms 285132 KB ok
25 Correct 119 ms 285092 KB ok
26 Correct 121 ms 285132 KB ok
27 Correct 125 ms 285156 KB ok
28 Correct 120 ms 285160 KB ok
29 Correct 122 ms 285152 KB ok
30 Correct 123 ms 285076 KB ok
31 Correct 127 ms 285084 KB ok
32 Correct 123 ms 285188 KB ok
33 Correct 121 ms 285120 KB ok
34 Correct 139 ms 285132 KB ok
35 Correct 127 ms 285660 KB ok
36 Correct 120 ms 285644 KB ok
37 Correct 123 ms 285648 KB ok
38 Correct 120 ms 285572 KB ok
39 Correct 120 ms 285612 KB ok
40 Correct 120 ms 285516 KB ok
41 Correct 120 ms 285452 KB ok
42 Correct 132 ms 285472 KB ok
43 Correct 120 ms 285476 KB ok
44 Correct 121 ms 285512 KB ok
45 Correct 129 ms 285644 KB ok
46 Correct 123 ms 285668 KB ok
47 Correct 307 ms 338636 KB ok
48 Correct 275 ms 334980 KB ok
49 Correct 382 ms 342968 KB ok
50 Correct 389 ms 343296 KB ok
51 Correct 357 ms 340940 KB ok
52 Correct 314 ms 340816 KB ok
53 Correct 248 ms 328884 KB ok
54 Correct 225 ms 329908 KB ok
55 Correct 267 ms 332668 KB ok
56 Correct 323 ms 338472 KB ok
57 Correct 168 ms 315676 KB ok
58 Correct 158 ms 312016 KB ok
59 Correct 192 ms 315880 KB ok
60 Correct 178 ms 319676 KB ok
61 Correct 203 ms 323608 KB ok
62 Correct 298 ms 343060 KB ok
63 Correct 313 ms 343272 KB ok
64 Correct 317 ms 343140 KB ok
65 Execution timed out 4564 ms 1069632 KB Time limit exceeded
66 Halted 0 ms 0 KB -