Submission #917277

#	Time	Username	Problem	Language	Result	Execution time	Memory
917277		hotboy2703	IOI Fever (JOI21_fever)	C++14	100 / 100	1025 ms	175444 KiB

fever

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))

const ll MAXN = 1e5;
pll pnt[MAXN + 100];
map <ll,vector <ll> > mp_row,mp_col,mp_sum,mp_dif;
ll n;
vector <ll> real[MAXN+100][4];
vector <pll> g[MAXN*10+100];
vector <ll> all;
map <ll,ll> row_st,row_en,col_st,col_en,sum_st,sum_en,dif_st,dif_en;
ll dir[MAXN*10+100];
ll dist[MAXN*10+100];
const ll INF = 1e18;

ll iright(ll x){
    if (x==-1)return 0;
    return n+1+x*2;
}
ll ileft(ll x){
    if (x==-1)return 0;
    return n+1+x*2+1;
}

ll f(ll st, ll en, ll val, bool Ox, bool large){
    if (Ox){
        if (large){
            auto sus = lower_bound(all.begin()+st,all.begin()+en,val,[&](ll x, ll y){return pnt[x].fi < y;});
            if (sus != all.begin()+en)return sus-all.begin();
            else return -1;
        }
        else{
            auto sus = upper_bound(all.begin()+st,all.begin()+en,val,[&](ll x, ll y){return x < pnt[y].fi;});
            if (sus != all.begin()+st)return sus-all.begin()-1;
            else return -1;
        }
    }
    else{
        if (large){
            auto sus = lower_bound(all.begin()+st,all.begin()+en,val,[&](ll x, ll y){return pnt[x].se < y;});
            if (sus != all.begin()+en)return sus-all.begin();
            else return -1;
        }
        else{
            auto sus = upper_bound(all.begin()+st,all.begin()+en,val,[&](ll x, ll y){return x < pnt[y].se;});
            if (sus != all.begin()+st)return sus-all.begin()-1;
            else return -1;
        }
    }
}

ll dijkstra(ll sussy){
    priority_queue <pll,vector <pll>, greater <pll> > q;
    for (ll i = 1;i <= n*10+10;i++)dist[i]=INF;

    {
    auto add = [&](ll v,ll dir_v,ll dist_v){
        if (dist_v >= dist[v])return;

        dir[v] = dir_v;
        dist[v] = dist_v;
        q.push({dist_v,v});
    };
    add(1,sussy,0);
    }
    dist[0] = -1;

    while (!q.empty()){
        ll u = q.top().se;
        ll val = q.top().fi;
        q.pop();
        if (val != dist[u])continue;
//        if (u <= n)//cout<<u<<' '<<dist[u]<<' '<<dir[u]<<endl;
//        else{
////            cout<<u<<' '<<all[(u-(n+1))/2]<<' '<<dist[u]<<' '<<dir[u]<<endl;
//        }
        auto add = [&](ll v,ll dir_v,ll dist_v){
            if (dist_v >= dist[v])return;
//            cout<<"EDGE "<<u<<' '<<v<<' '<<dist_v<<endl;
            dir[v] = dir_v;
            dist[v] = dist_v;
            q.push({dist_v,v});
        };
        if (u <= n){
            if (u == 1)dist[u] = 1;
            auto d1 = [&](ll x,ll y){return max(abs(pnt[x].fi-pnt[y].fi),abs(pnt[x].se-pnt[y].se));};
            ll pivot;
            if (dir[u] == 0){
                pivot = f(row_st[pnt[u].se],row_en[pnt[u].se],pnt[u].fi - dist[u],1,0);
                if (pivot != -1)add(ileft(pivot),3,d1(all[pivot],u));
                pivot = f(dif_st[pnt[u].fi-pnt[u].se],dif_en[pnt[u].fi-pnt[u].se],pnt[u].fi - (dist[u]+1)/2,1,0);
                if (pivot != -1)add(ileft(pivot),1,d1(all[pivot],u) * 2);
                pivot = f(sum_st[pnt[u].fi+pnt[u].se],sum_en[pnt[u].fi+pnt[u].se],pnt[u].fi - (dist[u]+1)/2,1,0);
                if (pivot != -1)add(ileft(pivot),2,d1(all[pivot],u) * 2);
            }
            else if (dir[u] == 1){
                pivot = f(col_st[pnt[u].fi],col_en[pnt[u].fi],pnt[u].se + dist[u],0,1);
                if (pivot != -1)add(iright(pivot),2,d1(all[pivot],u));
                pivot = f(dif_st[pnt[u].fi-pnt[u].se],dif_en[pnt[u].fi-pnt[u].se],pnt[u].fi + (dist[u]+1)/2,1,1);
                if (pivot != -1)add(iright(pivot),0,d1(all[pivot],u) * 2);
                pivot = f(sum_st[pnt[u].fi+pnt[u].se],sum_en[pnt[u].fi+pnt[u].se],pnt[u].fi - (dist[u]+1)/2,1,0);
                if (pivot != -1)add(ileft(pivot),3,d1(all[pivot],u) * 2);
            }
            else if (dir[u] == 2){
                pivot = f(col_st[pnt[u].fi],col_en[pnt[u].fi],pnt[u].se - dist[u],0,0);
                if (pivot != -1)add(ileft(pivot),1,d1(all[pivot],u));
                pivot = f(dif_st[pnt[u].fi-pnt[u].se],dif_en[pnt[u].fi-pnt[u].se],pnt[u].fi - (dist[u]+1)/2,1,0);
                if (pivot != -1)add(ileft(pivot),3,d1(all[pivot],u) * 2);
                pivot = f(sum_st[pnt[u].fi+pnt[u].se],sum_en[pnt[u].fi+pnt[u].se],pnt[u].fi + (dist[u]+1)/2,1,1);
                if (pivot != -1)add(iright(pivot),0,d1(all[pivot],u) * 2);
            }
            else{
                pivot = f(row_st[pnt[u].se],row_en[pnt[u].se],pnt[u].fi + dist[u],1,1);
                if (pivot != -1)add(iright(pivot),0,d1(all[pivot],u));
                pivot = f(dif_st[pnt[u].fi-pnt[u].se],dif_en[pnt[u].fi-pnt[u].se],pnt[u].fi + (dist[u]+1)/2,1,1);
                if (pivot != -1)add(iright(pivot),2,d1(all[pivot],u) * 2);
                pivot = f(sum_st[pnt[u].fi+pnt[u].se],sum_en[pnt[u].fi+pnt[u].se],pnt[u].fi + (dist[u]+1)/2,1,1);
                if (pivot != -1)add(iright(pivot),1,d1(all[pivot],u) * 2);
            }
        if (u == 1)dist[u] = 0;
        }
        else{
            for (auto tmp:g[u]){
                ll v = tmp.fi;
                ll w = tmp.se;
                add(v,dir[u],dist[u]+w);
            }
        }
    }
    ll res = 0;
    for (ll i = 1;i <= n;i++)res += dist[i] != INF;
    return res;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    for (ll i = 1;i <= n;i ++)cin>>pnt[i].fi>>pnt[i].se;
    for (ll i = 1;i <= n;i ++){
        mp_col[pnt[i].fi].push_back(i);
        mp_row[pnt[i].se].push_back(i);
        mp_sum[pnt[i].fi+pnt[i].se].push_back(i);
        mp_dif[pnt[i].fi-pnt[i].se].push_back(i);
    }


    for (auto &x:mp_col){
        sort(x.se.begin(),x.se.end(),[&](ll &xx,ll &y){return pnt[xx].se < pnt[y].se;});
    }
    for (auto &x:mp_row){
        sort(x.se.begin(),x.se.end(),[&](ll &xx,ll &y){return pnt[xx].fi < pnt[y].fi;});
    }
    for (auto &x:mp_sum){
        sort(x.se.begin(),x.se.end(),[&](ll &xx,ll &y){return pnt[xx].fi < pnt[y].fi;});
    }
    for (auto &x:mp_dif){
        sort(x.se.begin(),x.se.end(),[&](ll &xx,ll &y){return pnt[xx].fi < pnt[y].fi;});
    }


    auto f1 = [&](map <ll,vector <ll> > &mp,map<ll,ll> &st, map <ll,ll> &en,ll w){
        auto d1 = [&](ll x,ll y){return max(abs(pnt[x].fi-pnt[y].fi),abs(pnt[x].se-pnt[y].se));};
        for (auto x:mp){
            st[x.fi] = sz(all);
            auto &tmp = x.se;
            for (ll j = 0;j < sz(tmp);j ++){
                if (j + 1 < sz(tmp))g[iright(sz(all))].push_back({iright(sz(all)+1),w * d1(tmp[j],tmp[j+1])});
                if (j - 1 >= 0)g[ileft(sz(all))].push_back({ileft(sz(all) - 1),w * d1(tmp[j],tmp[j-1])});
                g[iright(sz(all))].push_back({tmp[j],0});
                g[ileft(sz(all))].push_back({tmp[j],0});
                all.push_back(tmp[j]);
            }
            en[x.fi] = sz(all);
        }
    };
    f1(mp_col,col_st,col_en,1);
    f1(mp_row,row_st,row_en,1);
    f1(mp_sum,sum_st,sum_en,2);
    f1(mp_dif,dif_st,dif_en,2);
//    for (auto x:all){
//        cout<<x<<' ';
//    }
//    cout<<'\n';
//    cout<<dijkstra(3)<<'\n';
    cout<<max({dijkstra(0),dijkstra(1),dijkstra(2),dijkstra(3)});
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 32 / 32
• Subtask 7: 31 / 31