oj.uz

Submission #883150

# Submission time Handle Problem Language Result Execution time Memory
883150 2023-12-04T16:21:34 Z abcvuitunggio Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 139 ms 14948 KB 
#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(2,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

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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2524 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2520 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2608 KB Output is correct
7 Correct 2 ms 2404 KB Output is correct
8 Correct 1 ms 2520 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2524 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2600 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 3 ms 2684 KB Output is correct
14 Correct 3 ms 2848 KB Output is correct
15 Correct 3 ms 2652 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Incorrect 3 ms 2652 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 65 ms 10100 KB Output is correct
6 Correct 66 ms 10040 KB Output is correct
7 Correct 66 ms 10104 KB Output is correct
8 Correct 65 ms 10192 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 2 ms 2524 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 64 ms 10856 KB Output is correct
6 Correct 72 ms 10700 KB Output is correct
7 Correct 65 ms 10768 KB Output is correct
8 Correct 85 ms 12652 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2520 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2608 KB Output is correct
7 Correct 2 ms 2404 KB Output is correct
8 Correct 1 ms 2520 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Correct 2 ms 2652 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 1 ms 2524 KB Output is correct
13 Correct 74 ms 10912 KB Output is correct
14 Correct 69 ms 10992 KB Output is correct
15 Correct 65 ms 10708 KB Output is correct
16 Correct 66 ms 10724 KB Output is correct
17 Correct 66 ms 11392 KB Output is correct
18 Correct 64 ms 10692 KB Output is correct
19 Correct 67 ms 11468 KB Output is correct
20 Correct 71 ms 12240 KB Output is correct
21 Correct 139 ms 14948 KB Output is correct
22 Correct 92 ms 12960 KB Output is correct
23 Correct 82 ms 13784 KB Output is correct
24 Correct 91 ms 14548 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2600 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 2 ms 2396 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 3 ms 2684 KB Output is correct
14 Correct 3 ms 2848 KB Output is correct
15 Correct 3 ms 2652 KB Output is correct
16 Correct 2 ms 2652 KB Output is correct
17 Incorrect 3 ms 2652 KB Output isn't correct
18 Halted 0 ms 0 KB -