Submission #883155

#	Time	Username	Problem	Language	Result	Execution time	Memory
883155		abcvuitunggio	Hamburg Steak (JOI20_hamburg)	C++17	100 / 100	458 ms	16400 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;
const int INF=2e9;
int n,k,c[200001][4],mn=INF,mx,mn2=INF,mx2,x,y,mask[200001];
vector <pair <int, int>> res;
vector <int> v,ve[16];
vector <pair <int, int>> type[16];
bool check(vector <int> v, int k){
    if (v.empty()){
        while (k--)
            cout << 1 << ' ' << 1 << '\n';
        return true;
    }
    if (!k)
        return false;
    int a[2]={INF,0},b[2]={INF,0};
    for (int i:v){
        a[0]=min(a[0],c[i][2]);
        a[1]=max(a[1],c[i][0]);
        b[0]=min(b[0],c[i][3]);
        b[1]=max(b[1],c[i][1]);
    }
    for (int i=0;i<2;i++)
        for (int j=0;j<2;j++){
            vector <int> v2;
            for (int k:v)
                if (c[k][0]>a[i]||c[k][2]<a[i]||c[k][1]>b[j]||c[k][3]<b[j])
                    v2.push_back(k);
            if (check(v2,k-1)){
                cout << a[i] << ' ' << b[j] << '\n';
                return true;
            }
        }
    return false;
}
void strain(int idx, int a, int b, int sign=1, int dir=1){
    x=a,y=b;
    sort(ve[idx].begin(),ve[idx].end(),[](int i, int j){
            return make_pair(c[i][x],c[i][y])<make_pair(c[j][x],c[j][y]);
        });
    int mx=-INF;
    for (int i:ve[idx]){
        if (dir){
            while (!type[idx].empty()&&c[i][y]*sign<type[idx].back().second*sign)
                type[idx].pop_back();
            type[idx].push_back({c[i][x],c[i][y]});
        }
        else if (type[idx].empty()||c[i][y]*sign>type[idx].back().second*sign)
            type[idx].push_back({c[i][x],c[i][y]});
    }
}
void update(int i, int p, int &x){
    if (type[i].empty())
        return;
    int tmp=upper_bound(type[i].begin(),type[i].end(),make_pair(p,INF))-type[i].begin();
    if (tmp<type[i].size())
        x=min(x,type[i][tmp].second);
}
int f(int mask, int pos, int pos2=-INF){
    int res=(type[mask].empty()?INF:type[mask][0].second);
    update(6,pos2,res);
    if (!type[mask|1].empty()){
        if (mask==4){
            int tmp=lower_bound(type[5].begin(),type[5].end(),make_pair(pos,0))-type[5].begin()-1;
            if (tmp>=0)
                res=min(res,type[5][tmp].second);
        }
        else
            update(3,pos,res);
    }
    return res;
}
pair <int, int> calc(int x, int y){
    int l=INF,r=INF;
    update(12,x,r);
    update(10,y,l);
    return {(l==INF?0:l),r};
}
void check(int pos, int i){
    if (mask[i]%2==0||(!type[1].empty()&&(pos<type[1].back().first||pos>type[1][0].second)))
        return;
    int l=0,r=INF;
    if (!type[8].empty()){
        l=type[8].back().first;
        r=type[8][0].second;
    }
    if (!type[9].empty()){
        if (pos<=type[9][0].second){
            int tmp=upper_bound(type[9].begin(),type[9].end(),make_pair(pos,INF))-type[9].begin();
            if (tmp<type[9].size()){
                l=max(l,type[9].back().first);
                r=min(r,type[9][tmp].second);
            }
        }
        else if (pos>=type[9].back().first){
            int lo=0,hi=type[9].size(),kq=-1;
            while (lo<=hi){
                int mid=(lo+hi)>>1;
                if (type[9][mid].second<pos){
                    l=max(l,type[9][mid].first);
                    kq=mid;
                    lo=mid+1;
                }
                else
                    hi=mid-1;
            }
            if (kq!=-1)
                r=min(r,type[9][0].second);
        }
        else{
            l=max(l,type[9].back().first);
            r=min(r,type[9][0].second);
        }
    }
    int pos2=f(4,pos);
    if (type[4].empty()||(!type[4].empty()&&type[4].back().first<=pos2)){
        int pos3=f(2,pos,pos2);
        if (type[2].empty()||(!type[2].empty()&&type[2].back().first<=pos3)){
            if (type[6].empty()||(!type[6].empty()&&type[6].back().first<=pos3)){
                auto [x,y]=calc(pos2,pos3);
                if (max(l,x)<=min(r,y)){
                    cout << mn << ' ' << pos << '\n' << pos2 << ' ' << mn2 << '\n' << pos3 << ' ' << mx2 << '\n' << mx << ' ' << max(l,x);
                    exit(0);
                }
            }
        }
    }
    pos2=f(2,pos);
    if (type[2].empty()||(!type[2].empty()&&type[2].back().first<=pos2)){
        int pos3=f(4,pos,pos2);
        if (type[4].empty()||(!type[4].empty()&&type[4].back().first<=pos3)){
            if (type[6].empty()||(!type[6].empty()&&type[6].back().first<=pos3)){
                auto [x,y]=calc(pos3,pos2);
                if (max(l,x)<=min(r,y)){
                    cout << mn << ' ' << pos << '\n' << pos2 << ' ' << mx2 << '\n' << pos3 << ' ' << mn2 << '\n' << mx << ' ' << max(l,x);
                    exit(0);
                }
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> k;
    for (int i=0;i<n;i++){
        for (int j=0;j<4;j++)
            cin >> c[i][j];
        v.push_back(i);
    }
    if (check(v,k))
        return 0;
    for (int i=0;i<n;i++){
        mn=min(mn,c[i][2]);
        mx=max(mx,c[i][0]);
        mn2=min(mn2,c[i][3]);
        mx2=max(mx2,c[i][1]);
    }
    for (int i=0;i<n;i++){
        mask[i]=(c[i][0]<=mn)+(c[i][3]>=mx2)*2+(c[i][1]<=mn2)*4+(c[i][2]>=mx)*8;
        if (__builtin_popcount(mask[i])<3)
            ve[mask[i]].push_back(i);
    }
    strain(1,1,3);
    strain(2,0,2);
    strain(4,0,2);
    strain(8,1,3);
    strain(3,1,2);
    strain(5,3,2,-1,0);
    strain(10,0,1,-1);
    strain(12,0,3);
    strain(9,1,3);
    strain(6,0,2);
    for (int i=0;i<n;i++){
        check(c[i][1],i);
        check(c[i][3],i);
    }
}

Compilation message (stderr)

hamburg.cpp: In function 'void strain(int, int, int, int, int)':
hamburg.cpp:41:9: warning: unused variable 'mx' [-Wunused-variable]
   41 |     int mx=-INF;
      |         ^~
hamburg.cpp: In function 'void update(int, int, int&)':
hamburg.cpp:56:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     if (tmp<type[i].size())
      |         ~~~^~~~~~~~~~~~~~~
hamburg.cpp: In function 'void check(int, int)':
hamburg.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |             if (tmp<type[9].size()){
      |                 ~~~^~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 79 / 79