Submission #1067644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067644		jerzyk	Sky Walking (IOI19_walk)	C++17	0 / 100	192 ms	110764 KiB

walk

#include <bits/stdc++.h>
#include "walk.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
const int NN = 1<<20;
int tab[NN], hei[NN];
int drz[2 * N], drz2[2 * N];

int cnt = 0;
pair<int, int> co[NN];
vector<pair<int, ll>> ed[NN];
ll dis[NN];
pair<pair<int, int>, int> wal[NN];
bool vis[NN];

vector<int> poi[NN];
vector<int> sky[NN];


void DoDrz(int n)
{
    for(int i = 1; i <= n; ++i)
        drz[i + N] = hei[i];
    for(int i = 1; i <= n; ++i)
        drz2[i + N] = 1;
    for(int i = N - 1; i >= 1; --i)
        drz[i] = max(drz[i * 2], drz[i * 2 + 1]);
    for(int i = N - 1; i >= 1; --i)
        drz2[i] = drz2[i * 2] + drz2[i * 2 + 1];
}

int Find(int a, int b, int x, int r)
{
    a += N - 1; b += N + 1;
    int a1 = 0, a2 = 0, b1 = 0, b2 = 0;
    while(a / 2 != b / 2)
    {
        if(a % 2 == 0 && drz[a + 1] >= x)
        {
            if(a1 == 0)
                a1 = a + 1;
            a2 = a + 1;
        }
        if(b % 2 == 1 && drz[b - 1] >= x)
        {
            if(b1 == 0)
                b1 = b - 1;

            b2 = b - 1;
        }
        a /= 2; b /= 2;
    }
    if(r == 0)
        a = a1;
    if(a == 0)
        a = b2;
    if(r == 1)
        a = b1;
    if(a == 0)
        a = a2;
    while(a < N)
    {
        a = a * 2 + r;
        if(drz[a] < x) a ^= 1;
    }
    return a - N;
}

bool C(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b)
{
    return (make_pair(a.nd, a.st) < make_pair(b.nd, b.st));
}

void Clr(int v, int a, int b, int pz, int kz, int id)
{
    if(drz2[v] <= 0 || a > kz || b < pz) return;
    if(v > N)
    {
        v -= N;
        //cerr << "clr: " << v << " " << id << "\n";
        if(hei[v] >= wal[id].nd)
            sky[v].pb(id);
        --drz2[v + N];
        return;
    }
    Clr(v * 2, a, (a + b) / 2, pz, kz, id);
    Clr(v * 2 + 1, (a + b) / 2 + 1, b, pz, kz, id);
    drz2[v] = drz2[v * 2] + drz2[v * 2 + 1];
}

inline ll D(int i, int j)
{
    ll d1 = max(co[i].st - co[j].st, co[j].st - co[i].st);
    ll d2 = max(co[i].nd - co[j].nd, co[j].nd - co[i].nd);
    return d1 + d2;
}

inline void A(int x, int y)
{
    ll d = D(x, y);
    ed[x].pb(make_pair(y, d)); ed[y].pb(make_pair(x, d));
}

void SanInput(int n, int &k, int u, int v)
{
    int dod = 0;
    sort(wal + 1, wal + 1 + k, C);
    for(int i = 1; i <= k; ++i)
    {
        //cerr << "skypath: " << i << " " << wal[i].st.st - 1 << " " << wal[i].st.nd - 1 << " " << wal[i].nd << "\n";
        vector<int> cur = {wal[i].st.st, wal[i].st.nd}, hl;
        if(wal[i].st.st < u && wal[i].st.nd > u)
        {
            int v1 = Find(1, u, wal[i].nd, 1), v2 = Find(u, n, wal[i].nd, 0);
            cur.pb(v1); cur.pb(v2);
        }
        if(wal[i].st.st < v && wal[i].st.nd > v)
        {
            int v1 = Find(1, v, wal[i].nd, 1), v2 = Find(v, n, wal[i].nd, 0);
            cur.pb(v1); cur.pb(v2);
        }
        sort(cur.begin(), cur.end());

        for(int j = 0; j < (int)cur.size(); ++j)
            if(j == 0 || cur[j] != cur[j - 1]) hl.pb(cur[j]);
        cur = hl;
        wal[i].st.nd = cur[1];
        Clr(1, 0, N - 1, wal[i].st.st, wal[i].st.nd, i);

        sky[cur[0]].pb(i);
        sky[cur[1]].pb(i);

        for(int j = 1; j < (int)cur.size() - 1; ++j)
        {
            ++dod; 
            wal[k + dod] = make_pair(make_pair(cur[j], cur[j + 1]), wal[i].nd);
            Clr(1, 0, N - 1, wal[k + dod].st.st, wal[k + dod].st.nd, i);

            sky[cur[j]].pb(k + dod);
            sky[cur[j + 1]].pb(k + dod);
        }

        //for(int j = 1; j < (int)cur.size() - 1; ++j)
        //{
            //cerr << cur[j] - 1 << " ";
        //}
        //cerr << "\n";
    }
    k += dod;
    cnt = n;
    for(int i = 1; i <= n; ++i)
    {
        vector<int> hlp;
        for(int j = 0; j < (int)sky[i].size(); ++j)
            if(j == 0 || sky[i][j] != sky[i][j - 1]) hlp.pb(sky[i][j]);
        sky[i] = hlp;
        co[i] = make_pair(tab[i], 0);
        int pr = i;
        //cerr << "Sky: " << i << " " << "\n";
        for(int j = 0; j < (int)sky[i].size(); ++j)
        {
            if(j != 0) pr = cnt;
            if(j == 0 || wal[sky[i][j]].nd != wal[sky[i][j - 1]].nd)
            {++cnt; co[cnt] = make_pair(tab[i], wal[sky[i][j]].nd); A(cnt, pr);}
            poi[sky[i][j]].pb(cnt);
            //cerr << sky[i][j] << " ";
        }
        //cerr << "\n";
    }
    for(int i = 1; i <= k; ++i)
        for(int j = 1; j < (int)poi[i].size(); ++j)
            A(poi[i][j - 1], poi[i][j]);
}

void Dijkstra(int s)
{
    int n = cnt;
    priority_queue<pair<ll, int>> q;
    for(int i = 1; i <= n; ++i) dis[i] = I;
    dis[s] = 0LL;
    q.push(make_pair(0LL, s));
    while((int)q.size() > 0)
    {
        int v = q.top().nd; q.pop();
        if(vis[v]) continue;
        vis[v] = true;
        //cerr << "Dijkstra: " << v << " " << co[v].st << " " << co[v].nd << " " << dis[v] << "\n";
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            //cout << "ed: " << ed[v][i].st << " " << ed[v][i].nd << "\n";
            ll d = dis[v] + ed[v][i].nd;
            if(d < dis[ed[v][i].st])
            {
                dis[ed[v][i].st] = d;
                q.push(make_pair(-d, ed[v][i].st));
            }
        }
    }
}

long long min_distance(vector<int> _x, vector<int> _h, vector<int> _l, vector<int> _r, vector<int> _y, int _s, int _g)
{
    int u = _s + 1, v = _g + 1;
    int n = _x.size(), k = _l.size();
    for(int i = 1; i <= n; ++i)
        {tab[i] = _x[i - 1]; hei[i] = _h[i - 1]; ++cnt;}
    for(int i = 1; i <= k; ++i)
        wal[i] = make_pair(make_pair(_l[i - 1] + 1, _r[i - 1] + 1), _y[i - 1]);
    DoDrz(n);
    SanInput(n, k, u, v);
    Dijkstra(u);
    if(dis[v] == I) return -1;
    return dis[v];
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43