oj.uz

Submission #1038925

# Submission time Handle Problem Language Result Execution time Memory
1038925 2024-07-30T09:26:03 Z hotboy2703 Hamburg Steak (JOI20_hamburg) C++17
15 / 100
 232 ms 175328 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,D+1,U-1});
    A.push_back({R,R,D+1,U-1});
    A.push_back({L+1,R-1,D,D});
    A.push_back({L+1,R-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 27 ms 115544 KB Output is correct
2 Correct 27 ms 115540 KB Output is correct
3 Correct 26 ms 115544 KB Output is correct
4 Correct 28 ms 115536 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 115544 KB Output is correct
2 Correct 29 ms 115548 KB Output is correct
3 Correct 27 ms 115516 KB Output is correct
4 Correct 29 ms 115676 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 115536 KB Output is correct
2 Correct 29 ms 115544 KB Output is correct
3 Correct 28 ms 115748 KB Output is correct
4 Correct 27 ms 115548 KB Output is correct
5 Correct 27 ms 115544 KB Output is correct
6 Correct 27 ms 115744 KB Output is correct
7 Correct 28 ms 115788 KB Output is correct
8 Correct 29 ms 115916 KB Output is correct
9 Correct 27 ms 115804 KB Output is correct
10 Correct 30 ms 115804 KB Output is correct
11 Correct 28 ms 115804 KB Output is correct
12 Correct 29 ms 115800 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 115544 KB Output is correct
2 Correct 28 ms 115548 KB Output is correct
3 Correct 28 ms 115548 KB Output is correct
4 Correct 30 ms 115536 KB Output is correct
5 Correct 28 ms 115800 KB Output is correct
6 Correct 28 ms 115548 KB Output is correct
7 Correct 27 ms 115796 KB Output is correct
8 Correct 31 ms 116080 KB Output is correct
9 Correct 28 ms 115796 KB Output is correct
10 Correct 29 ms 115924 KB Output is correct
11 Correct 31 ms 116060 KB Output is correct
12 Correct 29 ms 115780 KB Output is correct
13 Correct 28 ms 115804 KB Output is correct
14 Incorrect 33 ms 118200 KB Integer parameter [name=y_1] equals to 0, violates the range [1, 10^9]
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 115544 KB Output is correct
2 Correct 27 ms 115540 KB Output is correct
3 Correct 26 ms 115544 KB Output is correct
4 Correct 28 ms 115536 KB Output is correct
5 Correct 107 ms 141804 KB Output is correct
6 Correct 89 ms 141832 KB Output is correct
7 Correct 88 ms 141836 KB Output is correct
8 Correct 90 ms 141800 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 115544 KB Output is correct
2 Correct 29 ms 115548 KB Output is correct
3 Correct 27 ms 115516 KB Output is correct
4 Correct 29 ms 115676 KB Output is correct
5 Correct 104 ms 154944 KB Output is correct
6 Correct 108 ms 154820 KB Output is correct
7 Correct 103 ms 149056 KB Output is correct
8 Correct 109 ms 163456 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 115536 KB Output is correct
2 Correct 29 ms 115544 KB Output is correct
3 Correct 28 ms 115748 KB Output is correct
4 Correct 27 ms 115548 KB Output is correct
5 Correct 27 ms 115544 KB Output is correct
6 Correct 27 ms 115744 KB Output is correct
7 Correct 28 ms 115788 KB Output is correct
8 Correct 29 ms 115916 KB Output is correct
9 Correct 27 ms 115804 KB Output is correct
10 Correct 30 ms 115804 KB Output is correct
11 Correct 28 ms 115804 KB Output is correct
12 Correct 29 ms 115800 KB Output is correct
13 Correct 112 ms 151808 KB Output is correct
14 Correct 107 ms 152216 KB Output is correct
15 Correct 101 ms 153168 KB Output is correct
16 Correct 103 ms 147864 KB Output is correct
17 Correct 113 ms 152496 KB Output is correct
18 Correct 91 ms 146324 KB Output is correct
19 Correct 118 ms 155820 KB Output is correct
20 Correct 232 ms 175328 KB Output is correct
21 Correct 122 ms 156940 KB Output is correct
22 Correct 142 ms 174460 KB Output is correct
23 Correct 171 ms 173844 KB Output is correct
24 Correct 156 ms 173272 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 115544 KB Output is correct
2 Correct 28 ms 115548 KB Output is correct
3 Correct 28 ms 115548 KB Output is correct
4 Correct 30 ms 115536 KB Output is correct
5 Correct 28 ms 115800 KB Output is correct
6 Correct 28 ms 115548 KB Output is correct
7 Correct 27 ms 115796 KB Output is correct
8 Correct 31 ms 116080 KB Output is correct
9 Correct 28 ms 115796 KB Output is correct
10 Correct 29 ms 115924 KB Output is correct
11 Correct 31 ms 116060 KB Output is correct
12 Correct 29 ms 115780 KB Output is correct
13 Correct 28 ms 115804 KB Output is correct
14 Incorrect 33 ms 118200 KB Integer parameter [name=y_1] equals to 0, violates the range [1, 10^9]
15 Halted 0 ms 0 KB -