oj.uz

Submission #1113705

# Submission time Handle Problem Language Result Execution time Memory
1113705 2024-11-17T07:48:58 Z lighton Soccer Stadium (IOI23_soccer) C++17
48 / 100
 4500 ms 428744 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(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 nrs = re+1 - segu[re+1].query(1,1,N,nowc,nce).fs+1;
                    int ind = lower_bound(all(rect),Rect{nrs, re + 1, nowc, nce,-1,0})-rect.begin();
                    if(ind < sz(rect) && rect[ind] == Rect{nrs, re + 1, 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 nre = rs-1 + segd[rs-1].query(1,1,N,nowc,nce).fs-1;
                    int ind = lower_bound(all(rect),Rect{rs-1, nre, nowc, nce,-1,0})-rect.begin();
                    if(ind < sz(rect) && rect[ind] == Rect{rs-1, 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
0.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 2 ms 8528 KB ok
6 Correct 2 ms 10576 KB ok
7 Correct 11 ms 24008 KB ok
8 Correct 263 ms 54700 KB ok
9 Execution timed out 4566 ms 428744 KB Time limit exceeded
10 Halted 0 ms 0 KB -

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 10576 KB ok
7 Correct 2 ms 10744 KB ok
8 Correct 2 ms 10576 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 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 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 10588 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 10576 KB ok
10 Correct 2 ms 10744 KB ok
11 Correct 2 ms 10576 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 10588 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 2 ms 10832 KB ok
33 Correct 2 ms 10832 KB ok
34 Correct 2 ms 10832 KB ok
35 Correct 2 ms 10832 KB ok
36 Correct 2 ms 10832 KB ok
37 Correct 2 ms 10832 KB ok
38 Correct 2 ms 10832 KB ok
39 Correct 2 ms 10832 KB ok
40 Correct 2 ms 8784 KB ok
41 Correct 3 ms 10832 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 10576 KB ok
10 Correct 2 ms 10744 KB ok
11 Correct 2 ms 10576 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 10588 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 2 ms 10832 KB ok
33 Correct 2 ms 10832 KB ok
34 Correct 2 ms 10832 KB ok
35 Correct 2 ms 10832 KB ok
36 Correct 2 ms 10832 KB ok
37 Correct 2 ms 10832 KB ok
38 Correct 2 ms 10832 KB ok
39 Correct 2 ms 10832 KB ok
40 Correct 2 ms 8784 KB ok
41 Correct 3 ms 10832 KB ok
42 Correct 453 ms 42492 KB ok
43 Correct 389 ms 54536 KB ok
44 Correct 445 ms 51608 KB ok
45 Correct 373 ms 48788 KB ok
46 Correct 524 ms 48020 KB ok
47 Correct 279 ms 50048 KB ok
48 Correct 194 ms 50980 KB ok
49 Correct 213 ms 51636 KB ok
50 Execution timed out 4575 ms 50596 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 2 ms 8528 KB ok
7 Correct 2 ms 10576 KB ok
8 Correct 11 ms 24008 KB ok
9 Correct 263 ms 54700 KB ok
10 Execution timed out 4566 ms 428744 KB Time limit exceeded
11 Halted 0 ms 0 KB -