oj.uz

Submission #1113712

# Submission time Handle Problem Language Result Execution time Memory
1113712 2024-11-17T08:24:12 Z lighton Soccer Stadium (IOI23_soccer) C++17
100 / 100
 4310 ms 348332 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];
int p = 4000;
struct Rect{
    int rs,re,cs,ce,id,dp;
    bool operator<(const Rect &r) const{
        return array<int,3>{(cs-ce)*p + re-rs, rs*p+cs, id} < array<int,3>{(r.cs-r.ce)*p+r.re-r.rs, r.rs*p+r.cs, r.id};
    }
    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[8001];
    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));
    }
} segu[2001], segd[2001];


void dnc(int row, int ud, int s, int e, int prev){
    if(s>e) return;
    pair<int,int> tmp;
    if(ud == 1) tmp = segd[row].query(1,1,N,s,e);
    else tmp = segu[row].query(1,1,N,s,e);
    int x=tmp.fs, m = tmp.se;
    if(x>prev) {
        if (ud == 1 && segu[row].query(1,1,N,s,e).fs==1) rect.push_back({row, row + x - 1,s,e,sz(rect),0});
        else if( ud == 0 && segd[row].query(1,1,N,s,e).fs==1)rect.push_back({row - x + 1, row,s,e,sz(rect),0});
    }

    dnc(row,ud,s,m-1,x);
    dnc(row,ud,m+1,e,x);
}
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) segu[i].update(1,1,N,j,{u[i][j],j});
        forf(j,1,N) segd[i].update(1,1,N,j,{d[i][j],j});
    }
    forf(i,1,N){
        dnc(i,0,1,N,0);
        dnc(i,1,1,N,0);
    }

    assert(sz(rect) < 4000000);
    sort(all(rect)); comp(rect);
    forf(i,0,sz(rect)-1) rect[i].id = i;
    int ans = 0;

    for(auto &[rs,re,cs,ce,id,dp] : rect){
        dp = max(dp, area(rs,re,cs,ce));
        ans = max(ans,dp);

        if(re<N) {
            int nowc = cs;
            while (nowc <= ce) {
                int nxtc = nowc + R[re + 1][nowc];
                if (arr[re + 1][nowc] == 0) {
                    int nce = min(nxtc - 1, ce);
                    int nre = re+1 + segd[re+1].query(1,1,N,nowc,nce).fs-1;
                    int nrs = re+1 - segu[re+1].query(1,1,N,nowc,nce).fs+1;
                    int ind = lower_bound(all(rect),Rect{nrs, nre ,nowc, nce,-1,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) {
            int nowc = cs;
            while (nowc <= ce) {
                int nxtc = nowc + R[rs - 1][nowc];
                if (arr[rs - 1][nowc] == 0) {
                    int nce = min(nxtc - 1, ce);
                    int nrs = rs-1 - segu[rs-1].query(1,1,N,nowc,nce).fs+1;
                    int nre = rs-1 + segd[rs-1].query(1,1,N,nowc,nce).fs-1;
                    int ind = lower_bound(all(rect),Rect{nrs, nre, nowc, nce,-1,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:38:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         int m = s+e>>1;
      |                 ~^~
soccer.cpp: In member function 'std::pair<int, int> Seg::query(int, int, int, int, int)':
soccer.cpp:46:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         int m = s+e>>1;
      |                 ~^~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8528 KB ok
2 Correct 2 ms 10576 KB ok
3 Correct 2 ms 12624 KB ok
4 Correct 2 ms 10576 KB ok
5 Correct 1 ms 8528 KB ok
6 Correct 2 ms 10576 KB ok
7 Correct 6 ms 23376 KB ok
8 Correct 66 ms 41056 KB ok
9 Correct 1201 ms 242480 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8528 KB ok
2 Correct 2 ms 10576 KB ok
3 Correct 2 ms 8528 KB ok
4 Correct 2 ms 8528 KB ok
5 Correct 3 ms 10576 KB ok
6 Correct 2 ms 10576 KB ok
7 Correct 2 ms 10576 KB ok
8 Correct 2 ms 10744 KB ok
9 Correct 2 ms 10576 KB ok
10 Correct 2 ms 10576 KB ok
11 Correct 2 ms 8528 KB ok
12 Correct 1 ms 8528 KB ok
13 Correct 2 ms 12624 KB ok

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10576 KB ok
2 Correct 1 ms 8528 KB ok
3 Correct 2 ms 10576 KB ok
4 Correct 2 ms 8528 KB ok
5 Correct 2 ms 8528 KB ok
6 Correct 3 ms 10576 KB ok
7 Correct 2 ms 10576 KB ok
8 Correct 2 ms 10576 KB ok
9 Correct 2 ms 10744 KB ok
10 Correct 2 ms 10576 KB ok
11 Correct 2 ms 10576 KB ok
12 Correct 2 ms 8528 KB ok
13 Correct 1 ms 8528 KB ok
14 Correct 2 ms 12624 KB ok
15 Correct 2 ms 10576 KB ok
16 Correct 2 ms 10576 KB ok
17 Correct 2 ms 8528 KB ok
18 Correct 2 ms 8528 KB ok
19 Correct 2 ms 8528 KB ok
20 Correct 2 ms 10576 KB ok
21 Correct 2 ms 10576 KB ok
22 Correct 2 ms 10576 KB ok
23 Correct 2 ms 10576 KB ok
24 Correct 2 ms 10576 KB ok
25 Correct 2 ms 10576 KB ok
26 Correct 2 ms 10576 KB ok

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10576 KB ok
2 Correct 1 ms 8528 KB ok
3 Correct 2 ms 10576 KB ok
4 Correct 2 ms 12624 KB ok
5 Correct 2 ms 10576 KB ok
6 Correct 2 ms 8528 KB ok
7 Correct 2 ms 8528 KB ok
8 Correct 3 ms 10576 KB ok
9 Correct 2 ms 10576 KB ok
10 Correct 2 ms 10576 KB ok
11 Correct 2 ms 10744 KB ok
12 Correct 2 ms 10576 KB ok
13 Correct 2 ms 10576 KB ok
14 Correct 2 ms 8528 KB ok
15 Correct 1 ms 8528 KB ok
16 Correct 2 ms 12624 KB ok
17 Correct 2 ms 10576 KB ok
18 Correct 2 ms 10576 KB ok
19 Correct 2 ms 8528 KB ok
20 Correct 2 ms 8528 KB ok
21 Correct 2 ms 8528 KB ok
22 Correct 2 ms 10576 KB ok
23 Correct 2 ms 10576 KB ok
24 Correct 2 ms 10576 KB ok
25 Correct 2 ms 10576 KB ok
26 Correct 2 ms 10576 KB ok
27 Correct 2 ms 10576 KB ok
28 Correct 2 ms 10576 KB ok
29 Correct 2 ms 10744 KB ok
30 Correct 2 ms 10832 KB ok
31 Correct 3 ms 10832 KB ok
32 Correct 3 ms 10832 KB ok
33 Correct 2 ms 10832 KB ok
34 Correct 2 ms 8784 KB ok
35 Correct 2 ms 11000 KB ok
36 Correct 2 ms 10832 KB ok
37 Correct 2 ms 10832 KB ok
38 Correct 3 ms 10832 KB ok
39 Correct 3 ms 10832 KB ok
40 Correct 2 ms 8784 KB ok
41 Correct 2 ms 10832 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10576 KB ok
2 Correct 1 ms 8528 KB ok
3 Correct 2 ms 10576 KB ok
4 Correct 2 ms 12624 KB ok
5 Correct 2 ms 10576 KB ok
6 Correct 2 ms 8528 KB ok
7 Correct 2 ms 8528 KB ok
8 Correct 3 ms 10576 KB ok
9 Correct 2 ms 10576 KB ok
10 Correct 2 ms 10576 KB ok
11 Correct 2 ms 10744 KB ok
12 Correct 2 ms 10576 KB ok
13 Correct 2 ms 10576 KB ok
14 Correct 2 ms 8528 KB ok
15 Correct 1 ms 8528 KB ok
16 Correct 2 ms 12624 KB ok
17 Correct 2 ms 10576 KB ok
18 Correct 2 ms 10576 KB ok
19 Correct 2 ms 8528 KB ok
20 Correct 2 ms 8528 KB ok
21 Correct 2 ms 8528 KB ok
22 Correct 2 ms 10576 KB ok
23 Correct 2 ms 10576 KB ok
24 Correct 2 ms 10576 KB ok
25 Correct 2 ms 10576 KB ok
26 Correct 2 ms 10576 KB ok
27 Correct 2 ms 10576 KB ok
28 Correct 2 ms 10576 KB ok
29 Correct 2 ms 10744 KB ok
30 Correct 2 ms 10832 KB ok
31 Correct 3 ms 10832 KB ok
32 Correct 3 ms 10832 KB ok
33 Correct 2 ms 10832 KB ok
34 Correct 2 ms 8784 KB ok
35 Correct 2 ms 11000 KB ok
36 Correct 2 ms 10832 KB ok
37 Correct 2 ms 10832 KB ok
38 Correct 3 ms 10832 KB ok
39 Correct 3 ms 10832 KB ok
40 Correct 2 ms 8784 KB ok
41 Correct 2 ms 10832 KB ok
42 Correct 213 ms 46024 KB ok
43 Correct 182 ms 41052 KB ok
44 Correct 139 ms 45388 KB ok
45 Correct 119 ms 43628 KB ok
46 Correct 203 ms 43196 KB ok
47 Correct 65 ms 37704 KB ok
48 Correct 82 ms 36168 KB ok
49 Correct 87 ms 39496 KB ok
50 Correct 93 ms 37712 KB ok
51 Correct 113 ms 40128 KB ok
52 Correct 64 ms 37960 KB ok
53 Correct 59 ms 39496 KB ok
54 Correct 61 ms 42824 KB ok
55 Correct 65 ms 36272 KB ok
56 Correct 66 ms 36168 KB ok
57 Correct 160 ms 37592 KB ok
58 Correct 175 ms 46112 KB ok
59 Correct 193 ms 42496 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10576 KB ok
2 Correct 1 ms 8528 KB ok
3 Correct 2 ms 10576 KB ok
4 Correct 2 ms 12624 KB ok
5 Correct 2 ms 10576 KB ok
6 Correct 1 ms 8528 KB ok
7 Correct 2 ms 10576 KB ok
8 Correct 6 ms 23376 KB ok
9 Correct 66 ms 41056 KB ok
10 Correct 1201 ms 242480 KB ok
11 Correct 2 ms 8528 KB ok
12 Correct 2 ms 8528 KB ok
13 Correct 3 ms 10576 KB ok
14 Correct 2 ms 10576 KB ok
15 Correct 2 ms 10576 KB ok
16 Correct 2 ms 10744 KB ok
17 Correct 2 ms 10576 KB ok
18 Correct 2 ms 10576 KB ok
19 Correct 2 ms 8528 KB ok
20 Correct 1 ms 8528 KB ok
21 Correct 2 ms 12624 KB ok
22 Correct 2 ms 10576 KB ok
23 Correct 2 ms 10576 KB ok
24 Correct 2 ms 8528 KB ok
25 Correct 2 ms 8528 KB ok
26 Correct 2 ms 8528 KB ok
27 Correct 2 ms 10576 KB ok
28 Correct 2 ms 10576 KB ok
29 Correct 2 ms 10576 KB ok
30 Correct 2 ms 10576 KB ok
31 Correct 2 ms 10576 KB ok
32 Correct 2 ms 10576 KB ok
33 Correct 2 ms 10576 KB ok
34 Correct 2 ms 10744 KB ok
35 Correct 2 ms 10832 KB ok
36 Correct 3 ms 10832 KB ok
37 Correct 3 ms 10832 KB ok
38 Correct 2 ms 10832 KB ok
39 Correct 2 ms 8784 KB ok
40 Correct 2 ms 11000 KB ok
41 Correct 2 ms 10832 KB ok
42 Correct 2 ms 10832 KB ok
43 Correct 3 ms 10832 KB ok
44 Correct 3 ms 10832 KB ok
45 Correct 2 ms 8784 KB ok
46 Correct 2 ms 10832 KB ok
47 Correct 213 ms 46024 KB ok
48 Correct 182 ms 41052 KB ok
49 Correct 139 ms 45388 KB ok
50 Correct 119 ms 43628 KB ok
51 Correct 203 ms 43196 KB ok
52 Correct 65 ms 37704 KB ok
53 Correct 82 ms 36168 KB ok
54 Correct 87 ms 39496 KB ok
55 Correct 93 ms 37712 KB ok
56 Correct 113 ms 40128 KB ok
57 Correct 64 ms 37960 KB ok
58 Correct 59 ms 39496 KB ok
59 Correct 61 ms 42824 KB ok
60 Correct 65 ms 36272 KB ok
61 Correct 66 ms 36168 KB ok
62 Correct 160 ms 37592 KB ok
63 Correct 175 ms 46112 KB ok
64 Correct 193 ms 42496 KB ok
65 Correct 4310 ms 290956 KB ok
66 Correct 2058 ms 297940 KB ok
67 Correct 1568 ms 273324 KB ok
68 Correct 2239 ms 251412 KB ok
69 Correct 2976 ms 266580 KB ok
70 Correct 3558 ms 271728 KB ok
71 Correct 2037 ms 249512 KB ok
72 Correct 1367 ms 247372 KB ok
73 Correct 1683 ms 247152 KB ok
74 Correct 1636 ms 248352 KB ok
75 Correct 1640 ms 247932 KB ok
76 Correct 2108 ms 247988 KB ok
77 Correct 2082 ms 247212 KB ok
78 Correct 1982 ms 260324 KB ok
79 Correct 1429 ms 254124 KB ok
80 Correct 1455 ms 253680 KB ok
81 Correct 1448 ms 250084 KB ok
82 Correct 1723 ms 254200 KB ok
83 Correct 1855 ms 272640 KB ok
84 Correct 1293 ms 248172 KB ok
85 Correct 1250 ms 249556 KB ok
86 Correct 1335 ms 248140 KB ok
87 Correct 1430 ms 248772 KB ok
88 Correct 1247 ms 248760 KB ok
89 Correct 1499 ms 248792 KB ok
90 Correct 1390 ms 247272 KB ok
91 Correct 1438 ms 247132 KB ok
92 Correct 1490 ms 262864 KB ok
93 Correct 1595 ms 259600 KB ok
94 Correct 1431 ms 255928 KB ok
95 Correct 1428 ms 250168 KB ok
96 Correct 1356 ms 251980 KB ok
97 Correct 1402 ms 249496 KB ok
98 Correct 1234 ms 250516 KB ok
99 Correct 3545 ms 296312 KB ok
100 Correct 3051 ms 296516 KB ok
101 Correct 3057 ms 297280 KB ok
102 Correct 3040 ms 300752 KB ok
103 Correct 3526 ms 345832 KB ok
104 Correct 3745 ms 348332 KB ok
105 Correct 3668 ms 345664 KB ok
106 Correct 3702 ms 345692 KB ok
107 Correct 3756 ms 345844 KB ok
108 Correct 1817 ms 253988 KB ok
109 Correct 1866 ms 256796 KB ok