oj.uz

Submission #592761

# Submission time Handle Problem Language Result Execution time Memory
592761 2022-07-09T14:44:07 Z Lucpp Sky Walking (IOI19_walk) C++17
15 / 100
 156 ms 20128 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

ll min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int start, int goal) {
	int n = (int)X.size(), m = (int)L.size();
	vector<vector<pair<int, int>>> todo(n+1);
    for(int i = 0; i < m; i++){
        todo[L[i]].emplace_back(Y[i], 1);
        todo[R[i]+1].emplace_back(Y[i], -1);
    }
    todo[1].emplace_back(0, -1);
    map<int, ll> mp;
    mp[0] = 0;
    set<int> just_added;
	for(int i = 0; i < n; i++){
        for(auto [y, op] : todo[i]){
            if(op == -1 && !just_added.count(y)) mp.erase(y);
        }
        just_added.clear();
        for(auto [y, op] : todo[i]){
            if(op == 1){
                auto it = mp.lower_bound(y);
                ll v = INF;
                if(it != mp.end()) v = min(v, it->second+it->first-y);
                if(it != mp.begin()){
                    it--;
                    v = min(v, it->second+y-it->first);
                }
                mp[y] = v;
                just_added.insert(y);
            }
        }
	}
    if(mp.empty()) return -1;
    return mp.begin()->first+mp.begin()->second+X[n-1]-X[0];
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 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 24 ms 3364 KB Output is correct
2 Correct 90 ms 5112 KB Output is correct
3 Correct 98 ms 7944 KB Output is correct
4 Correct 117 ms 14456 KB Output is correct
5 Correct 156 ms 20128 KB Output is correct
6 Correct 133 ms 16804 KB Output is correct
7 Correct 63 ms 10660 KB Output is correct
8 Correct 83 ms 13612 KB Output is correct
9 Correct 134 ms 17188 KB Output is correct
10 Correct 97 ms 16544 KB Output is correct
11 Correct 10 ms 3004 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 3364 KB Output is correct
2 Correct 90 ms 5112 KB Output is correct
3 Correct 98 ms 7944 KB Output is correct
4 Correct 117 ms 14456 KB Output is correct
5 Correct 156 ms 20128 KB Output is correct
6 Correct 133 ms 16804 KB Output is correct
7 Correct 63 ms 10660 KB Output is correct
8 Correct 83 ms 13612 KB Output is correct
9 Correct 134 ms 17188 KB Output is correct
10 Correct 97 ms 16544 KB Output is correct
11 Correct 10 ms 3004 KB Output is correct
12 Correct 96 ms 7940 KB Output is correct
13 Incorrect 128 ms 14368 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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