Submission #1038931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038931		hotboy2703	Hamburg Steak (JOI20_hamburg)	C++17	100 / 100	1721 ms	320092 KiB

hamburg

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll INF = 1e18;
const ll MAXN = 2e5+100;
struct rec{
    ll l,r,d,u;
    rec(ll l1= 0,ll r1 = 0,ll d1 = 0,ll u1 = 0):l(l1),r(r1),d(d1),u(u1){}
};
namespace SCC{

    bool res[MAXN*12];
    vector <ll> g1[MAXN*12];
    vector <ll> g2[MAXN*12];
    bool in[MAXN*12];
    ll val[MAXN*12];
    ll n;
    void add(ll x,ll y){
        n = max({n,x|1,y|1});
        g1[x].push_back(y);    
        g2[y].push_back(x);
    }
    void dfs(ll u,vector <ll> g[],vector <ll> &comp){
        in[u] = 1;
        for (auto v:g[u]){
            if (!in[v])dfs(v,g,comp);
        }
        comp.push_back(u);
    }
    void solve(){
        vector <ll> order;
        for (ll i = 0;i <= n;i ++){
            if (!in[i]){
                dfs(i,g1,order);
            }
        }
        memset(in,0,sizeof in);
        reverse(order.begin(),order.end());
        ll cur = 0;
        for (auto x:order){
            if (!in[x]){
                vector <ll> comp;
                dfs(x,g2,comp);
                for (auto y:comp)val[y] = cur;
                cur++;
            }
        }
        for (ll i = 0;i <= n;i ++){
            res[i] = (val[i] > val[i^1]);
        }
    }
}
vector <rec> A;
ll n,k;
ll PTR;
struct line{
    ll l,r,id;
};
vector <line> b[4];
void solve(){
    ll L=0,R=INF,D=0,U=INF;
    for (auto x:A){
        L = max(x.l,L);
        R = min(x.r,R);
        D = max(x.d,D);
        U = min(x.u,U);
    }
    // U < D,R < L
    A.push_back({L,L,U+1,D-1});
    A.push_back({R,R,U+1,D-1});
    A.push_back({R+1,L-1,D,D});
    A.push_back({R+1,L-1,U,U});
    for (auto [l,r,d,u]:A){
        vector <pair <ll,pll> > all;
        if (l <= L && L <= r)all.push_back(MP(0,MP(d,u)));
        if (l <= R && R <= r)all.push_back(MP(1,MP(d,u)));
        if (d <= D && D <= u)all.push_back(MP(2,MP(l,r)));
        if (d <= U && U <= u)all.push_back(MP(3,MP(l,r)));
        if (sz(all) >= 3)continue;
        for (auto x:all){
            b[x.fi].push_back({x.se.fi,x.se.se,PTR++});
        }
        if (sz(all) == 2){
            ll u = PTR-2,v = PTR-1;
            SCC::add(u<<1|1,v<<1);
            SCC::add(v<<1|1,u<<1);
        }
        if (sz(all) == 1){
            ll u = PTR-1;
            SCC::add(u<<1|1,u<<1);
        }
    }
    for (ll i = 0;i < 4;i ++){
        sort(b[i].begin(),b[i].end(),[](line x,line y){return x.r < y.r;});
        vector <ll> ban(sz(b[i]));
        for (ll j = 0;j < sz(b[i]);j ++){
            ban[j] = PTR++;
            SCC::add(ban[j]<<1,b[i][j].id<<1|1);
            if (j)SCC::add(ban[j]<<1,ban[j-1]<<1);
            auto tmp = lower_bound(b[i].begin(),b[i].end(),b[i][j].l,[](line x,ll y){return x.r < y;}) - b[i].begin()-1;;
            if (tmp>=0)SCC::add(b[i][j].id<<1,ban[tmp]<<1);
        }
        sort(b[i].begin(),b[i].end(),[](line x,line y){return x.l > y.l;});
        for (ll j = 0;j < sz(b[i]);j ++){
            ban[j] = PTR++;
            SCC::add(ban[j]<<1,b[i][j].id<<1|1);
            if (j)SCC::add(ban[j]<<1,ban[j-1]<<1);
            auto tmp = lower_bound(b[i].begin(),b[i].end(),b[i][j].r,[](line x,ll y){return x.l > y;}) - b[i].begin()-1;;
            if (tmp>=0)SCC::add(b[i][j].id<<1,ban[tmp]<<1);
        }
    }
    SCC::solve();
    pll ans[4];
    for (ll i = 0;i < 4;i ++){
        ans[i].fi = 0,ans[i].se = INF;
        for (auto j:b[i]){
            if (SCC::res[j.id<<1]){
                ans[i].fi = max(ans[i].fi,j.l);
                ans[i].se = min(ans[i].se,j.r);
            }
        }
    }
    cout<<L<<' '<<ans[0].fi<<'\n';
    cout<<R<<' '<<ans[1].fi<<'\n';
    cout<<ans[2].fi<<' '<<D<<'\n';
    cout<<ans[3].fi<<' '<<U<<'\n';
}
vector <pll> ans;
bool done = 0;
vector <rec> del(vector <rec> a,pll y){
    vector <rec> res;
    for (auto x:a){
        if (x.l <= y.fi && x.r >= y.fi &&
            x.d <= y.se && x.u >= y.se){}
        else res.emplace_back(x);
    }
    return res;
}
void brute(vector <rec> cur,vector <pll> c){
    if (done)return;
    // for (auto x:cur)cout<<x.l<<' '<<x.r<<' '<<x.d<<' '<<x.u<<' ';
    // cout<<sz(c)<<'\n';
    if (sz(c)==k||cur.empty()){
        while (sz(c) < k){c.push_back(MP(0,0));}
        if (cur.empty()){
            for (ll i = 0;i < k;i ++)cout<<c[i].fi<<' '<<c[i].se<<'\n';
            done = 1;
        }
        return;
    }
    ll L=0,R=INF,D=0,U=INF;
    for (auto x:cur){
        L = max(x.l,L);
        R = min(x.r,R);
        D = max(x.d,D);
        U = min(x.u,U);
    }
    {
        auto tmp = MP(L,D);
        c.push_back(tmp);
        brute(del(cur,tmp),c);
        c.pop_back();
    }
    {
        auto tmp = MP(L,U);
        c.push_back(tmp);
        brute(del(cur,tmp),c);
        c.pop_back();
    }
    {
        auto tmp = MP(R,D);
        c.push_back(tmp);
        brute(del(cur,tmp),c);
        c.pop_back();
    }
    {
        auto tmp = MP(R,U);
        c.push_back(tmp);
        brute(del(cur,tmp),c);
        c.pop_back();
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>k;
    A.resize(n);
    for (auto &x:A)cin>>x.l>>x.d>>x.r>>x.u;
    brute(A,ans);
    if (done)return 0;
    solve();
    return 0;
}

• 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