oj.uz

Submission #1113701

# Submission time Handle Problem Language Result Execution time Memory
1113701 2024-11-17T06:59:26 Z lighton Soccer Stadium (IOI23_soccer) C++17
14 / 100
 3876 ms 300248 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[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,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) 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,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 ind = lower_bound(all(rect),Rect{rs, re + 1, nowc, min(nxtc - 1, ce),0,0})-rect.begin();
                    if(ind < sz(rect) && rect[ind] == Rect{rs, re + 1, nowc, min(nxtc - 1, ce)}) {
                        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 ind = lower_bound(all(rect),Rect{rs-1, re, nowc, min(nxtc - 1, ce),0,0})-rect.begin();
                    if(ind < sz(rect) && rect[ind] == Rect{rs-1, re, nowc, min(nxtc - 1, ce)}) {
                        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 6480 KB ok

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4432 KB ok
2 Correct 2 ms 6480 KB ok
3 Correct 2 ms 10576 KB ok
4 Correct 2 ms 8528 KB ok
5 Correct 1 ms 6480 KB ok
6 Correct 2 ms 6480 KB ok
7 Correct 10 ms 11596 KB ok
8 Correct 217 ms 36276 KB ok
9 Correct 3876 ms 300248 KB ok

Subtask #2
8.0 / 8.0

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

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB ok
2 Correct 2 ms 4432 KB ok
3 Correct 2 ms 6480 KB ok
4 Correct 2 ms 4552 KB ok
5 Correct 2 ms 4432 KB ok
6 Correct 2 ms 6480 KB ok
7 Correct 1 ms 6480 KB ok
8 Correct 2 ms 6480 KB ok
9 Correct 2 ms 6480 KB ok
10 Correct 2 ms 6480 KB ok
11 Correct 2 ms 6480 KB ok
12 Correct 1 ms 4432 KB ok
13 Correct 1 ms 4432 KB ok
14 Correct 2 ms 8528 KB ok
15 Correct 2 ms 6480 KB ok
16 Correct 2 ms 6480 KB ok
17 Correct 2 ms 4432 KB ok
18 Correct 1 ms 4432 KB ok
19 Correct 2 ms 4432 KB ok
20 Correct 1 ms 6480 KB ok
21 Incorrect 2 ms 6480 KB wrong
22 Halted 0 ms 0 KB -

Subtask #4
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB ok
2 Correct 2 ms 4432 KB ok
3 Correct 2 ms 6480 KB ok
4 Correct 2 ms 10576 KB ok
5 Correct 2 ms 8528 KB ok
6 Correct 2 ms 4552 KB ok
7 Correct 2 ms 4432 KB ok
8 Correct 2 ms 6480 KB ok
9 Correct 1 ms 6480 KB ok
10 Correct 2 ms 6480 KB ok
11 Correct 2 ms 6480 KB ok
12 Correct 2 ms 6480 KB ok
13 Correct 2 ms 6480 KB ok
14 Correct 1 ms 4432 KB ok
15 Correct 1 ms 4432 KB ok
16 Correct 2 ms 8528 KB ok
17 Correct 2 ms 6480 KB ok
18 Correct 2 ms 6480 KB ok
19 Correct 2 ms 4432 KB ok
20 Correct 1 ms 4432 KB ok
21 Correct 2 ms 4432 KB ok
22 Correct 1 ms 6480 KB ok
23 Incorrect 2 ms 6480 KB wrong
24 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB ok
2 Correct 2 ms 4432 KB ok
3 Correct 2 ms 6480 KB ok
4 Correct 2 ms 10576 KB ok
5 Correct 2 ms 8528 KB ok
6 Correct 2 ms 4552 KB ok
7 Correct 2 ms 4432 KB ok
8 Correct 2 ms 6480 KB ok
9 Correct 1 ms 6480 KB ok
10 Correct 2 ms 6480 KB ok
11 Correct 2 ms 6480 KB ok
12 Correct 2 ms 6480 KB ok
13 Correct 2 ms 6480 KB ok
14 Correct 1 ms 4432 KB ok
15 Correct 1 ms 4432 KB ok
16 Correct 2 ms 8528 KB ok
17 Correct 2 ms 6480 KB ok
18 Correct 2 ms 6480 KB ok
19 Correct 2 ms 4432 KB ok
20 Correct 1 ms 4432 KB ok
21 Correct 2 ms 4432 KB ok
22 Correct 1 ms 6480 KB ok
23 Incorrect 2 ms 6480 KB wrong
24 Halted 0 ms 0 KB -

Subtask #6
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6480 KB ok
2 Correct 2 ms 4432 KB ok
3 Correct 2 ms 6480 KB ok
4 Correct 2 ms 10576 KB ok
5 Correct 2 ms 8528 KB ok
6 Correct 1 ms 6480 KB ok
7 Correct 2 ms 6480 KB ok
8 Correct 10 ms 11596 KB ok
9 Correct 217 ms 36276 KB ok
10 Correct 3876 ms 300248 KB ok
11 Correct 2 ms 4552 KB ok
12 Correct 2 ms 4432 KB ok
13 Correct 2 ms 6480 KB ok
14 Correct 1 ms 6480 KB ok
15 Correct 2 ms 6480 KB ok
16 Correct 2 ms 6480 KB ok
17 Correct 2 ms 6480 KB ok
18 Correct 2 ms 6480 KB ok
19 Correct 1 ms 4432 KB ok
20 Correct 1 ms 4432 KB ok
21 Correct 2 ms 8528 KB ok
22 Correct 2 ms 6480 KB ok
23 Correct 2 ms 6480 KB ok
24 Correct 2 ms 4432 KB ok
25 Correct 1 ms 4432 KB ok
26 Correct 2 ms 4432 KB ok
27 Correct 1 ms 6480 KB ok
28 Incorrect 2 ms 6480 KB wrong
29 Halted 0 ms 0 KB -