oj.uz

Submission #932349

# Submission time Handle Problem Language Result Execution time Memory
932349 2024-02-23T08:35:07 Z salmon Sky Walking (IOI19_walk) C++14
33 / 100
 607 ms 268024 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 < 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.0

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

Subtask #2
0 / 14.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7408 KB Output is correct
2 Correct 607 ms 259964 KB Output is correct
3 Correct 530 ms 217680 KB Output is correct
4 Correct 551 ms 257624 KB Output is correct
5 Correct 570 ms 261636 KB Output is correct
6 Correct 555 ms 268024 KB Output is correct
7 Correct 228 ms 140180 KB Output is correct
8 Correct 431 ms 237804 KB Output is correct
9 Correct 447 ms 255284 KB Output is correct
10 Correct 198 ms 26808 KB Output is correct
11 Correct 9 ms 6748 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 7408 KB Output is correct
2 Correct 607 ms 259964 KB Output is correct
3 Correct 530 ms 217680 KB Output is correct
4 Correct 551 ms 257624 KB Output is correct
5 Correct 570 ms 261636 KB Output is correct
6 Correct 555 ms 268024 KB Output is correct
7 Correct 228 ms 140180 KB Output is correct
8 Correct 431 ms 237804 KB Output is correct
9 Correct 447 ms 255284 KB Output is correct
10 Correct 198 ms 26808 KB Output is correct
11 Correct 9 ms 6748 KB Output is correct
12 Correct 535 ms 241000 KB Output is correct
13 Correct 556 ms 247084 KB Output is correct
14 Correct 549 ms 245664 KB Output is correct
15 Correct 269 ms 109908 KB Output is correct
16 Correct 307 ms 107764 KB Output is correct
17 Correct 283 ms 107860 KB Output is correct
18 Correct 277 ms 110364 KB Output is correct
19 Correct 279 ms 107816 KB Output is correct
20 Correct 252 ms 138064 KB Output is correct
21 Correct 22 ms 12116 KB Output is correct
22 Correct 355 ms 191828 KB Output is correct
23 Correct 343 ms 195156 KB Output is correct
24 Correct 345 ms 211744 KB Output is correct
25 Correct 392 ms 223060 KB Output is correct
26 Correct 379 ms 245072 KB Output is correct
27 Correct 551 ms 247564 KB Output is correct
28 Correct 498 ms 257876 KB Output is correct
29 Correct 504 ms 242372 KB Output is correct
30 Correct 237 ms 140756 KB Output is correct
31 Correct 471 ms 255692 KB Output is correct
32 Correct 147 ms 21580 KB Output is correct
33 Correct 161 ms 22356 KB Output is correct
34 Correct 166 ms 29264 KB Output is correct
35 Correct 204 ms 69968 KB Output is correct
36 Correct 182 ms 62764 KB Output is correct
37 Correct 116 ms 15956 KB Output is correct
38 Correct 142 ms 18256 KB Output is correct
39 Correct 148 ms 37808 KB Output is correct
40 Correct 135 ms 19284 KB Output is correct
41 Correct 116 ms 16468 KB Output is correct

Subtask #5
0 / 43.0

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