oj.uz

Submission #1113709

# Submission time Handle Problem Language Result Execution time Memory
1113709 2024-11-17T08:00:16 Z lighton Soccer Stadium (IOI23_soccer) C++17
54 / 100
 4500 ms 427020 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,id,dp;
    bool operator<(const Rect &r) const{
        return array<int,5>{cs-ce, re-rs, rs, cs, id} < array<int,5>{r.cs-r.ce, r.re-r.rs, r.rs, 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){
    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>0) {
        if (ud == 1) rect.push_back({row, row + x - 1,s,e,sz(rect),0});
        else rect.push_back({row - x + 1, row,s,e,sz(rect),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) segu[i].update(1,1,N,j,{u[i][j],j});
        dnc(i,0,1,N);
        forf(j,1,N) segd[i].update(1,1,N,j,{d[i][j],j});
        dnc(i,1,1,N);
    }

    sort(all(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(segu[rs].query(1,1,N,cs,ce).fs != 1 || segd[re].query(1,1,N,cs,ce).fs != 1) continue;

        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();

                    if(ind < sz(rect) && rect[ind] == Rect{nrs, nre, nowc, nce}) {
                        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();
                    if(ind < sz(rect) && rect[ind] == Rect{nrs, nre, nowc, nce}) {
                        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:37:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |         int m = s+e>>1;
      |                 ~^~
soccer.cpp: In member function 'std::pair<int, int> Seg::query(int, int, int, int, int)':
soccer.cpp:45:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |         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 2 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 8652 KB ok
6 Correct 2 ms 10576 KB ok
7 Correct 9 ms 24008 KB ok
8 Correct 193 ms 69556 KB ok
9 Correct 3994 ms 427020 KB ok

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 10576 KB ok
6 Correct 2 ms 10752 KB ok
7 Correct 2 ms 10576 KB ok
8 Correct 2 ms 10740 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 2 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 2 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 2 ms 10576 KB ok
7 Correct 2 ms 10752 KB ok
8 Correct 2 ms 10576 KB ok
9 Correct 2 ms 10740 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 2 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 2 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 2 ms 10576 KB ok
9 Correct 2 ms 10752 KB ok
10 Correct 2 ms 10576 KB ok
11 Correct 2 ms 10740 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 2 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 10576 KB ok
30 Correct 2 ms 10832 KB ok
31 Correct 3 ms 10832 KB ok
32 Correct 2 ms 10832 KB ok
33 Correct 3 ms 10832 KB ok
34 Correct 2 ms 10832 KB ok
35 Correct 2 ms 10832 KB ok
36 Correct 3 ms 10832 KB ok
37 Correct 2 ms 10832 KB ok
38 Correct 3 ms 10832 KB ok
39 Correct 2 ms 10832 KB ok
40 Correct 3 ms 8784 KB ok
41 Correct 3 ms 11000 KB ok

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10576 KB ok
2 Correct 2 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 2 ms 10576 KB ok
9 Correct 2 ms 10752 KB ok
10 Correct 2 ms 10576 KB ok
11 Correct 2 ms 10740 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 2 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 10576 KB ok
30 Correct 2 ms 10832 KB ok
31 Correct 3 ms 10832 KB ok
32 Correct 2 ms 10832 KB ok
33 Correct 3 ms 10832 KB ok
34 Correct 2 ms 10832 KB ok
35 Correct 2 ms 10832 KB ok
36 Correct 3 ms 10832 KB ok
37 Correct 2 ms 10832 KB ok
38 Correct 3 ms 10832 KB ok
39 Correct 2 ms 10832 KB ok
40 Correct 3 ms 8784 KB ok
41 Correct 3 ms 11000 KB ok
42 Correct 443 ms 51876 KB ok
43 Correct 408 ms 62112 KB ok
44 Correct 320 ms 61392 KB ok
45 Correct 290 ms 54436 KB ok
46 Correct 401 ms 62472 KB ok
47 Correct 218 ms 61352 KB ok
48 Correct 143 ms 55480 KB ok
49 Correct 152 ms 55984 KB ok
50 Execution timed out 4566 ms 56748 KB Time limit exceeded
51 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10576 KB ok
2 Correct 2 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 8652 KB ok
7 Correct 2 ms 10576 KB ok
8 Correct 9 ms 24008 KB ok
9 Correct 193 ms 69556 KB ok
10 Correct 3994 ms 427020 KB ok
11 Correct 2 ms 8528 KB ok
12 Correct 2 ms 8528 KB ok
13 Correct 2 ms 10576 KB ok
14 Correct 2 ms 10752 KB ok
15 Correct 2 ms 10576 KB ok
16 Correct 2 ms 10740 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 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 10576 KB ok
35 Correct 2 ms 10832 KB ok
36 Correct 3 ms 10832 KB ok
37 Correct 2 ms 10832 KB ok
38 Correct 3 ms 10832 KB ok
39 Correct 2 ms 10832 KB ok
40 Correct 2 ms 10832 KB ok
41 Correct 3 ms 10832 KB ok
42 Correct 2 ms 10832 KB ok
43 Correct 3 ms 10832 KB ok
44 Correct 2 ms 10832 KB ok
45 Correct 3 ms 8784 KB ok
46 Correct 3 ms 11000 KB ok
47 Correct 443 ms 51876 KB ok
48 Correct 408 ms 62112 KB ok
49 Correct 320 ms 61392 KB ok
50 Correct 290 ms 54436 KB ok
51 Correct 401 ms 62472 KB ok
52 Correct 218 ms 61352 KB ok
53 Correct 143 ms 55480 KB ok
54 Correct 152 ms 55984 KB ok
55 Execution timed out 4566 ms 56748 KB Time limit exceeded
56 Halted 0 ms 0 KB -