oj.uz

답안 #1113711

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1113711 2024-11-17T08:07:11 Z lighton 축구 경기장 (IOI23_soccer) C++17
70 / 100
 4500 ms 396472 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, 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) 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,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});
        dnc(i,0,1,N,0);
        forf(j,1,N) segd[i].update(1,1,N,j,{d[i][j],j});
        dnc(i,1,1,N,0);
    }

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10576 KB ok

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8700 KB ok
2 Correct 2 ms 10576 KB ok
3 Correct 2 ms 12624 KB ok
4 Correct 2 ms 10744 KB ok
5 Correct 2 ms 8528 KB ok
6 Correct 2 ms 10576 KB ok
7 Correct 5 ms 23376 KB ok
8 Correct 62 ms 41208 KB ok
9 Correct 1193 ms 241920 KB ok

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8700 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 10576 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10576 KB ok
2 Correct 2 ms 8700 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 10576 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 10576 KB ok
17 Correct 2 ms 8528 KB ok
18 Correct 3 ms 8528 KB ok
19 Correct 2 ms 8528 KB ok
20 Correct 3 ms 10576 KB ok
21 Correct 2 ms 10576 KB ok
22 Correct 2 ms 10576 KB ok
23 Correct 2 ms 10744 KB ok
24 Correct 2 ms 10740 KB ok
25 Correct 2 ms 10576 KB ok
26 Correct 2 ms 10576 KB ok

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10576 KB ok
2 Correct 2 ms 8700 KB ok
3 Correct 2 ms 10576 KB ok
4 Correct 2 ms 12624 KB ok
5 Correct 2 ms 10744 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 10576 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 10576 KB ok
19 Correct 2 ms 8528 KB ok
20 Correct 3 ms 8528 KB ok
21 Correct 2 ms 8528 KB ok
22 Correct 3 ms 10576 KB ok
23 Correct 2 ms 10576 KB ok
24 Correct 2 ms 10576 KB ok
25 Correct 2 ms 10744 KB ok
26 Correct 2 ms 10740 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 3 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 10844 KB ok
35 Correct 2 ms 10832 KB ok
36 Correct 2 ms 10832 KB ok
37 Correct 3 ms 10832 KB ok
38 Correct 3 ms 10832 KB ok
39 Correct 2 ms 10832 KB ok
40 Correct 2 ms 8784 KB ok
41 Correct 2 ms 10832 KB ok

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10576 KB ok
2 Correct 2 ms 8700 KB ok
3 Correct 2 ms 10576 KB ok
4 Correct 2 ms 12624 KB ok
5 Correct 2 ms 10744 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 10576 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 10576 KB ok
19 Correct 2 ms 8528 KB ok
20 Correct 3 ms 8528 KB ok
21 Correct 2 ms 8528 KB ok
22 Correct 3 ms 10576 KB ok
23 Correct 2 ms 10576 KB ok
24 Correct 2 ms 10576 KB ok
25 Correct 2 ms 10744 KB ok
26 Correct 2 ms 10740 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 3 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 10844 KB ok
35 Correct 2 ms 10832 KB ok
36 Correct 2 ms 10832 KB ok
37 Correct 3 ms 10832 KB ok
38 Correct 3 ms 10832 KB ok
39 Correct 2 ms 10832 KB ok
40 Correct 2 ms 8784 KB ok
41 Correct 2 ms 10832 KB ok
42 Correct 341 ms 45368 KB ok
43 Correct 330 ms 49504 KB ok
44 Correct 274 ms 53112 KB ok
45 Correct 234 ms 50352 KB ok
46 Correct 337 ms 51108 KB ok
47 Correct 71 ms 44868 KB ok
48 Correct 100 ms 51480 KB ok
49 Correct 94 ms 53176 KB ok
50 Correct 169 ms 60332 KB ok
51 Correct 158 ms 57520 KB ok
52 Correct 72 ms 49244 KB ok
53 Correct 69 ms 46916 KB ok
54 Correct 76 ms 49088 KB ok
55 Correct 82 ms 51388 KB ok
56 Correct 71 ms 53920 KB ok
57 Correct 220 ms 60868 KB ok
58 Correct 269 ms 58548 KB ok
59 Correct 277 ms 61100 KB ok

Subtask #6
0.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10576 KB ok
2 Correct 2 ms 8700 KB ok
3 Correct 2 ms 10576 KB ok
4 Correct 2 ms 12624 KB ok
5 Correct 2 ms 10744 KB ok
6 Correct 2 ms 8528 KB ok
7 Correct 2 ms 10576 KB ok
8 Correct 5 ms 23376 KB ok
9 Correct 62 ms 41208 KB ok
10 Correct 1193 ms 241920 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 10576 KB ok
15 Correct 2 ms 10576 KB ok
16 Correct 2 ms 10576 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 3 ms 8528 KB ok
26 Correct 2 ms 8528 KB ok
27 Correct 3 ms 10576 KB ok
28 Correct 2 ms 10576 KB ok
29 Correct 2 ms 10576 KB ok
30 Correct 2 ms 10744 KB ok
31 Correct 2 ms 10740 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 3 ms 10832 KB ok
36 Correct 3 ms 10832 KB ok
37 Correct 2 ms 10832 KB ok
38 Correct 2 ms 10832 KB ok
39 Correct 2 ms 10844 KB ok
40 Correct 2 ms 10832 KB ok
41 Correct 2 ms 10832 KB ok
42 Correct 3 ms 10832 KB ok
43 Correct 3 ms 10832 KB ok
44 Correct 2 ms 10832 KB ok
45 Correct 2 ms 8784 KB ok
46 Correct 2 ms 10832 KB ok
47 Correct 341 ms 45368 KB ok
48 Correct 330 ms 49504 KB ok
49 Correct 274 ms 53112 KB ok
50 Correct 234 ms 50352 KB ok
51 Correct 337 ms 51108 KB ok
52 Correct 71 ms 44868 KB ok
53 Correct 100 ms 51480 KB ok
54 Correct 94 ms 53176 KB ok
55 Correct 169 ms 60332 KB ok
56 Correct 158 ms 57520 KB ok
57 Correct 72 ms 49244 KB ok
58 Correct 69 ms 46916 KB ok
59 Correct 76 ms 49088 KB ok
60 Correct 82 ms 51388 KB ok
61 Correct 71 ms 53920 KB ok
62 Correct 220 ms 60868 KB ok
63 Correct 269 ms 58548 KB ok
64 Correct 277 ms 61100 KB ok
65 Execution timed out 4588 ms 396472 KB Time limit exceeded
66 Halted 0 ms 0 KB -