Submission #932349

#	Time	Username	Problem	Language	Result	Execution time	Memory
932349		salmon	Sky Walking (IOI19_walk)	C++14	33 / 100	607 ms	268024 KiB

walk

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

long long int inf = 1e18;

struct node{
    int s, e, m;
    int fleb;
    long long int v;
    node *l,*r;

    node(int S, int E, int fleba){
        s = S;
        e = E;
        fleb = fleba;
        m = (s + e)/2;

        v = inf;

        l = NULL;
        r = NULL;
    }

    void update(int i, long long int k){
        if(s == e){
            v = min(k + s * fleb,v);
            if(k == inf) v = inf;
            return;
        }

        if(l == NULL){
            l = new node(s,m,fleb);
            r = new node(m + 1,e,fleb);
        }

        if(i <= m){
            l -> update(i,k);
        }
        else{
            r -> update(i,k);
        }

        v = min(l -> v, r -> v);
    }

    long long int query(int S, int E){
        if(S <= s && e <= E){
            return v;
        }

        long long int V = inf;

        if(l == NULL) return inf;

        if(S <= m){
            V = min(V,l -> query(S,E));
        }
        if(m < E){
            V = min(V,r -> query(S,E));
        }

        return V;
    }
}*root,*froot;

vector<int> re[100100];
vector<int> er[100100];

long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {

    int N = x.size();

    int M = l.size();

    for(int i = 0; i < M; i++){
        re[l[i]].push_back(i);
        er[r[i]].push_back(i);
    }

    root = new node(0,1'000'000'000,1);
    froot = new node(0,1'000'000'000,-1);

    for(int j : re[0]){
        root -> update(y[j],y[j]);
        froot -> update(y[j],y[j]);
    }

    for(int i = 1; i < N; i++){
        set<int> oobless;
        set<int> ahbah;
        set<int> ah;

        for(int j : re[i]){
            oobless.insert(y[j]);
        }

        for(int j : er[i]){
            if(oobless.find(y[j]) != oobless.end()){
                ah.insert(j);
            }
        }

        oobless.clear();

        for(int j : er[i]){
            oobless.insert(y[j]);
        }

        for(int j : re[i]){
            if(oobless.find(y[j]) != oobless.end()){
                ahbah.insert(j);
            }
        }


        for(int j : re[i]){
            if(ahbah.find(j) != ahbah.end()) continue;

            long long int num = min(root -> query(y[j],1'000'000'000) - y[j], froot -> query(0,y[j]) + y[j]);
            if(num == inf) continue;
            root -> update(y[j],num);
            froot -> update(y[j],num);
        }


        if(i != N - 1){
            for(int j : er[i]){
                if(ah.find(j) != ah.end()) continue;

                root -> update(y[j],inf);
                froot -> update(y[j],inf);
            }
        }
    }


    if(root -> query(0,1'000'000'000) == inf) return -1;

	return root -> query(0,1'000'000'000) + x[N - 1] - x[0];
}

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