oj.uz

Submission #1113715

# Submission time Handle Problem Language Result Execution time Memory
1113715 2024-11-17T08:35:16 Z lighton Soccer Stadium (IOI23_soccer) C++17
100 / 100
 4400 ms 425536 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];
struct Seg2{
    int arr[8001];
    void update(int now, int s, int e, int f, 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]);
    }
    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;
        int m = s+e>>1;
        return min(query(now*2,s,m,_l,_r),  query(now*2+1,m+1,e,_l,_r));
    }
} segu2[2001], segd2[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 && segu2[row].query(1,1,N,s,e)==1) rect.push_back({row, row + x - 1,s,e,sz(rect),0});
        else if( ud == 0 && segd2[row].query(1,1,N,s,e)==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(j,1,N) segu2[i].update(1,1,N,j,u[i][j]);
        forf(j,1,N) segd2[i].update(1,1,N,j,d[i][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 + segd2[re+1].query(1,1,N,nowc,nce)-1;
                    int nrs = re+1 - segu2[re+1].query(1,1,N,nowc,nce)+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 - segu2[rs-1].query(1,1,N,nowc,nce)+1;
                    int nre = rs-1 + segd2[rs-1].query(1,1,N,nowc,nce)-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;
      |                 ~^~
soccer.cpp: In member function 'void Seg2::update(int, int, int, int, int)':
soccer.cpp:54:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         int m = s+e>>1;
      |                 ~^~
soccer.cpp: In member function 'int Seg2::query(int, int, int, int, int)':
soccer.cpp:62:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int m = s+e>>1;
      |                 ~^~

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10576 KB ok
2 Correct 2 ms 12760 KB ok
3 Correct 3 ms 16736 KB ok
4 Correct 2 ms 14672 KB ok
5 Correct 2 ms 12624 KB ok
6 Correct 3 ms 12624 KB ok
7 Correct 6 ms 23888 KB ok
8 Correct 86 ms 46604 KB ok
9 Correct 1618 ms 323632 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB ok
2 Correct 2 ms 10576 KB ok
3 Correct 2 ms 12760 KB ok
4 Correct 3 ms 16736 KB ok
5 Correct 2 ms 14672 KB ok
6 Correct 2 ms 10576 KB ok
7 Correct 2 ms 10576 KB ok
8 Correct 3 ms 12636 KB ok
9 Correct 2 ms 12624 KB ok
10 Correct 2 ms 12624 KB ok
11 Correct 2 ms 12624 KB ok
12 Correct 2 ms 12624 KB ok
13 Correct 2 ms 12624 KB ok
14 Correct 2 ms 10576 KB ok
15 Correct 2 ms 10744 KB ok
16 Correct 2 ms 14672 KB ok
17 Correct 2 ms 14672 KB ok
18 Correct 2 ms 14672 KB ok
19 Correct 2 ms 12624 KB ok
20 Correct 2 ms 12624 KB ok
21 Correct 2 ms 12624 KB ok
22 Correct 2 ms 14672 KB ok
23 Correct 2 ms 14672 KB ok
24 Correct 2 ms 14672 KB ok
25 Correct 2 ms 14672 KB ok
26 Correct 2 ms 14672 KB ok
27 Correct 2 ms 14672 KB ok
28 Correct 2 ms 14776 KB ok
29 Correct 2 ms 14672 KB ok
30 Correct 3 ms 14928 KB ok
31 Correct 3 ms 15100 KB ok
32 Correct 3 ms 14940 KB ok
33 Correct 2 ms 14928 KB ok
34 Correct 2 ms 15168 KB ok
35 Correct 2 ms 14928 KB ok
36 Correct 3 ms 14928 KB ok
37 Correct 3 ms 14928 KB ok
38 Correct 3 ms 14928 KB ok
39 Correct 3 ms 14928 KB ok
40 Correct 2 ms 12880 KB ok
41 Correct 3 ms 13052 KB ok

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB ok
2 Correct 2 ms 10576 KB ok
3 Correct 2 ms 12760 KB ok
4 Correct 3 ms 16736 KB ok
5 Correct 2 ms 14672 KB ok
6 Correct 2 ms 10576 KB ok
7 Correct 2 ms 10576 KB ok
8 Correct 3 ms 12636 KB ok
9 Correct 2 ms 12624 KB ok
10 Correct 2 ms 12624 KB ok
11 Correct 2 ms 12624 KB ok
12 Correct 2 ms 12624 KB ok
13 Correct 2 ms 12624 KB ok
14 Correct 2 ms 10576 KB ok
15 Correct 2 ms 10744 KB ok
16 Correct 2 ms 14672 KB ok
17 Correct 2 ms 14672 KB ok
18 Correct 2 ms 14672 KB ok
19 Correct 2 ms 12624 KB ok
20 Correct 2 ms 12624 KB ok
21 Correct 2 ms 12624 KB ok
22 Correct 2 ms 14672 KB ok
23 Correct 2 ms 14672 KB ok
24 Correct 2 ms 14672 KB ok
25 Correct 2 ms 14672 KB ok
26 Correct 2 ms 14672 KB ok
27 Correct 2 ms 14672 KB ok
28 Correct 2 ms 14776 KB ok
29 Correct 2 ms 14672 KB ok
30 Correct 3 ms 14928 KB ok
31 Correct 3 ms 15100 KB ok
32 Correct 3 ms 14940 KB ok
33 Correct 2 ms 14928 KB ok
34 Correct 2 ms 15168 KB ok
35 Correct 2 ms 14928 KB ok
36 Correct 3 ms 14928 KB ok
37 Correct 3 ms 14928 KB ok
38 Correct 3 ms 14928 KB ok
39 Correct 3 ms 14928 KB ok
40 Correct 2 ms 12880 KB ok
41 Correct 3 ms 13052 KB ok
42 Correct 198 ms 47556 KB ok
43 Correct 219 ms 44732 KB ok
44 Correct 148 ms 43076 KB ok
45 Correct 135 ms 45840 KB ok
46 Correct 196 ms 46620 KB ok
47 Correct 87 ms 43464 KB ok
48 Correct 88 ms 45136 KB ok
49 Correct 93 ms 40520 KB ok
50 Correct 101 ms 43336 KB ok
51 Correct 136 ms 49652 KB ok
52 Correct 88 ms 43648 KB ok
53 Correct 84 ms 43848 KB ok
54 Correct 87 ms 44096 KB ok
55 Correct 81 ms 47444 KB ok
56 Correct 89 ms 43848 KB ok
57 Correct 151 ms 44736 KB ok
58 Correct 158 ms 48300 KB ok
59 Correct 172 ms 51292 KB ok

Subtask #6
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14672 KB ok
2 Correct 2 ms 10576 KB ok
3 Correct 2 ms 12760 KB ok
4 Correct 3 ms 16736 KB ok
5 Correct 2 ms 14672 KB ok
6 Correct 2 ms 12624 KB ok
7 Correct 3 ms 12624 KB ok
8 Correct 6 ms 23888 KB ok
9 Correct 86 ms 46604 KB ok
10 Correct 1618 ms 323632 KB ok
11 Correct 2 ms 10576 KB ok
12 Correct 2 ms 10576 KB ok
13 Correct 3 ms 12636 KB ok
14 Correct 2 ms 12624 KB ok
15 Correct 2 ms 12624 KB ok
16 Correct 2 ms 12624 KB ok
17 Correct 2 ms 12624 KB ok
18 Correct 2 ms 12624 KB ok
19 Correct 2 ms 10576 KB ok
20 Correct 2 ms 10744 KB ok
21 Correct 2 ms 14672 KB ok
22 Correct 2 ms 14672 KB ok
23 Correct 2 ms 14672 KB ok
24 Correct 2 ms 12624 KB ok
25 Correct 2 ms 12624 KB ok
26 Correct 2 ms 12624 KB ok
27 Correct 2 ms 14672 KB ok
28 Correct 2 ms 14672 KB ok
29 Correct 2 ms 14672 KB ok
30 Correct 2 ms 14672 KB ok
31 Correct 2 ms 14672 KB ok
32 Correct 2 ms 14672 KB ok
33 Correct 2 ms 14776 KB ok
34 Correct 2 ms 14672 KB ok
35 Correct 3 ms 14928 KB ok
36 Correct 3 ms 15100 KB ok
37 Correct 3 ms 14940 KB ok
38 Correct 2 ms 14928 KB ok
39 Correct 2 ms 15168 KB ok
40 Correct 2 ms 14928 KB ok
41 Correct 3 ms 14928 KB ok
42 Correct 3 ms 14928 KB ok
43 Correct 3 ms 14928 KB ok
44 Correct 3 ms 14928 KB ok
45 Correct 2 ms 12880 KB ok
46 Correct 3 ms 13052 KB ok
47 Correct 198 ms 47556 KB ok
48 Correct 219 ms 44732 KB ok
49 Correct 148 ms 43076 KB ok
50 Correct 135 ms 45840 KB ok
51 Correct 196 ms 46620 KB ok
52 Correct 87 ms 43464 KB ok
53 Correct 88 ms 45136 KB ok
54 Correct 93 ms 40520 KB ok
55 Correct 101 ms 43336 KB ok
56 Correct 136 ms 49652 KB ok
57 Correct 88 ms 43648 KB ok
58 Correct 84 ms 43848 KB ok
59 Correct 87 ms 44096 KB ok
60 Correct 81 ms 47444 KB ok
61 Correct 89 ms 43848 KB ok
62 Correct 151 ms 44736 KB ok
63 Correct 158 ms 48300 KB ok
64 Correct 172 ms 51292 KB ok
65 Correct 4400 ms 376520 KB ok
66 Correct 2480 ms 372932 KB ok
67 Correct 1937 ms 349080 KB ok
68 Correct 2548 ms 326592 KB ok
69 Correct 3182 ms 335908 KB ok
70 Correct 3629 ms 344216 KB ok
71 Correct 2383 ms 321020 KB ok
72 Correct 1791 ms 326252 KB ok
73 Correct 1982 ms 321076 KB ok
74 Correct 2119 ms 325704 KB ok
75 Correct 2086 ms 325664 KB ok
76 Correct 2343 ms 321096 KB ok
77 Correct 2296 ms 326532 KB ok
78 Correct 2247 ms 336784 KB ok
79 Correct 1743 ms 331672 KB ok
80 Correct 1853 ms 324124 KB ok
81 Correct 1910 ms 330688 KB ok
82 Correct 2037 ms 325772 KB ok
83 Correct 2097 ms 346500 KB ok
84 Correct 1744 ms 322356 KB ok
85 Correct 1756 ms 323476 KB ok
86 Correct 1743 ms 325620 KB ok
87 Correct 1847 ms 321844 KB ok
88 Correct 1680 ms 321184 KB ok
89 Correct 1822 ms 319304 KB ok
90 Correct 1772 ms 321096 KB ok
91 Correct 1906 ms 323008 KB ok
92 Correct 1929 ms 339888 KB ok
93 Correct 2020 ms 340168 KB ok
94 Correct 1753 ms 327232 KB ok
95 Correct 1689 ms 325176 KB ok
96 Correct 1741 ms 328084 KB ok
97 Correct 1670 ms 323484 KB ok
98 Correct 1655 ms 323712 KB ok
99 Correct 3495 ms 376660 KB ok
100 Correct 3026 ms 371300 KB ok
101 Correct 3223 ms 372944 KB ok
102 Correct 3103 ms 374604 KB ok
103 Correct 3500 ms 419000 KB ok
104 Correct 3492 ms 425536 KB ok
105 Correct 3713 ms 421564 KB ok
106 Correct 3592 ms 418204 KB ok
107 Correct 3637 ms 424892 KB ok
108 Correct 2290 ms 336240 KB ok
109 Correct 2330 ms 335548 KB ok