oj.uz

Submission #592775

# Submission time Handle Problem Language Result Execution time Memory
592775 2022-07-09T15:08:32 Z Lucpp Sky Walking (IOI19_walk) C++17
15 / 100
 175 ms 16160 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() || mp.begin()->first > H[n-1]) 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 22 ms 3340 KB Output is correct
2 Correct 86 ms 5108 KB Output is correct
3 Correct 88 ms 5784 KB Output is correct
4 Correct 131 ms 10440 KB Output is correct
5 Correct 175 ms 16160 KB Output is correct
6 Correct 126 ms 12752 KB Output is correct
7 Correct 57 ms 7632 KB Output is correct
8 Correct 72 ms 9664 KB Output is correct
9 Correct 119 ms 13104 KB Output is correct
10 Correct 106 ms 13220 KB Output is correct
11 Correct 11 ms 2260 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3340 KB Output is correct
2 Correct 86 ms 5108 KB Output is correct
3 Correct 88 ms 5784 KB Output is correct
4 Correct 131 ms 10440 KB Output is correct
5 Correct 175 ms 16160 KB Output is correct
6 Correct 126 ms 12752 KB Output is correct
7 Correct 57 ms 7632 KB Output is correct
8 Correct 72 ms 9664 KB Output is correct
9 Correct 119 ms 13104 KB Output is correct
10 Correct 106 ms 13220 KB Output is correct
11 Correct 11 ms 2260 KB Output is correct
12 Correct 89 ms 5896 KB Output is correct
13 Incorrect 112 ms 10372 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 -