oj.uz

Submission #711392

# Submission time Handle Problem Language Result Execution time Memory
711392 2023-03-16T19:40:56 Z Username4132 Izvanzemaljci (COI21_izvanzemaljci) C++14
100 / 100
 229 ms 16180 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){
        ll 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<=0) 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=rect();
    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 && width<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[i+1]+height));
        }
    }
    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 = cross_checks(side);
    if(ret.valid) return ret;

    ret = horizontal_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:271:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  271 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
izvanzemaljci.cpp:273:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  273 |         int a, b; scanf("%d %d", &a, &b);
      |                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 1 ms 340 KB Output is correct
6 Correct 0 ms 296 KB Output is correct
7 Correct 42 ms 9672 KB Output is correct
8 Correct 40 ms 9656 KB Output is correct
9 Correct 39 ms 9692 KB Output is correct
10 Correct 39 ms 9696 KB Output is correct
11 Correct 42 ms 9680 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 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 352 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 55 ms 9620 KB Output is correct
11 Correct 60 ms 9680 KB Output is correct
12 Correct 56 ms 9788 KB Output is correct
13 Correct 58 ms 9692 KB Output is correct
14 Correct 58 ms 9676 KB Output is correct
15 Correct 56 ms 9684 KB Output is correct
16 Correct 49 ms 9688 KB Output is correct
17 Correct 48 ms 8912 KB Output is correct
18 Correct 42 ms 8592 KB Output is correct
19 Correct 48 ms 7880 KB Output is correct
20 Correct 43 ms 8344 KB Output is correct
21 Correct 61 ms 9656 KB Output is correct
22 Correct 65 ms 9932 KB Output is correct
23 Correct 60 ms 9636 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 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 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 1 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 1 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 300 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 3 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 448 KB Output is correct
24 Correct 3 ms 468 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 4 ms 468 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 3 ms 468 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 202 ms 11484 KB Output is correct
15 Correct 177 ms 12924 KB Output is correct
16 Correct 175 ms 13972 KB Output is correct
17 Correct 182 ms 12640 KB Output is correct
18 Correct 206 ms 12708 KB Output is correct
19 Correct 225 ms 15012 KB Output is correct
20 Correct 222 ms 16180 KB Output is correct
21 Correct 169 ms 12980 KB Output is correct
22 Correct 138 ms 14028 KB Output is correct
23 Correct 153 ms 14588 KB Output is correct
24 Correct 229 ms 15064 KB Output is correct
25 Correct 151 ms 14524 KB Output is correct
26 Correct 201 ms 14612 KB Output is correct