oj.uz

Submission #853282

# Submission time Handle Problem Language Result Execution time Memory
853282 2023-09-23T21:22:29 Z resting Soccer Stadium (IOI23_soccer) C++17
70 / 100
 4500 ms 1076384 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; // map to good shit ig idkkk

    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;
        }
    }

    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 = owo[{lo2, hi2, j}], id2 = owo[{lo3, hi3, 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++;
        }
    }
    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 = owo[{lo2, hi2, 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 51 ms 328528 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 328532 KB ok
2 Correct 46 ms 328528 KB ok
3 Correct 45 ms 328716 KB ok
4 Correct 47 ms 328528 KB ok
5 Correct 45 ms 328544 KB ok
6 Correct 45 ms 328528 KB ok
7 Correct 48 ms 330028 KB ok
8 Correct 200 ms 362080 KB ok
9 Correct 3117 ms 854388 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 328532 KB ok
2 Correct 46 ms 328528 KB ok
3 Correct 45 ms 328528 KB ok
4 Correct 45 ms 328524 KB ok
5 Correct 44 ms 328564 KB ok
6 Correct 45 ms 328528 KB ok
7 Correct 45 ms 328524 KB ok
8 Correct 48 ms 328592 KB ok
9 Correct 45 ms 328528 KB ok
10 Correct 45 ms 328664 KB ok
11 Correct 45 ms 328528 KB ok
12 Correct 45 ms 328528 KB ok
13 Correct 45 ms 328528 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 328528 KB ok
2 Correct 44 ms 328532 KB ok
3 Correct 46 ms 328528 KB ok
4 Correct 45 ms 328528 KB ok
5 Correct 45 ms 328524 KB ok
6 Correct 44 ms 328564 KB ok
7 Correct 45 ms 328528 KB ok
8 Correct 45 ms 328524 KB ok
9 Correct 48 ms 328592 KB ok
10 Correct 45 ms 328528 KB ok
11 Correct 45 ms 328664 KB ok
12 Correct 45 ms 328528 KB ok
13 Correct 45 ms 328528 KB ok
14 Correct 45 ms 328528 KB ok
15 Correct 46 ms 328528 KB ok
16 Correct 45 ms 328660 KB ok
17 Correct 45 ms 328528 KB ok
18 Correct 45 ms 328528 KB ok
19 Correct 46 ms 328528 KB ok
20 Correct 46 ms 328528 KB ok
21 Correct 45 ms 328528 KB ok
22 Correct 47 ms 328576 KB ok
23 Correct 47 ms 328532 KB ok
24 Correct 46 ms 328528 KB ok
25 Correct 46 ms 328528 KB ok
26 Correct 47 ms 328528 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 328528 KB ok
2 Correct 44 ms 328532 KB ok
3 Correct 46 ms 328528 KB ok
4 Correct 45 ms 328716 KB ok
5 Correct 47 ms 328528 KB ok
6 Correct 45 ms 328528 KB ok
7 Correct 45 ms 328524 KB ok
8 Correct 44 ms 328564 KB ok
9 Correct 45 ms 328528 KB ok
10 Correct 45 ms 328524 KB ok
11 Correct 48 ms 328592 KB ok
12 Correct 45 ms 328528 KB ok
13 Correct 45 ms 328664 KB ok
14 Correct 45 ms 328528 KB ok
15 Correct 45 ms 328528 KB ok
16 Correct 45 ms 328528 KB ok
17 Correct 46 ms 328528 KB ok
18 Correct 45 ms 328660 KB ok
19 Correct 45 ms 328528 KB ok
20 Correct 45 ms 328528 KB ok
21 Correct 46 ms 328528 KB ok
22 Correct 46 ms 328528 KB ok
23 Correct 45 ms 328528 KB ok
24 Correct 47 ms 328576 KB ok
25 Correct 47 ms 328532 KB ok
26 Correct 46 ms 328528 KB ok
27 Correct 46 ms 328528 KB ok
28 Correct 47 ms 328528 KB ok
29 Correct 45 ms 328528 KB ok
30 Correct 45 ms 328744 KB ok
31 Correct 46 ms 328784 KB ok
32 Correct 46 ms 328784 KB ok
33 Correct 56 ms 328784 KB ok
34 Correct 45 ms 328784 KB ok
35 Correct 45 ms 328788 KB ok
36 Correct 45 ms 328784 KB ok
37 Correct 46 ms 328784 KB ok
38 Correct 45 ms 328788 KB ok
39 Correct 46 ms 328784 KB ok
40 Correct 46 ms 328684 KB ok
41 Correct 45 ms 328780 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 328528 KB ok
2 Correct 44 ms 328532 KB ok
3 Correct 46 ms 328528 KB ok
4 Correct 45 ms 328716 KB ok
5 Correct 47 ms 328528 KB ok
6 Correct 45 ms 328528 KB ok
7 Correct 45 ms 328524 KB ok
8 Correct 44 ms 328564 KB ok
9 Correct 45 ms 328528 KB ok
10 Correct 45 ms 328524 KB ok
11 Correct 48 ms 328592 KB ok
12 Correct 45 ms 328528 KB ok
13 Correct 45 ms 328664 KB ok
14 Correct 45 ms 328528 KB ok
15 Correct 45 ms 328528 KB ok
16 Correct 45 ms 328528 KB ok
17 Correct 46 ms 328528 KB ok
18 Correct 45 ms 328660 KB ok
19 Correct 45 ms 328528 KB ok
20 Correct 45 ms 328528 KB ok
21 Correct 46 ms 328528 KB ok
22 Correct 46 ms 328528 KB ok
23 Correct 45 ms 328528 KB ok
24 Correct 47 ms 328576 KB ok
25 Correct 47 ms 328532 KB ok
26 Correct 46 ms 328528 KB ok
27 Correct 46 ms 328528 KB ok
28 Correct 47 ms 328528 KB ok
29 Correct 45 ms 328528 KB ok
30 Correct 45 ms 328744 KB ok
31 Correct 46 ms 328784 KB ok
32 Correct 46 ms 328784 KB ok
33 Correct 56 ms 328784 KB ok
34 Correct 45 ms 328784 KB ok
35 Correct 45 ms 328788 KB ok
36 Correct 45 ms 328784 KB ok
37 Correct 46 ms 328784 KB ok
38 Correct 45 ms 328788 KB ok
39 Correct 46 ms 328784 KB ok
40 Correct 46 ms 328684 KB ok
41 Correct 45 ms 328780 KB ok
42 Correct 435 ms 388348 KB ok
43 Correct 351 ms 380944 KB ok
44 Correct 463 ms 396152 KB ok
45 Correct 441 ms 394236 KB ok
46 Correct 455 ms 393528 KB ok
47 Correct 269 ms 369524 KB ok
48 Correct 232 ms 366092 KB ok
49 Correct 241 ms 368252 KB ok
50 Correct 255 ms 375632 KB ok
51 Correct 314 ms 374668 KB ok
52 Correct 124 ms 354864 KB ok
53 Correct 97 ms 352112 KB ok
54 Correct 111 ms 353856 KB ok
55 Correct 149 ms 358132 KB ok
56 Correct 143 ms 355472 KB ok
57 Correct 324 ms 378832 KB ok
58 Correct 350 ms 380224 KB ok
59 Correct 355 ms 381336 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 328528 KB ok
2 Correct 44 ms 328532 KB ok
3 Correct 46 ms 328528 KB ok
4 Correct 45 ms 328716 KB ok
5 Correct 47 ms 328528 KB ok
6 Correct 45 ms 328544 KB ok
7 Correct 45 ms 328528 KB ok
8 Correct 48 ms 330028 KB ok
9 Correct 200 ms 362080 KB ok
10 Correct 3117 ms 854388 KB ok
11 Correct 45 ms 328528 KB ok
12 Correct 45 ms 328524 KB ok
13 Correct 44 ms 328564 KB ok
14 Correct 45 ms 328528 KB ok
15 Correct 45 ms 328524 KB ok
16 Correct 48 ms 328592 KB ok
17 Correct 45 ms 328528 KB ok
18 Correct 45 ms 328664 KB ok
19 Correct 45 ms 328528 KB ok
20 Correct 45 ms 328528 KB ok
21 Correct 45 ms 328528 KB ok
22 Correct 46 ms 328528 KB ok
23 Correct 45 ms 328660 KB ok
24 Correct 45 ms 328528 KB ok
25 Correct 45 ms 328528 KB ok
26 Correct 46 ms 328528 KB ok
27 Correct 46 ms 328528 KB ok
28 Correct 45 ms 328528 KB ok
29 Correct 47 ms 328576 KB ok
30 Correct 47 ms 328532 KB ok
31 Correct 46 ms 328528 KB ok
32 Correct 46 ms 328528 KB ok
33 Correct 47 ms 328528 KB ok
34 Correct 45 ms 328528 KB ok
35 Correct 45 ms 328744 KB ok
36 Correct 46 ms 328784 KB ok
37 Correct 46 ms 328784 KB ok
38 Correct 56 ms 328784 KB ok
39 Correct 45 ms 328784 KB ok
40 Correct 45 ms 328788 KB ok
41 Correct 45 ms 328784 KB ok
42 Correct 46 ms 328784 KB ok
43 Correct 45 ms 328788 KB ok
44 Correct 46 ms 328784 KB ok
45 Correct 46 ms 328684 KB ok
46 Correct 45 ms 328780 KB ok
47 Correct 435 ms 388348 KB ok
48 Correct 351 ms 380944 KB ok
49 Correct 463 ms 396152 KB ok
50 Correct 441 ms 394236 KB ok
51 Correct 455 ms 393528 KB ok
52 Correct 269 ms 369524 KB ok
53 Correct 232 ms 366092 KB ok
54 Correct 241 ms 368252 KB ok
55 Correct 255 ms 375632 KB ok
56 Correct 314 ms 374668 KB ok
57 Correct 124 ms 354864 KB ok
58 Correct 97 ms 352112 KB ok
59 Correct 111 ms 353856 KB ok
60 Correct 149 ms 358132 KB ok
61 Correct 143 ms 355472 KB ok
62 Correct 324 ms 378832 KB ok
63 Correct 350 ms 380224 KB ok
64 Correct 355 ms 381336 KB ok
65 Execution timed out 4561 ms 1076384 KB Time limit exceeded
66 Halted 0 ms 0 KB -