oj.uz

답안 #711267

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711267 2023-03-16T12:07:35 Z Username4132 Izvanzemaljci (COI21_izvanzemaljci) C++14
38 / 100
 85 ms 10012 KB 
#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)

struct pt{
    int x, y, ind;
    pt(int X, int Y, int I){
        x=X, y=Y, ind=I;
    }
    pt(){}
};

struct rect{
    int assi;
    ll l, d, r, u;
    rect(ll L, ll D, ll R, ll U, int A=2000000000){
        l=L, d=D, r=R, u=U, assi=A;
    }
    rect(){l=d=r=u=0, assi=-1;}
    void transform(bool a, bool b, bool c){
        int aux;
        if(a) aux=l, l=-r, r=-aux;
        if(b) aux=d, d=-u, u=-aux;
        if(c) swap(l, d), swap(r, u);
    }
};

struct sol{
    bool valid;
    rect re[3];
    sol(){
        valid = false;
    }
    sol(rect R1, rect R2, rect R3){
        re[0]=R1, re[1]=R2, re[2]=R3, valid=true;
    }
    void print(){forn(i, 3) if(re[i].assi!=-1) printf("%lld %lld %lld", re[i].l, re[i].d, re[i].u-re[i].d), printf("\n");}
    void dummySquare(int num){
        int start = 2001000000;
        forn(i, 3){
            num+=(re[i].assi==-1);
            if(re[i].assi==-1 && num>3) re[i]=rect(start, 0, start+1, 1, 0), start+=2;
        }
    }
    void transform(bool a, bool b, bool c){
        forn(i, 3) re[i].transform(a, b, c);
    }
};

const int MAXN=100010, INF=2000000100;
int n, k, ext[MAXN], calc[MAXN];
ll st[2*MAXN], st1[MAXN], st2[MAXN];
bool seen[MAXN];
pt srt[2][2][2][MAXN], varg[MAXN];
rect le[2][2][2], oneans;

auto fstCmp = [](pt a, pt b){
    return a.x<b.x;
};

auto sndCmp = [](pt a, pt b){
    return a.y<b.y;
};

rect cover(pt* arr, int m){
    if(!m) return rect();
    int mn=INF, mx=-INF;
    forn(i, m) mn=min(mn, arr[i].y), mx=max(mx, arr[i].y);
    return rect(arr[0].x, mn, arr[m-1].x, mx);
}

rect push_corner(rect re, int dir, int len){
    switch(dir){
        case 0: return rect(re.l, re.d, re.l+len, re.d+len);
        case 1: return rect(re.r-len, re.d, re.r, re.d+len);
        case 2: return rect(re.l, re.u-len, re.l+len, re.u);
        case 3: return rect(re.r-len, re.u-len, re.r, re.u);
    }
}

rect rightmost(pt* arr, int m, int side){
    int mn=INF, mx=-INF; rect ret;
    forn(i, m){
        mx=max(mx, arr[i].y), mn=min(mn, arr[i].y);
        if(arr[i].x-arr[0].x>side || mx-mn>side) break;
        if(i==m-1 || arr[i+1].x!=arr[i].x) ret = rect(arr[0].x, mn, arr[i].x, mx, i);
    }
    return ret;
}

sol low_high_check(pt* arr, int l, int r, int side){
    
    int high_left = max_element(arr, arr+l, sndCmp)->y;
    int high_center = max_element(arr+l, arr+r, sndCmp)->y;
    int low_center = min_element(arr+l, arr+r, sndCmp)->y;
    int low_right = min_element(arr+r, arr+n, sndCmp)->y;
    if(high_left>high_center || low_center>low_right) return sol();

    ext[l]=low_center, ext[r-1]=high_center;
    dforn(i, l) ext[i]=min(ext[i+1], arr[i].y);
    forsn(i, r, n) ext[i]=max(ext[i-1], arr[i].y);
    dforn(i, l) calc[i]=ext[i+1]-arr[i].x;
    forsn(i, r, n) calc[i]=ext[i-1]-arr[i].x;
    dforn(i, l-1) calc[i]=max(calc[i+1], calc[i]);
    forsn(i, r+1, n) calc[i]=min(calc[i-1], calc[i]);

    int pos=r;
    forn(i, l){
        while(pos<n && (calc[pos]+2>calc[i] || (ext[pos-1]==ext[i+1] && arr[pos].x-arr[i].x==2))) ++pos;
        int width = arr[pos].x - arr[i].x - 2, height = max(ext[pos-1]-ext[i+1], 1);
        if(height<=width && height<=side){
            ll left_edge = max(arr[i].x+1, arr[r-1].x-height);
            int szl = lower_bound(arr, arr+n, pt(left_edge, -INF, 0), fstCmp)-arr;
            int szr = upper_bound(arr, arr+n, pt(left_edge+height, INF, 0), fstCmp)-arr;

            return sol(push_corner(cover(arr, szl), 1, side),
            push_corner(cover(arr+szr, n-szr), 0, side),
            rect(left_edge, ext[i+1], left_edge+height, ext[pos-1]));
        }
    }
    return sol();
}

sol lowest_check(pt* arr, pt* brr, int l, int r, int side){
    if(arr[r-1].x - arr[l].x > side) return sol();
    int pos = find_if(arr, arr+n, [&brr](pt a){
        return a.ind==brr[0].ind;
    }) - arr;
    if(pos<l || pos>=r) return sol();
    int L=pos, R=pos;
    forn(i, n) seen[i]=false;
    forn(i, n){
        seen[brr[i].ind]=true;
        while(L>0 && seen[arr[L-1].ind]) --L;
        while(R<n-1 && seen[arr[R+1].ind]) ++R;
        int height=max(brr[i].x-brr[0].x, 1);

        if(L<=l && R>=r-1 && height<=side && (L==0 || R==n-1 || (height<=arr[R+1].x-arr[L-1].x-2))){
            ll left_edge = max(L==0? -INF : arr[L-1].x+1, arr[r-1].x-height);
            int szl = lower_bound(arr, arr+n, pt(left_edge, -INF, 0), fstCmp)-arr;
            int szr = upper_bound(arr, arr+n, pt(left_edge+height, INF, 0), fstCmp)-arr;
            return sol(push_corner(cover(arr, szl), 1, side),
            push_corner(cover(arr+szr, n-szr), 0, side),
            rect(left_edge, brr[0].x, left_edge+height, brr[0].x + height));
        }
    }
    return sol();
}

sol equal_check(pt* arr, int l, int r, int side){

    int L=0, R=0;
    deque<int> mn, mx;
    forn(i, n) st1[i]=arr[i].x+1, st2[i]=arr[i].x-(ll)side;
    merge(st1, st1+n, st2, st2+n, st);
    mn.push_back(arr[0].y);
    mx.push_back(arr[0].y);
    forn(i, 2*n){
        while(R<n && arr[R+1].x<=st[i]+side){
            ++R;
            while(!mn.empty() && mn.back()>arr[R].y) mn.pop_back();
            while(!mx.empty() && mx.back()<arr[R].y) mx.pop_back();
            mx.push_back(arr[R].y);
            mn.push_back(arr[R].y);
        }
        while(L<n && arr[L].x<st[i]){
            if(!mn.empty() && arr[L].y==mn.front()) mn.pop_front();
            if(!mx.empty() && arr[L].y==mx.front()) mx.pop_front();
            ++L;
        }
        if(L<=l && R>=r-1 && mx.front()-mn.front()<=side){
            ll left_edge = max(arr[L-1].x+1, arr[r-1].x-side);
            return sol(push_corner(cover(arr, L), 1, side),
            push_corner(cover(arr+R+1, n-R-1), 0, side),
            rect(left_edge, mn.front(), left_edge+side, mn.front()+(ll)side));
        }
    }
    return sol();
}

sol check_two(pt* arr, int m, int side){
    rect fst=rightmost(arr, m, side);
    rect snd=rightmost(arr+fst.assi+1, m-fst.assi-1, side);
    if((fst.assi==-1 || snd.assi==-1) && fst.assi!=m-1 && snd.assi!=m-1) return sol();
    if(fst.assi+snd.assi+2==m) return sol(rect(), fst, snd);
    return sol();
}

sol v2_check(pt* arr, pt* brr, int side){
    int m=0;
    rect fst=rightmost(arr, n, side);
    forn(i, n) seen[i]=false;
    forn(i, fst.assi+1) seen[arr[i].ind]=true;
    forn(i, n) if(!seen[brr[i].ind]) varg[m++]=brr[i];
    sol ret = check_two(varg, m, side);
    if(m!=0 && !ret.valid) return sol();
    ret.transform(0, 0, 1);
    ret.re[0]=push_corner(fst, 1, side);
    ret.re[1]=push_corner(ret.re[1], 2, side);
    ret.re[2]=push_corner(ret.re[2], 0, side);

    return ret;
}

sol horizontal_checks(int side){
    
    forn(i, 2){
        sol ret = equal_check(srt[0][0][i], le[0][0][i].assi+1, n-le[1][0][i].assi-1, side);
        if(ret.valid){
            ret.transform(0, 0, i);
            return ret;
        }
    }

    forn(i, 2) forn(j, 2){
        sol ret = lowest_check(srt[0][i][j], srt[i][0][j^1], le[0][i][j].assi+1, n-le[1][i][j].assi-1, side);
        if(ret.valid){
            ret.transform(0, i, j);
            return ret;
        }
        ret = low_high_check(srt[0][i][j], le[0][i][j].assi+1, n-le[1][i][j].assi-1, side);
        if(ret.valid){
            ret.transform(0, i, j);
            return ret;
        }
    }

    return sol();
}

sol cross_checks(int side){
    forn(i, 2) forn(j, 2){
        sol ret = v2_check(srt[i][0][j], srt[0][i][j^1], side);
        if(ret.valid){
            ret.transform(i, 0, j);
            return ret;
        }
    }
    return sol();
}

sol test(int type, int side){
    if(side>=oneans.r-oneans.l) return sol(rect(), rect(), oneans);
    forn(i, 2) forn(j, 2) forn(w, 2) le[i][j][w] = rightmost(srt[i][j][w], n, side);

    forn(i, 2) if(le[0][0][i].assi+le[1][0][i].assi>=n-2){
        sol ret = check_two(srt[0][0][i], n, side);
        ret.re[1]=push_corner(ret.re[1], 1, side);
        ret.re[2]=push_corner(ret.re[2], 0, side);
        ret.transform(0, 0, i);
        return ret;
    }

    if(type==2) return sol();
    
    sol ret = horizontal_checks(side);
    if(ret.valid) return ret;

    ret = cross_checks(side);
    if(ret.valid) return ret;

    return sol();
}


int main(){
    scanf("%d %d", &n, &k);
    forn(i, n){
        int a, b; scanf("%d %d", &a, &b);
        srt[0][0][0][i] = pt(a, b, i);
        srt[0][0][1][i] = pt(b, a, i);
    }

    forn(i, 2) sort(srt[0][0][i], srt[0][0][i]+n, fstCmp);
    forn(i, 2) forn(j, n) srt[0][1][i][j]=pt(srt[0][0][i][j].x, -srt[0][0][i][j].y, srt[0][0][i][j].ind);
    forn(i, 2) forn(j, 2) forn(w, n) srt[1][i][j][w]=pt(-srt[0][i][j][n-1-w].x, srt[0][i][j][n-1-w].y, srt[0][i][j][n-1-w].ind);

    oneans = cover(srt[0][0][0], n);
    oneans = push_corner(oneans, 0, max(max(oneans.r-oneans.l, oneans.u-oneans.d), 1LL));
    if(k==1){
        sol(rect(), rect(), oneans).print();
        return 0;
    }

    int lo=0, hi=INF;
    sol ans;
    while(hi-lo>1){
        int mid = ((hi-lo)>>1)+lo;
        sol partial = test(k, mid);
        if(partial.valid) hi=mid, ans=partial;
        else lo=mid;
    }
    ans.dummySquare(k);
    ans.print();
}

Compilation message

izvanzemaljci.cpp: In function 'rect push_corner(rect, int, int)':
izvanzemaljci.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
   84 | }
      | ^
izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:272:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  272 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
izvanzemaljci.cpp:274:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  274 |         int a, b; scanf("%d %d", &a, &b);
      |                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 44 ms 9968 KB Output is correct
8 Correct 44 ms 9916 KB Output is correct
9 Correct 49 ms 9872 KB Output is correct
10 Correct 47 ms 9864 KB Output is correct
11 Correct 44 ms 9908 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 57 ms 9852 KB Output is correct
11 Correct 67 ms 9940 KB Output is correct
12 Correct 85 ms 9936 KB Output is correct
13 Correct 66 ms 10012 KB Output is correct
14 Correct 60 ms 9940 KB Output is correct
15 Correct 62 ms 9924 KB Output is correct
16 Correct 56 ms 9932 KB Output is correct
17 Correct 55 ms 9064 KB Output is correct
18 Correct 48 ms 8852 KB Output is correct
19 Correct 62 ms 8080 KB Output is correct
20 Correct 52 ms 8608 KB Output is correct
21 Correct 71 ms 9952 KB Output is correct
22 Correct 62 ms 9904 KB Output is correct
23 Correct 71 ms 9932 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 392 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 308 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 312 KB Output is correct
24 Correct 1 ms 312 KB Output is correct
25 Correct 1 ms 304 KB Output is correct
26 Correct 1 ms 340 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 468 KB Output is correct
2 Incorrect 4 ms 448 KB Integer -2392564465 violates the range [1, 2*10^9]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 468 KB Output is correct
2 Correct 5 ms 556 KB Output is correct
3 Incorrect 4 ms 468 KB Integer -2376787775 violates the range [1, 2*10^9]
4 Halted 0 ms 0 KB -