oj.uz

Submission #1038926

# Submission time Handle Problem Language Result Execution time Memory
1038926 2024-07-30T09:27:34 Z hotboy2703 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 251 ms 167552 KB 
#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[res[i]] > val[res[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.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 115536 KB Output is correct
2 Correct 31 ms 115332 KB Output is correct
3 Correct 31 ms 115548 KB Output is correct
4 Correct 31 ms 115544 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 115528 KB Output is correct
2 Correct 31 ms 115480 KB Output is correct
3 Correct 36 ms 115592 KB Output is correct
4 Correct 33 ms 115544 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 115536 KB Output is correct
2 Correct 32 ms 115660 KB Output is correct
3 Correct 32 ms 115548 KB Output is correct
4 Correct 31 ms 115536 KB Output is correct
5 Correct 37 ms 115668 KB Output is correct
6 Correct 31 ms 115548 KB Output is correct
7 Correct 30 ms 115632 KB Output is correct
8 Correct 32 ms 115796 KB Output is correct
9 Correct 30 ms 115544 KB Output is correct
10 Correct 32 ms 115804 KB Output is correct
11 Correct 32 ms 115776 KB Output is correct
12 Correct 31 ms 115544 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 115548 KB Output is correct
2 Correct 32 ms 115544 KB Output is correct
3 Correct 31 ms 115548 KB Output is correct
4 Correct 32 ms 115544 KB Output is correct
5 Correct 32 ms 115548 KB Output is correct
6 Correct 31 ms 115548 KB Output is correct
7 Correct 32 ms 115544 KB Output is correct
8 Correct 33 ms 116012 KB Output is correct
9 Correct 31 ms 115780 KB Output is correct
10 Correct 33 ms 115908 KB Output is correct
11 Correct 35 ms 115972 KB Output is correct
12 Correct 36 ms 115704 KB Output is correct
13 Correct 33 ms 115548 KB Output is correct
14 Incorrect 35 ms 118188 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 115536 KB Output is correct
2 Correct 31 ms 115332 KB Output is correct
3 Correct 31 ms 115548 KB Output is correct
4 Correct 31 ms 115544 KB Output is correct
5 Correct 92 ms 134068 KB Output is correct
6 Correct 88 ms 134120 KB Output is correct
7 Correct 93 ms 134120 KB Output is correct
8 Correct 89 ms 134120 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 115528 KB Output is correct
2 Correct 31 ms 115480 KB Output is correct
3 Correct 36 ms 115592 KB Output is correct
4 Correct 33 ms 115544 KB Output is correct
5 Correct 106 ms 147188 KB Output is correct
6 Correct 112 ms 147140 KB Output is correct
7 Correct 105 ms 141252 KB Output is correct
8 Correct 112 ms 155588 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 115536 KB Output is correct
2 Correct 32 ms 115660 KB Output is correct
3 Correct 32 ms 115548 KB Output is correct
4 Correct 31 ms 115536 KB Output is correct
5 Correct 37 ms 115668 KB Output is correct
6 Correct 31 ms 115548 KB Output is correct
7 Correct 30 ms 115632 KB Output is correct
8 Correct 32 ms 115796 KB Output is correct
9 Correct 30 ms 115544 KB Output is correct
10 Correct 32 ms 115804 KB Output is correct
11 Correct 32 ms 115776 KB Output is correct
12 Correct 31 ms 115544 KB Output is correct
13 Correct 121 ms 144012 KB Output is correct
14 Correct 143 ms 144596 KB Output is correct
15 Correct 115 ms 145484 KB Output is correct
16 Correct 105 ms 140124 KB Output is correct
17 Correct 112 ms 144812 KB Output is correct
18 Correct 96 ms 138712 KB Output is correct
19 Correct 120 ms 148124 KB Output is correct
20 Correct 251 ms 167552 KB Output is correct
21 Correct 118 ms 149392 KB Output is correct
22 Correct 138 ms 166832 KB Output is correct
23 Correct 184 ms 166216 KB Output is correct
24 Correct 152 ms 165632 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 115548 KB Output is correct
2 Correct 32 ms 115544 KB Output is correct
3 Correct 31 ms 115548 KB Output is correct
4 Correct 32 ms 115544 KB Output is correct
5 Correct 32 ms 115548 KB Output is correct
6 Correct 31 ms 115548 KB Output is correct
7 Correct 32 ms 115544 KB Output is correct
8 Correct 33 ms 116012 KB Output is correct
9 Correct 31 ms 115780 KB Output is correct
10 Correct 33 ms 115908 KB Output is correct
11 Correct 35 ms 115972 KB Output is correct
12 Correct 36 ms 115704 KB Output is correct
13 Correct 33 ms 115548 KB Output is correct
14 Incorrect 35 ms 118188 KB Output isn't correct
15 Halted 0 ms 0 KB -