Submission #1193217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193217		hengliao	Hamburg Steak (JOI20_hamburg)	C++20	2 / 100	3096 ms	54048 KiB

hamburg

#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
#define pb push_back

typedef long long ll;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll mxN=8e5+5;
const ll dumb=10;

struct segtree{
    vll tree;
    ll treelen;

    void init(ll siz){
        treelen=siz+1;
        while(__builtin_popcount(treelen)!=1) treelen++;
        tree=vll(2*treelen, 0);
    }

    void update1(ll idx, ll low, ll high, ll qlow, ll qhigh, ll val){
        if(low>=qlow && high<=qhigh){
            tree[idx]+=val;
            return;
        }
        if(low>qhigh || high<qlow){
            return;
        }
        ll mid=(low+high)/2;
        update1(2*idx, low, mid, qlow, qhigh, val);
        update1(2*idx+1, mid+1, high, qlow, qhigh, val);
    }

    void update(ll qlow, ll qhigh, ll val){
        update1(1, 0, treelen-1, qlow, qhigh, val);
    }

    ll getval(ll idx){
        ll re=0;
        ll tar=idx+treelen;
        while(tar>0){
            re+=tree[tar];
            tar/=2;
        }
        return re;
    }
};

ll n, k;
ll x1[mxN], x2[mxN], yy[mxN], y2[mxN];
vll con;
vll in[mxN], out[mxN];

segtree seg;

ll rand(ll a, ll b){
    return a+rng()%(b-a+1);
}

ll id(ll tar){
    return lower_bound(con.begin(), con.end(), tar)-con.begin();
}

vll rem(vll v, pll p){
    vll re;
    for(auto &idx:v){
        if(p.F>=x1[idx] && p.F<=x2[idx] && p.S>=yy[idx] && p.S<=y2[idx]){
            continue;
        }
        re.pb(idx);
    }
    return re;
}

bool f(vll v, ll x){
    if(v.empty()){
        if(x-1>=1) f(v, x-1);
        cout<<"1 1\n";
        return true;
    }
    if(x==1){
        array<ll, 4> tep={x1[v[0]], yy[v[0]], x2[v[0]], y2[v[0]]};
        for(ll i=1;i<(ll) v.size();i++){
            tep[0]=max(tep[0], x1[v[i]]);
            tep[1]=max(tep[1], yy[v[i]]);
            tep[2]=min(tep[2], x2[v[i]]);
            tep[3]=min(tep[3], y2[v[i]]);
        }
        if(tep[0]<=tep[2] && tep[1]<=tep[3]){
            cout<<tep[0]<<' '<<tep[1]<<'\n';
            return true;
        }
        return false;
    }
    ll sz=v.size();
    ll th=sz/x;
    vector<pll> p;
    for(auto &idx:v){
        in[id(x1[idx])].pb(idx);
        out[id(x2[idx])].pb(idx);
        p.pb({x1[idx], yy[idx]});
        p.pb({x1[idx], y2[idx]});
        p.pb({x2[idx], yy[idx]});
        p.pb({x2[idx], y2[idx]});
    } 
    sort(p.begin(), p.end());
    seg.init((ll) con.size());
    ll pt=0;
    vector<pll> good;
    // for(ll i=0;i<(ll) con.size();i++){
    //     for(auto &idx:in[i]){
    //         seg.update(id(yy[idx]), id(y2[idx]), 1);
    //     }
    //     while(pt<(ll) p.size() && p[pt].F<=con[i]){
    //         if(seg.getval(id(p[pt].S))>=th){
    //             good.pb(p[pt]);
    //         }
    //         pt++;
    //     }
    //     for(auto &idx:out[i]){
    //         seg.update(id(yy[idx]), id(y2[idx]), -1);
    //     }
    // }  
    // for(auto &idx:v){
    //     in[id(x1[idx])].clear();
    //     out[id(x2[idx])].clear();
    // } 
    good=p;
    if(good.empty()){
        return false;
    }
    for(ll rep=0;rep<(ll) good.size();rep++){
        ll tep=rep;
        pll cur=good[tep];
        vll re=rem(v, cur);
        if(f(re, x-1)){
            cout<<cur.F<<' '<<cur.S<<'\n';
            return true;
        }
    }
    return false;
}

void solve(){
    cin>>n>>k;
    for(ll i=0;i<n;i++){
        cin>>x1[i]>>yy[i]>>x2[i]>>y2[i];
        con.pb(x1[i]);
        con.pb(yy[i]);
        con.pb(x2[i]);
        con.pb(y2[i]);
    }
    sort(con.begin(), con.end());
    con.erase(unique(con.begin(), con.end()), con.end());
    vll v;
    for(ll i=0;i<n;i++){
        v.pb(i);
    }
    bool tep=f(v, k);
    assert(tep);
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  solve();

  return 0;
}

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