oj.uz

답안 #710846

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
710846 2023-03-16T01:25:53 Z Username4132 Izvanzemaljci (COI21_izvanzemaljci) C++14
38 / 100
 89 ms 9704 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], 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){
    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[i].x));
        }
    }
    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-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()+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:82:1: warning: control reaches end of non-void function [-Wreturn-type]
   82 | }
      | ^
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 0 ms 340 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 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 0 ms 340 KB Output is correct
7 Correct 43 ms 9664 KB Output is correct
8 Correct 46 ms 9580 KB Output is correct
9 Correct 41 ms 9700 KB Output is correct
10 Correct 42 ms 9696 KB Output is correct
11 Correct 51 ms 9680 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 0 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 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 57 ms 9672 KB Output is correct
11 Correct 61 ms 9672 KB Output is correct
12 Correct 58 ms 9692 KB Output is correct
13 Correct 63 ms 9692 KB Output is correct
14 Correct 59 ms 9696 KB Output is correct
15 Correct 68 ms 9704 KB Output is correct
16 Correct 69 ms 9684 KB Output is correct
17 Correct 51 ms 8920 KB Output is correct
18 Correct 44 ms 8524 KB Output is correct
19 Correct 50 ms 7896 KB Output is correct
20 Correct 46 ms 8332 KB Output is correct
21 Correct 89 ms 9676 KB Output is correct
22 Correct 61 ms 9692 KB Output is correct
23 Correct 60 ms 9676 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 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 468 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 4 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Incorrect 5 ms 468 KB Integer -2376787775 violates the range [1, 2*10^9]
4 Halted 0 ms 0 KB -