oj.uz

Submission #1051035

# Submission time Handle Problem Language Result Execution time Memory
1051035 2024-08-09T18:36:43 Z Itamar Sky Walking (IOI19_walk) C++14
0 / 100
 171 ms 21508 KB 
using namespace std;
#include<vector>
#include<map>
#include<set>
#define ll long long
#define vll vector<ll>
#define pll pair<ll,ll>
#define pi pair<ll,ll>
#include<cmath>
#define vi vector<int>
#include<algorithm>
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	int n = x.size(), m = l.size();
    if(n==1)return 0;
    vector<vi> in(2e5+2);
    vector<vi> out(2e5+2);
    map<ll,ll> dp;
    multiset<ll> se;
    se.insert(1e18+1);
    se.insert(-1e18-1);
    dp[1e18+1]=1e18;
    dp[-1e18-1]=1e18;
    for(int i = 0; i < m;i++){
        dp[y[i]]=1e18;
        in[l[i]].push_back(y[i]);
        out[r[i]].push_back(y[i]);
    }
    out[0].push_back(0);
    dp[0]=0;
    se.insert(0);
    for(int i = 0; i < n; i++){
        for(ll t : in[i])se.insert(t);
        for(ll t : out[i]){
            if(i == n-1){
                dp[0] = min(dp[0], dp[t]+t);
            }
            se.erase(se.find(t));
        }
        for(ll t : out[i]){
            auto it1 = se.lower_bound(t), it2 = se.upper_bound(t);
            dp[*it1] = min(dp[*it1],dp[t]+abs(*it1-t));
            dp[*it2] = min(dp[*it2],dp[t]+abs(*it2-t));
        }
        for(ll t : out[i])if(se.find(t) == se.end())dp[t] = 1e18;
    }
    
    if(dp[0] == 1e18)return -1;
    return dp[0]+x[n-1]-x[0];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 9820 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 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 11868 KB Output is correct
2 Incorrect 171 ms 21508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 11868 KB Output is correct
2 Incorrect 171 ms 21508 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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