Submission #916709

#	Time	Username	Problem	Language	Result	Execution time	Memory
916709		Tuanlinh123	IOI Fever (JOI21_fever)	C++17	100 / 100	873 ms	162476 KiB

fever

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

const ll maxn=100005, inf=1e15;
pll dis[maxn*20];
vector <pll> A[maxn*20];
vector <ll> nx, ny, ns, nd;
vector <pll> ho[maxn], ve[maxn], sm[maxn], df[maxn];
vector <ll> pho[maxn], pve[maxn], psm[maxn], pdf[maxn];
vector <ll> sho[maxn], sve[maxn], ssm[maxn], sdf[maxn];
ll crr, x[maxn], y[maxn], poho[maxn], pove[maxn], posm[maxn], podf[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n; cin >> n; crr=n;
    for (ll i=1; i<=n; i++)
    {
        cin >> x[i] >> y[i]; x[i]*=2, y[i]*=2;
        nx.pb(x[i]), ny.pb(y[i]), ns.pb(x[i]+y[i]), nd.pb(x[i]-y[i]);
    }
    auto compr=[&](vector <ll> &a)
    {
        sort(a.begin(), a.end());
        a.resize(unique(a.begin(), a.end())-a.begin());
        return;
    };
    compr(nx), compr(ny), compr(ns), compr(nd);
    for (ll i=1; i<=n; i++)
    {
        ll h=lower_bound(ny.begin(), ny.end(), y[i])-ny.begin()+1;
        ll v=lower_bound(nx.begin(), nx.end(), x[i])-nx.begin()+1;
        ll s=lower_bound(ns.begin(), ns.end(), x[i]+y[i])-ns.begin()+1;
        ll d=lower_bound(nd.begin(), nd.end(), x[i]-y[i])-nd.begin()+1;
        ho[h].pb({x[i], i}), ve[v].pb({y[i], i}), sm[s].pb({x[i], i}), df[d].pb({x[i], i});
        poho[i]=h, pove[i]=v, posm[i]=s, podf[i]=d;
    }
    auto getnodes=[&](vector <pll> &id, vector <ll> &pre, vector <ll> &suf, bool diag)
    {
        sort(id.begin(), id.end());
        pre.resize(id.size()), suf.resize(id.size());
        for (ll i=0; i<id.size(); i++)
        {
            pre[i]=++crr; A[pre[i]].pb({id[i].se, 0});
            if (i) A[pre[i]].pb({pre[i-1], (id[i].fi-id[i-1].fi)/(diag?1:2)});
        }
        for (ll i=(ll)id.size()-1; i>=0; i--)
        {
            suf[i]=++crr; A[suf[i]].pb({id[i].se, 0});
            if (i+1!=id.size()) A[suf[i]].pb({suf[i+1], (id[i+1].fi-id[i].fi)/(diag?1:2)});
        }
    };
    for (ll i=1; i<=ny.size(); i++) getnodes(ho[i], pho[i], sho[i], 0);
    for (ll i=1; i<=nx.size(); i++) getnodes(ve[i], pve[i], sve[i], 0);
    for (ll i=1; i<=ns.size(); i++) getnodes(sm[i], psm[i], ssm[i], 1);
    for (ll i=1; i<=nd.size(); i++) getnodes(df[i], pdf[i], sdf[i], 1);
    auto Try=[&](ll direction)
    {
        for (ll i=1; i<=crr; i++)
            dis[i]={inf, 0};
        priority_queue <pll, vector <pll>, greater<pll>> q;
        auto update=[&](ll v, ll t, ll di)
        {
            if (t<dis[v].fi)
                dis[v]={t, di}, q.push({dis[v].fi, v});
            return;
        };
        auto findpos=[&](vector <pll> &a, ll val, bool up)
        {
            if (!up) return lower_bound(a.begin(), a.end(), mp(val, 0ll))-a.begin();
            return lower_bound(a.begin(), a.end(), mp(val, inf))-a.begin()-1;
        };
        dis[1]={0, direction}; q.push({dis[1].fi, 1});
        while (q.size())
        {
            ll t=q.top().fi, u=q.top().se; q.pop();
            if (t!=dis[u].fi) continue;
            ll di=dis[u].se;
            if (u>n) for (pll child:A[u])
            {
                ll v=child.fi, tv=child.se;
                update(v, t+tv, di);
            }
            else if (di==0)
            {
                ll p=findpos(sm[posm[u]], x[u]-t, 1);
                if (p>=0) update(psm[posm[u]][p], x[u]-sm[posm[u]][p].fi, 1);
                p=findpos(ve[pove[u]], y[u]+t*2, 0);
                if (p<ve[pove[u]].size()) update(sve[pove[u]][p], (ve[pove[u]][p].fi-y[u])/2, 2);
                p=findpos(df[podf[u]], x[u]+t, 0);
                if (p<df[podf[u]].size()) update(sdf[podf[u]][p], df[podf[u]][p].fi-x[u], 3);
            }
            else if (di==1)
            {
                ll p=findpos(df[podf[u]], x[u]+t, 0);
                if (p<df[podf[u]].size()) update(sdf[podf[u]][p], df[podf[u]][p].fi-x[u], 2);
                p=findpos(ho[poho[u]], x[u]+2*t, 0);
                if (p<ho[poho[u]].size()) update(sho[poho[u]][p], (ho[poho[u]][p].fi-x[u])/2, 3);
                p=findpos(sm[posm[u]], x[u]+t, 0);
                if (p<sm[posm[u]].size()) update(ssm[posm[u]][p], sm[posm[u]][p].fi-x[u], 0);
            }
            else if (di==2)
            {
                ll p=findpos(sm[posm[u]], x[u]+t, 0);
                if (p<sm[posm[u]].size()) update(ssm[posm[u]][p], sm[posm[u]][p].fi-x[u], 3);
                p=findpos(ve[pove[u]], y[u]-t*2, 1);
                if (p>=0) update(pve[pove[u]][p], (y[u]-ve[pove[u]][p].fi)/2, 0);
                p=findpos(df[podf[u]], x[u]-t, 1);
                if (p>=0) update(pdf[podf[u]][p], x[u]-df[podf[u]][p].fi, 1);
            }
            else
            {
                ll p=findpos(df[podf[u]], x[u]-t, 1);
                if (p>=0) update(pdf[podf[u]][p], x[u]-df[podf[u]][p].fi, 0);
                p=findpos(ho[poho[u]], x[u]-t*2, 1);
                if (p>=0) update(pho[poho[u]][p], (x[u]-ho[poho[u]][p].fi)/2, 1);
                p=findpos(sm[posm[u]], x[u]-t, 1);
                if (p>=0) update(psm[posm[u]][p], x[u]-sm[posm[u]][p].fi, 2);
            }
        }
        ll cnt=0;
        for (ll i=1; i<=n; i++)
            if (dis[i].fi<inf) cnt++;
        return cnt;
    };
    ll ans=1;
    for (ll i=0; i<4; i++)
        ans=max(ans, Try(i));
    cout << ans << "\n";
}

Compilation message (stderr)

fever.cpp: In lambda function:
fever.cpp:50:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |         for (ll i=0; i<id.size(); i++)
      |                      ~^~~~~~~~~~
fever.cpp:58:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             if (i+1!=id.size()) A[suf[i]].pb({suf[i+1], (id[i+1].fi-id[i].fi)/(diag?1:2)});
      |                 ~~~^~~~~~~~~~~
fever.cpp: In function 'int main()':
fever.cpp:61:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (ll i=1; i<=ny.size(); i++) getnodes(ho[i], pho[i], sho[i], 0);
      |                  ~^~~~~~~~~~~
fever.cpp:62:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (ll i=1; i<=nx.size(); i++) getnodes(ve[i], pve[i], sve[i], 0);
      |                  ~^~~~~~~~~~~
fever.cpp:63:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (ll i=1; i<=ns.size(); i++) getnodes(sm[i], psm[i], ssm[i], 1);
      |                  ~^~~~~~~~~~~
fever.cpp:64:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (ll i=1; i<=nd.size(); i++) getnodes(df[i], pdf[i], sdf[i], 1);
      |                  ~^~~~~~~~~~~
fever.cpp: In lambda function:
fever.cpp:97:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |                 if (p<ve[pove[u]].size()) update(sve[pove[u]][p], (ve[pove[u]][p].fi-y[u])/2, 2);
      |                     ~^~~~~~~~~~~~~~~~~~~
fever.cpp:99:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |                 if (p<df[podf[u]].size()) update(sdf[podf[u]][p], df[podf[u]][p].fi-x[u], 3);
      |                     ~^~~~~~~~~~~~~~~~~~~
fever.cpp:104:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |                 if (p<df[podf[u]].size()) update(sdf[podf[u]][p], df[podf[u]][p].fi-x[u], 2);
      |                     ~^~~~~~~~~~~~~~~~~~~
fever.cpp:106:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |                 if (p<ho[poho[u]].size()) update(sho[poho[u]][p], (ho[poho[u]][p].fi-x[u])/2, 3);
      |                     ~^~~~~~~~~~~~~~~~~~~
fever.cpp:108:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |                 if (p<sm[posm[u]].size()) update(ssm[posm[u]][p], sm[posm[u]][p].fi-x[u], 0);
      |                     ~^~~~~~~~~~~~~~~~~~~
fever.cpp:113:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 if (p<sm[posm[u]].size()) update(ssm[posm[u]][p], sm[posm[u]][p].fi-x[u], 3);
      |                     ~^~~~~~~~~~~~~~~~~~~

• 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