oj.uz

Submission #932307

# Submission time Handle Problem Language Result Execution time Memory
932307 2024-02-23T07:52:41 Z salmon Sky Walking (IOI19_walk) C++14
0 / 100
 54 ms 7416 KB 
#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 < S){
            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> ah;

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

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


        for(int j : re[i]){
            if(ah.find(j) != ah.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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 7416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4952 KB Output isn't correct
2 Halted 0 ms 0 KB -