oj.uz

Submission #1113689

# Submission time Handle Problem Language Result Execution time Memory
1113689 2024-11-17T05:54:27 Z lighton Soccer Stadium (IOI23_soccer) C++17
22 / 100
 4500 ms 267452 KB 
#include "soccer.h"
#include<bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define forf(i,s,e) for(int i = s; i<=e; i++)
#define forb(i,s,e) for(int i = s; i>=e; i--)
#define idx(i,v) lower_bound(all(v),i)-v.begin()
#define comp(v) v.erase(unique(all(v)),v.end())
#define sz(v) (int)v.size()
#define fs first
#define se second
#define SP << " " <<
#define LN << "\n"
#define IO cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
ll inf = 1e18;

int N;
int arr[2005][2005];
int R[2005][2005],u[2005][2005],d[2005][2005];
struct Rect{
    int rs,re,cs,ce,dp;
    bool operator<(const Rect &r) const{
        if(ce-cs == r.ce-r.cs){
            return re-rs < r.re-r.rs;
        }
        return ce-cs > r.ce-r.cs;
    }
    bool operator==(const Rect &r) const{
        return (rs==r.rs && re==r.re && cs==r.cs && ce==r.ce);
    }
};
vector<Rect> rect;

struct Seg{
    pair<int,int> arr[100001];
    void update(int now, int s, int e, int f, pair<int,int> x){
        if(s==e){ arr[now] = x; return;}
        int m = s+e>>1;
        if(f<=m) update(now*2,s,m,f,x);
        else update(now*2+1,m+1,e,f,x);
        arr[now] = min(arr[now*2],arr[now*2+1]);
    }
    pair<int,int> query(int now,int s, int e, int _l, int _r){
        if(_l<=s && e<=_r) return arr[now];
        if(s>_r || e<_l) return {1e9,1e9};
        int m = s+e>>1;
        return min(query(now*2,s,m,_l,_r),  query(now*2+1,m+1,e,_l,_r));
    }
} seg;
void dnc(int row, int ud, int s, int e){
    if(s>e) return;
    auto [x,m] = seg.query(1,1,N,s,e);
    if(x>0) {
        if (ud == 1) rect.push_back({row, row + x - 1,s,e,0});
        else rect.push_back({row - x + 1, row,s,e,0});
    }

    dnc(row,ud,s,m-1);
    dnc(row,ud,m+1,e);
}
int area(int rs, int re, int cs,int ce){
    return (re-rs+1)*(ce-cs+1);
}


int biggest_stadium(int _N, std::vector<std::vector<int>> F)
{
    N=_N;
    forf(i,0,N+1) forf(j,0,N+1) arr[i][j] = 1;
    forf(i,1,N) forf(j,1,N) arr[i][j] = F[i-1][j-1];
    forf(i,1,N) forf(j,1,N){
        if(arr[i][j] == 1) u[i][j] = 0;
        else u[i][j] = u[i-1][j]+1;
    }
    forb(i,N,1) forb(j,N,1){
        if(arr[i][j] == 1) d[i][j] = 0;
        else d[i][j] = d[i+1][j]+1;
        if(arr[i][j] != arr[i][j+1]) R[i][j] = 1;
        else R[i][j] = R[i][j+1]+1;
    }
    forf(i,1,N){
        forf(j,1,N) seg.update(1,1,N,j,{u[i][j],j});
        dnc(i,0,1,N);
        forf(j,1,N) seg.update(1,1,N,j,{d[i][j],j});
        dnc(i,1,1,N);
    }

    sort(all(rect)); comp(rect);
    int ans = 0;

    for(auto &[rs,re,cs,ce,dp] : rect){
        dp = max(dp, area(rs,re,cs,ce));
        ans = max(ans,dp);
        int nowc = cs;
        if(re<N) {
            while (nowc <= ce) {
                int nxtc = nowc + R[re + 1][nowc];
                if (arr[re + 1][nowc] == 0) {
                    if (binary_search(all(rect),Rect{rs, re + 1, nowc, min(nxtc - 1, ce),0})) {
                        int ind = lower_bound(all(rect),Rect{rs, re + 1, nowc, min(nxtc - 1, ce),0})-rect.begin();
                        rect[ind].dp = max(rect[ind].dp, dp +
                                                         area(rect[ind].rs, rect[ind].re, rect[ind].cs, rect[ind].ce) -
                                                         area(rs, re, rect[ind].cs, rect[ind].ce));
                    }
                }
                nowc = nxtc;
            }
        }
        if(rs > 1) {
            nowc = cs;
            while (nowc <= ce) {
                int nxtc = nowc + R[rs - 1][nowc];
                if (arr[rs - 1][nowc] == 0) {
                    if (binary_search(all(rect),Rect{rs-1, re, nowc, min(nxtc - 1, ce),0})) {
                        int ind = lower_bound(all(rect),Rect{rs-1, re, nowc, min(nxtc - 1, ce),0})-rect.begin();
                        rect[ind].dp = max(rect[ind].dp, dp +
                                                         area(rect[ind].rs, rect[ind].re, rect[ind].cs, rect[ind].ce) -
                                                         area(rs, re, rect[ind].cs, rect[ind].ce));
                    }
                }
                nowc = nxtc;
            }
        }
    }

    return ans;
}

Compilation message

soccer.cpp: In member function 'void Seg::update(int, int, int, int, std::pair<int, int>)':
soccer.cpp:40:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |         int m = s+e>>1;
      |                 ~^~
soccer.cpp: In member function 'std::pair<int, int> Seg::query(int, int, int, int, int)':
soccer.cpp:48:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         int m = s+e>>1;
      |                 ~^~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB ok
2 Correct 2 ms 6480 KB ok
3 Correct 2 ms 6480 KB ok
4 Correct 2 ms 8528 KB ok
5 Correct 2 ms 6480 KB ok
6 Correct 2 ms 6480 KB ok
7 Correct 8 ms 11404 KB ok
8 Correct 168 ms 29268 KB ok
9 Correct 3075 ms 259564 KB ok

Subtask #2
2.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB ok
2 Correct 2 ms 6480 KB ok
3 Partially correct 1 ms 4432 KB partial
4 Correct 1 ms 4432 KB ok
5 Correct 1 ms 6480 KB ok
6 Correct 1 ms 6480 KB ok
7 Correct 1 ms 6480 KB ok
8 Correct 1 ms 6652 KB ok
9 Correct 1 ms 6480 KB ok
10 Correct 2 ms 4444 KB ok
11 Correct 1 ms 4432 KB ok
12 Correct 1 ms 4432 KB ok
13 Correct 1 ms 4432 KB ok

Subtask #3
5.5 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB ok
2 Correct 1 ms 4432 KB ok
3 Correct 2 ms 6480 KB ok
4 Partially correct 1 ms 4432 KB partial
5 Correct 1 ms 4432 KB ok
6 Correct 1 ms 6480 KB ok
7 Correct 1 ms 6480 KB ok
8 Correct 1 ms 6480 KB ok
9 Correct 1 ms 6652 KB ok
10 Correct 1 ms 6480 KB ok
11 Correct 2 ms 4444 KB ok
12 Correct 1 ms 4432 KB ok
13 Correct 1 ms 4432 KB ok
14 Correct 1 ms 4432 KB ok
15 Correct 1 ms 4432 KB ok
16 Correct 1 ms 4432 KB ok
17 Correct 1 ms 4432 KB ok
18 Correct 1 ms 4432 KB ok
19 Correct 1 ms 4600 KB ok
20 Correct 1 ms 4432 KB ok
21 Correct 1 ms 4432 KB ok
22 Correct 1 ms 4432 KB ok
23 Correct 2 ms 4600 KB ok
24 Partially correct 1 ms 4432 KB partial
25 Correct 1 ms 4432 KB ok
26 Correct 1 ms 4432 KB ok

Subtask #4
4.5 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB ok
2 Correct 1 ms 4432 KB ok
3 Correct 2 ms 6480 KB ok
4 Correct 2 ms 6480 KB ok
5 Correct 2 ms 8528 KB ok
6 Partially correct 1 ms 4432 KB partial
7 Correct 1 ms 4432 KB ok
8 Correct 1 ms 6480 KB ok
9 Correct 1 ms 6480 KB ok
10 Correct 1 ms 6480 KB ok
11 Correct 1 ms 6652 KB ok
12 Correct 1 ms 6480 KB ok
13 Correct 2 ms 4444 KB ok
14 Correct 1 ms 4432 KB ok
15 Correct 1 ms 4432 KB ok
16 Correct 1 ms 4432 KB ok
17 Correct 1 ms 4432 KB ok
18 Correct 1 ms 4432 KB ok
19 Correct 1 ms 4432 KB ok
20 Correct 1 ms 4432 KB ok
21 Correct 1 ms 4600 KB ok
22 Correct 1 ms 4432 KB ok
23 Correct 1 ms 4432 KB ok
24 Correct 1 ms 4432 KB ok
25 Correct 2 ms 4600 KB ok
26 Partially correct 1 ms 4432 KB partial
27 Correct 1 ms 4432 KB ok
28 Correct 1 ms 4432 KB ok
29 Correct 1 ms 4432 KB ok
30 Partially correct 2 ms 4688 KB partial
31 Partially correct 2 ms 6736 KB partial
32 Partially correct 2 ms 4688 KB partial
33 Correct 2 ms 6736 KB ok
34 Correct 2 ms 4688 KB ok
35 Correct 2 ms 848 KB ok
36 Correct 1 ms 848 KB ok
37 Correct 1 ms 848 KB ok
38 Correct 2 ms 848 KB ok
39 Correct 2 ms 848 KB ok
40 Correct 2 ms 848 KB ok
41 Correct 2 ms 848 KB ok

Subtask #5
4.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB ok
2 Correct 1 ms 4432 KB ok
3 Correct 2 ms 6480 KB ok
4 Correct 2 ms 6480 KB ok
5 Correct 2 ms 8528 KB ok
6 Partially correct 1 ms 4432 KB partial
7 Correct 1 ms 4432 KB ok
8 Correct 1 ms 6480 KB ok
9 Correct 1 ms 6480 KB ok
10 Correct 1 ms 6480 KB ok
11 Correct 1 ms 6652 KB ok
12 Correct 1 ms 6480 KB ok
13 Correct 2 ms 4444 KB ok
14 Correct 1 ms 4432 KB ok
15 Correct 1 ms 4432 KB ok
16 Correct 1 ms 4432 KB ok
17 Correct 1 ms 4432 KB ok
18 Correct 1 ms 4432 KB ok
19 Correct 1 ms 4432 KB ok
20 Correct 1 ms 4432 KB ok
21 Correct 1 ms 4600 KB ok
22 Correct 1 ms 4432 KB ok
23 Correct 1 ms 4432 KB ok
24 Correct 1 ms 4432 KB ok
25 Correct 2 ms 4600 KB ok
26 Partially correct 1 ms 4432 KB partial
27 Correct 1 ms 4432 KB ok
28 Correct 1 ms 4432 KB ok
29 Correct 1 ms 4432 KB ok
30 Partially correct 2 ms 4688 KB partial
31 Partially correct 2 ms 6736 KB partial
32 Partially correct 2 ms 4688 KB partial
33 Correct 2 ms 6736 KB ok
34 Correct 2 ms 4688 KB ok
35 Correct 2 ms 848 KB ok
36 Correct 1 ms 848 KB ok
37 Correct 1 ms 848 KB ok
38 Correct 2 ms 848 KB ok
39 Correct 2 ms 848 KB ok
40 Correct 2 ms 848 KB ok
41 Correct 2 ms 848 KB ok
42 Partially correct 241 ms 25260 KB partial
43 Partially correct 198 ms 25224 KB partial
44 Partially correct 216 ms 29876 KB partial
45 Partially correct 259 ms 27696 KB partial
46 Partially correct 249 ms 26124 KB partial
47 Correct 226 ms 25284 KB ok
48 Correct 145 ms 20996 KB ok
49 Correct 152 ms 29364 KB ok
50 Correct 1841 ms 31408 KB ok
51 Partially correct 182 ms 31808 KB partial
52 Partially correct 77 ms 21532 KB partial
53 Partially correct 71 ms 19588 KB partial
54 Partially correct 70 ms 20432 KB partial
55 Partially correct 88 ms 21692 KB partial
56 Correct 108 ms 24088 KB ok
57 Correct 172 ms 29364 KB ok
58 Correct 178 ms 27572 KB ok
59 Correct 186 ms 29876 KB ok

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB ok
2 Correct 1 ms 4432 KB ok
3 Correct 2 ms 6480 KB ok
4 Correct 2 ms 6480 KB ok
5 Correct 2 ms 8528 KB ok
6 Correct 2 ms 6480 KB ok
7 Correct 2 ms 6480 KB ok
8 Correct 8 ms 11404 KB ok
9 Correct 168 ms 29268 KB ok
10 Correct 3075 ms 259564 KB ok
11 Partially correct 1 ms 4432 KB partial
12 Correct 1 ms 4432 KB ok
13 Correct 1 ms 6480 KB ok
14 Correct 1 ms 6480 KB ok
15 Correct 1 ms 6480 KB ok
16 Correct 1 ms 6652 KB ok
17 Correct 1 ms 6480 KB ok
18 Correct 2 ms 4444 KB ok
19 Correct 1 ms 4432 KB ok
20 Correct 1 ms 4432 KB ok
21 Correct 1 ms 4432 KB ok
22 Correct 1 ms 4432 KB ok
23 Correct 1 ms 4432 KB ok
24 Correct 1 ms 4432 KB ok
25 Correct 1 ms 4432 KB ok
26 Correct 1 ms 4600 KB ok
27 Correct 1 ms 4432 KB ok
28 Correct 1 ms 4432 KB ok
29 Correct 1 ms 4432 KB ok
30 Correct 2 ms 4600 KB ok
31 Partially correct 1 ms 4432 KB partial
32 Correct 1 ms 4432 KB ok
33 Correct 1 ms 4432 KB ok
34 Correct 1 ms 4432 KB ok
35 Partially correct 2 ms 4688 KB partial
36 Partially correct 2 ms 6736 KB partial
37 Partially correct 2 ms 4688 KB partial
38 Correct 2 ms 6736 KB ok
39 Correct 2 ms 4688 KB ok
40 Correct 2 ms 848 KB ok
41 Correct 1 ms 848 KB ok
42 Correct 1 ms 848 KB ok
43 Correct 2 ms 848 KB ok
44 Correct 2 ms 848 KB ok
45 Correct 2 ms 848 KB ok
46 Correct 2 ms 848 KB ok
47 Partially correct 241 ms 25260 KB partial
48 Partially correct 198 ms 25224 KB partial
49 Partially correct 216 ms 29876 KB partial
50 Partially correct 259 ms 27696 KB partial
51 Partially correct 249 ms 26124 KB partial
52 Correct 226 ms 25284 KB ok
53 Correct 145 ms 20996 KB ok
54 Correct 152 ms 29364 KB ok
55 Correct 1841 ms 31408 KB ok
56 Partially correct 182 ms 31808 KB partial
57 Partially correct 77 ms 21532 KB partial
58 Partially correct 71 ms 19588 KB partial
59 Partially correct 70 ms 20432 KB partial
60 Partially correct 88 ms 21692 KB partial
61 Correct 108 ms 24088 KB ok
62 Correct 172 ms 29364 KB ok
63 Correct 178 ms 27572 KB ok
64 Correct 186 ms 29876 KB ok
65 Partially correct 4368 ms 267452 KB partial
66 Partially correct 1713 ms 185208 KB partial
67 Correct 1312 ms 123804 KB ok
68 Execution timed out 4510 ms 267360 KB Time limit exceeded
69 Halted 0 ms 0 KB -