oj.uz

Submission #853284

# Submission time Handle Problem Language Result Execution time Memory
853284 2023-09-23T21:29:48 Z resting Soccer Stadium (IOI23_soccer) C++17
100 / 100
 4369 ms 1477204 KB 
#include <bits/stdc++.h>
using namespace std;
//#include "soccer.h"

#define int long long

struct segtree{ //range max
    int l, r; 
    int v = -1;
    segtree *lc = 0, *rc = 0;
    segtree*getmem();
    segtree(int l, int r): l(l), r(r){
        if(l == r) return;
        int m = (l+r)/2;
        lc = getmem(); *lc = segtree(l, m);
        rc = getmem(); *rc = segtree(m+1, r);
    }
    segtree():segtree(-1, -1){};
    int q(int ql, int qr){
        if(ql <= l && r <= qr) return v;
        if(qr < l || ql > r) return -1;
        return max(lc->q(ql, qr), rc->q(ql, qr));
    }
    void upd(int qi, int qv){
        if(qi < l || qi > r) return;
        if(l == r){v = qv; return;}
        lc->upd(qi, qv); rc->upd(qi, qv);
        v = max(lc->v, rc->v);
    }
}mem[1024*1024*4*2]; int memsz = 0;
segtree* segtree::getmem(){return &mem[memsz++];}

int solve(int n, vector<vector<pair<int,int>>> &adj){
    vector<int> cnt(n);
    for(auto j : adj) for(auto &x : j)cnt[x.first]++;
    vector<int> q; // topological sorting
    for(int i = 0; i < n; i++) if(cnt[i] == 0) q.push_back(i);
    vector<int> sort;
    while(q.size()){
        int v = q.back();
        q.pop_back();
        sort.push_back(v);
        for(auto &x : adj[v]){
            cnt[x.first]--;
            if(cnt[x.first]==0)
            q.push_back(x.first);
        }
    }
    //sorted
    vector<int> dp(n, 0);
    int res = 0;
    for(auto &x : sort){
        res = max(res, dp[x]);
        for(auto &j : adj[x]){
            dp[j.first] = max(dp[j.first], dp[x] + j.second);
        }
    }
    return res;
}

int32_t biggest_stadium(int32_t N, std::vector<std::vector<int32_t>> F){
    map<vector<int>, int> owo; int cur = 1; 

    vector<vector<pair<int,int>>> adj(N*N+5); // shouldnt be moree??
    //set up segtree???
    vector<vector<int>> lo, hi, l;
    lo = hi = l = vector<vector<int>>(N, vector<int>(N, -1));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(j) l[i][j] = l[i][j-1];
            if(F[i][j]) l[i][j] = j;
        }
    }

    segtree uwu(0, N-1);

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(F[i][j]) uwu.upd(j, i);
        }
        for(int j = 0; j < N; j++){
            if(F[i][j]) continue;
            lo[i][j] = uwu.q(l[i][j]+1, j)+1;
        }
    }

    uwu = segtree(0, N-1);
    for(int i = N-1; i >= 0; i--){
        for(int j = 0; j < N; j++){
            if(F[i][j]) uwu.upd(j, N-i-1);
        }
        for(int j = 0; j < N; j++){
            if(F[i][j]) continue;
            hi[i][j] = N-uwu.q(l[i][j]+1, j)-2;
        }
    }

    vector<vector<int>> owo2(N, vector<int>(N));

    auto extend = [&](int i, int j, int i2, int j2){
        int lo2 = lo[i][j], hi2 = hi[i][j], lo3 = lo[i2][j2], hi3 = hi[i2][j2];
        int id = owo2[i][j], id2 = owo2[i2][j2];
        adj[id].push_back(make_pair(id2, (lo2-lo3 + hi3-hi2) * (j2 - l[i2][j2])));

    };
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(F[i][j]) continue;
            int lo2 = lo[i][j];
            int hi2 = hi[i][j];
            if(!owo.count({lo2, hi2, j})) owo[{lo2, hi2, j}] = cur++;
            owo2[i][j] = owo[{lo2, hi2, j}];
        }
    }
    for(int i =  0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(F[i][j]) continue;
            int lo2 = lo[i][j];
            int hi2 = hi[i][j];
            int id = owo2[i][j];
            adj[0].push_back(make_pair(id, (hi2-lo2+1) * (j - (l[i][j]+1) + 1)));

            if(l[i][j]+1 != j){
                extend(i, j, i, j-1);
            }

            if(lo2 && !F[lo2-1][j]){
                extend(i, j, lo2-1, j);
            }

            if(hi2 < N-1 && !F[hi2+1][j]){
                extend(i, j, hi2+1, j);
            }
        }
    }
    return solve(adj.size(), adj);
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 328536 KB ok
2 Correct 46 ms 328512 KB ok
3 Correct 45 ms 328560 KB ok
4 Correct 46 ms 328508 KB ok
5 Correct 45 ms 328684 KB ok
6 Correct 44 ms 328524 KB ok
7 Correct 48 ms 330024 KB ok
8 Correct 141 ms 364052 KB ok
9 Correct 1803 ms 887656 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 328536 KB ok
2 Correct 46 ms 328512 KB ok
3 Correct 46 ms 328532 KB ok
4 Correct 47 ms 328532 KB ok
5 Correct 46 ms 328532 KB ok
6 Correct 47 ms 328584 KB ok
7 Correct 44 ms 328540 KB ok
8 Correct 45 ms 328532 KB ok
9 Correct 49 ms 328628 KB ok
10 Correct 45 ms 328532 KB ok
11 Correct 45 ms 328784 KB ok
12 Correct 44 ms 328788 KB ok
13 Correct 46 ms 328540 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 328532 KB ok
2 Correct 45 ms 328536 KB ok
3 Correct 46 ms 328512 KB ok
4 Correct 46 ms 328532 KB ok
5 Correct 47 ms 328532 KB ok
6 Correct 46 ms 328532 KB ok
7 Correct 47 ms 328584 KB ok
8 Correct 44 ms 328540 KB ok
9 Correct 45 ms 328532 KB ok
10 Correct 49 ms 328628 KB ok
11 Correct 45 ms 328532 KB ok
12 Correct 45 ms 328784 KB ok
13 Correct 44 ms 328788 KB ok
14 Correct 46 ms 328540 KB ok
15 Correct 45 ms 328544 KB ok
16 Correct 46 ms 328712 KB ok
17 Correct 44 ms 328548 KB ok
18 Correct 46 ms 328788 KB ok
19 Correct 44 ms 328528 KB ok
20 Correct 47 ms 328536 KB ok
21 Correct 47 ms 328724 KB ok
22 Correct 45 ms 328544 KB ok
23 Correct 44 ms 328528 KB ok
24 Correct 47 ms 328732 KB ok
25 Correct 44 ms 328528 KB ok
26 Correct 46 ms 328664 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 328532 KB ok
2 Correct 45 ms 328536 KB ok
3 Correct 46 ms 328512 KB ok
4 Correct 45 ms 328560 KB ok
5 Correct 46 ms 328508 KB ok
6 Correct 46 ms 328532 KB ok
7 Correct 47 ms 328532 KB ok
8 Correct 46 ms 328532 KB ok
9 Correct 47 ms 328584 KB ok
10 Correct 44 ms 328540 KB ok
11 Correct 45 ms 328532 KB ok
12 Correct 49 ms 328628 KB ok
13 Correct 45 ms 328532 KB ok
14 Correct 45 ms 328784 KB ok
15 Correct 44 ms 328788 KB ok
16 Correct 46 ms 328540 KB ok
17 Correct 45 ms 328544 KB ok
18 Correct 46 ms 328712 KB ok
19 Correct 44 ms 328548 KB ok
20 Correct 46 ms 328788 KB ok
21 Correct 44 ms 328528 KB ok
22 Correct 47 ms 328536 KB ok
23 Correct 47 ms 328724 KB ok
24 Correct 45 ms 328544 KB ok
25 Correct 44 ms 328528 KB ok
26 Correct 47 ms 328732 KB ok
27 Correct 44 ms 328528 KB ok
28 Correct 46 ms 328664 KB ok
29 Correct 45 ms 328532 KB ok
30 Correct 48 ms 328688 KB ok
31 Correct 45 ms 328772 KB ok
32 Correct 48 ms 328784 KB ok
33 Correct 46 ms 328788 KB ok
34 Correct 45 ms 328788 KB ok
35 Correct 45 ms 328948 KB ok
36 Correct 47 ms 328784 KB ok
37 Correct 45 ms 328644 KB ok
38 Correct 46 ms 328656 KB ok
39 Correct 45 ms 328788 KB ok
40 Correct 46 ms 328768 KB ok
41 Correct 46 ms 328840 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 328532 KB ok
2 Correct 45 ms 328536 KB ok
3 Correct 46 ms 328512 KB ok
4 Correct 45 ms 328560 KB ok
5 Correct 46 ms 328508 KB ok
6 Correct 46 ms 328532 KB ok
7 Correct 47 ms 328532 KB ok
8 Correct 46 ms 328532 KB ok
9 Correct 47 ms 328584 KB ok
10 Correct 44 ms 328540 KB ok
11 Correct 45 ms 328532 KB ok
12 Correct 49 ms 328628 KB ok
13 Correct 45 ms 328532 KB ok
14 Correct 45 ms 328784 KB ok
15 Correct 44 ms 328788 KB ok
16 Correct 46 ms 328540 KB ok
17 Correct 45 ms 328544 KB ok
18 Correct 46 ms 328712 KB ok
19 Correct 44 ms 328548 KB ok
20 Correct 46 ms 328788 KB ok
21 Correct 44 ms 328528 KB ok
22 Correct 47 ms 328536 KB ok
23 Correct 47 ms 328724 KB ok
24 Correct 45 ms 328544 KB ok
25 Correct 44 ms 328528 KB ok
26 Correct 47 ms 328732 KB ok
27 Correct 44 ms 328528 KB ok
28 Correct 46 ms 328664 KB ok
29 Correct 45 ms 328532 KB ok
30 Correct 48 ms 328688 KB ok
31 Correct 45 ms 328772 KB ok
32 Correct 48 ms 328784 KB ok
33 Correct 46 ms 328788 KB ok
34 Correct 45 ms 328788 KB ok
35 Correct 45 ms 328948 KB ok
36 Correct 47 ms 328784 KB ok
37 Correct 45 ms 328644 KB ok
38 Correct 46 ms 328656 KB ok
39 Correct 45 ms 328788 KB ok
40 Correct 46 ms 328768 KB ok
41 Correct 46 ms 328840 KB ok
42 Correct 284 ms 390660 KB ok
43 Correct 261 ms 383004 KB ok
44 Correct 282 ms 398520 KB ok
45 Correct 283 ms 396348 KB ok
46 Correct 289 ms 395492 KB ok
47 Correct 157 ms 371504 KB ok
48 Correct 160 ms 368132 KB ok
49 Correct 164 ms 369464 KB ok
50 Correct 191 ms 376836 KB ok
51 Correct 224 ms 376452 KB ok
52 Correct 105 ms 356924 KB ok
53 Correct 96 ms 354276 KB ok
54 Correct 109 ms 355460 KB ok
55 Correct 133 ms 360240 KB ok
56 Correct 112 ms 357520 KB ok
57 Correct 222 ms 380972 KB ok
58 Correct 231 ms 382044 KB ok
59 Correct 260 ms 383244 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 328532 KB ok
2 Correct 45 ms 328536 KB ok
3 Correct 46 ms 328512 KB ok
4 Correct 45 ms 328560 KB ok
5 Correct 46 ms 328508 KB ok
6 Correct 45 ms 328684 KB ok
7 Correct 44 ms 328524 KB ok
8 Correct 48 ms 330024 KB ok
9 Correct 141 ms 364052 KB ok
10 Correct 1803 ms 887656 KB ok
11 Correct 46 ms 328532 KB ok
12 Correct 47 ms 328532 KB ok
13 Correct 46 ms 328532 KB ok
14 Correct 47 ms 328584 KB ok
15 Correct 44 ms 328540 KB ok
16 Correct 45 ms 328532 KB ok
17 Correct 49 ms 328628 KB ok
18 Correct 45 ms 328532 KB ok
19 Correct 45 ms 328784 KB ok
20 Correct 44 ms 328788 KB ok
21 Correct 46 ms 328540 KB ok
22 Correct 45 ms 328544 KB ok
23 Correct 46 ms 328712 KB ok
24 Correct 44 ms 328548 KB ok
25 Correct 46 ms 328788 KB ok
26 Correct 44 ms 328528 KB ok
27 Correct 47 ms 328536 KB ok
28 Correct 47 ms 328724 KB ok
29 Correct 45 ms 328544 KB ok
30 Correct 44 ms 328528 KB ok
31 Correct 47 ms 328732 KB ok
32 Correct 44 ms 328528 KB ok
33 Correct 46 ms 328664 KB ok
34 Correct 45 ms 328532 KB ok
35 Correct 48 ms 328688 KB ok
36 Correct 45 ms 328772 KB ok
37 Correct 48 ms 328784 KB ok
38 Correct 46 ms 328788 KB ok
39 Correct 45 ms 328788 KB ok
40 Correct 45 ms 328948 KB ok
41 Correct 47 ms 328784 KB ok
42 Correct 45 ms 328644 KB ok
43 Correct 46 ms 328656 KB ok
44 Correct 45 ms 328788 KB ok
45 Correct 46 ms 328768 KB ok
46 Correct 46 ms 328840 KB ok
47 Correct 284 ms 390660 KB ok
48 Correct 261 ms 383004 KB ok
49 Correct 282 ms 398520 KB ok
50 Correct 283 ms 396348 KB ok
51 Correct 289 ms 395492 KB ok
52 Correct 157 ms 371504 KB ok
53 Correct 160 ms 368132 KB ok
54 Correct 164 ms 369464 KB ok
55 Correct 191 ms 376836 KB ok
56 Correct 224 ms 376452 KB ok
57 Correct 105 ms 356924 KB ok
58 Correct 96 ms 354276 KB ok
59 Correct 109 ms 355460 KB ok
60 Correct 133 ms 360240 KB ok
61 Correct 112 ms 357520 KB ok
62 Correct 222 ms 380972 KB ok
63 Correct 231 ms 382044 KB ok
64 Correct 260 ms 383244 KB ok
65 Correct 4184 ms 1319248 KB ok
66 Correct 1828 ms 842132 KB ok
67 Correct 1183 ms 752264 KB ok
68 Correct 3603 ms 1408320 KB ok
69 Correct 4259 ms 1477204 KB ok
70 Correct 4369 ms 1449952 KB ok
71 Correct 3308 ms 1331676 KB ok
72 Correct 2045 ms 1025820 KB ok
73 Correct 2130 ms 961012 KB ok
74 Correct 2174 ms 971396 KB ok
75 Correct 2123 ms 961836 KB ok
76 Correct 2769 ms 1099364 KB ok
77 Correct 2739 ms 1098488 KB ok
78 Correct 3235 ms 1156364 KB ok
79 Correct 1060 ms 732604 KB ok
80 Correct 1094 ms 732236 KB ok
81 Correct 1240 ms 764216 KB ok
82 Correct 1673 ms 849444 KB ok
83 Correct 1552 ms 807200 KB ok
84 Correct 1135 ms 766752 KB ok
85 Correct 1065 ms 742080 KB ok
86 Correct 1286 ms 794032 KB ok
87 Correct 1338 ms 795068 KB ok
88 Correct 1555 ms 856024 KB ok
89 Correct 2374 ms 1028448 KB ok
90 Correct 2202 ms 999732 KB ok
91 Correct 2626 ms 1054840 KB ok
92 Correct 1307 ms 769132 KB ok
93 Correct 1326 ms 757792 KB ok
94 Correct 1217 ms 751732 KB ok
95 Correct 1156 ms 758620 KB ok
96 Correct 1131 ms 759432 KB ok
97 Correct 1146 ms 759540 KB ok
98 Correct 985 ms 733808 KB ok
99 Correct 3476 ms 1268148 KB ok
100 Correct 3399 ms 1160176 KB ok
101 Correct 3012 ms 1138448 KB ok
102 Correct 3033 ms 1162348 KB ok
103 Correct 3755 ms 1183928 KB ok
104 Correct 3140 ms 1196588 KB ok
105 Correct 3212 ms 1201832 KB ok
106 Correct 4086 ms 1211456 KB ok
107 Correct 4320 ms 1215264 KB ok
108 Correct 2462 ms 933224 KB ok
109 Correct 2426 ms 934984 KB ok