Submission #1189576

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189576		alexdd	Sky Walking (IOI19_walk)	C++20	0 / 100	28 ms	20924 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace  std;
#define int long long

const int INF = 1e18;

int n;
vector<int32_t> h;
vector<pair<int,int>> aint[400005];
void build(int nod, int st, int dr)
{
    for(int i=st;i<=dr;i++)
        aint[nod].push_back({h[i],i});
    sort(aint[nod].begin(),aint[nod].end());
    reverse(aint[nod].begin(),aint[nod].end());
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    build(nod*2,st,mij);
    build(nod*2+1,mij+1,dr);
}
pair<int,int> qry(int nod, int st, int dr, int le, int ri, int lim)
{
    if(le>ri)
        return {-1,-1};
    if(le==st && dr==ri)
    {
        return aint[nod][0];
    }
    int mij=(st+dr)/2;
    return max(qry(nod*2,st,mij,le,min(mij,ri),lim), qry(nod*2+1,mij+1,dr,max(mij+1,le),ri,lim));
}

vector<int> incep[100005],termina[100005];

set<pair<int,int>> s;
map<int,int> cnt;
void baga(int x)
{
    auto it = s.lower_bound({x,0});
    if((*it).first == x)
        return;

    int mnm=INF;
    if(it != s.end())
        mnm = min(mnm, (*it).second + abs((*it).first - x));
    if(it != s.begin())
    {
        it--;
        mnm = min(mnm, (*it).second + abs((*it).first - x));
    }
    s.insert({x,mnm});
}
long long min_distance(vector<int32_t> x, vector<int32_t> coph, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t src, int32_t g)
{
    h = coph;
    n = h.size();
    build(1,0,n-1);

    for(int i=0;i<l.size();i++)
    {
        pair<int,int> x = qry(1,0,n-1,l[i]+1,r[i]-1,y[i]);
        if(x.first > max(h[l[i]], h[r[i]]) && 0)
        {
            //assert(0);
            incep[l[i]].push_back(y[i]);
            termina[x.second].push_back(y[i]);
            incep[x.second].push_back(y[i]);
            termina[r[i]].push_back(y[i]);
        }
        else
        {
            incep[l[i]].push_back(y[i]);
            termina[r[i]].push_back(y[i]);
        }
    }
    assert(n!=1);
    s.insert({0,0});
    cnt[0]++;
    termina[0].push_back(0);
    incep[n-1].push_back(0);
    for(int i=0;i<n;i++)
    {
        for(int x:incep[i])
        {
            cnt[x]++;
            baga(x);
        }
        for(int x:termina[i])
        {
            auto it = s.lower_bound({x,0});

            assert(it != s.end() && (*it).first == x);
            
            cnt[x]--;
            if(cnt[x]==0)
                s.erase(it);
        }
    }
    assert(!s.empty());
    auto cop = *s.begin();
    if(cop.second == INF)
        return -1;
    return cop.second + x[n-1] - x[0];
}

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