oj.uz

답안 #596715

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
596715 2022-07-15T01:55:27 Z Temmie Sky Walking (IOI19_walk) C++17
0 / 100
 43 ms 5696 KB 
    #include <bits/stdc++.h>
     
    long long min_distance(std::vector <int> a, std::vector <int> h,
    std::vector <int> l, std::vector <int> r, std::vector <int> y,
    int s, int e) {
    	if (e < s) {
    		std::swap(s, e);
    	}
    	int n = a.size();
    	int m = y.size();
    	std::map <int, std::vector <int>> ind_seg_start_here;
    	std::map <int, std::vector <int>> ind_seg_end_here;
    	for (int i = 0; i < m; i++) {
    		ind_seg_start_here[a[l[i]]].push_back(i);
    		ind_seg_end_here[a[r[i]]].push_back(i);
    	}
    	std::map <int, std::map <int, long long>> arrive;
    	std::map <int, int> active;
    	arrive[0][0] = 0;
    	std::set <int> idx;
    	for (int x : a) {
    		idx.insert(x);
    	}
    	for (int i : idx) {
    		for (int x : ind_seg_end_here[i]) {
    			active.erase(y[x]);
    		}
    		for (int x : ind_seg_start_here[i]) {
    			active[y[x]] = x;
    		}
    		for (auto p : arrive[i]) {
    			auto it = active.lower_bound(p.first);
    			if (it != active.end()) {
    				auto itt = arrive[a[r[it->second]]].find(y[it->second]);
    				if (itt == arrive[a[r[it->second]]].end() ||
    				itt->second > p.second + abs(p.first - y[it->second])) {
    					arrive[a[r[it->second]]][y[it->second]] =
    					p.second + abs(p.first - y[it->second]) + (a[r[it->second]] - i);
    				}
    			}
    			it = active.upper_bound(p.first);
    			if (it != active.begin()) {
    				it--;
    				auto itt = arrive[a[r[it->second]]].find(y[it->second]);
    				if (itt == arrive[a[r[it->second]]].end() ||
    				itt->second > p.second + abs(p.first - y[it->second])) {
    					arrive[a[r[it->second]]][y[it->second]] =
    					p.second + abs(p.first - y[it->second]) + (a[r[it->second]] - i);
    				}
    			}
    		}
    	}
    	long long ans = 1LL << 60;
    	for (auto p : arrive[a[n - 1]]) {
    		ans = std::min(ans, p.second + p.first);
    	}
      	if (ans == (1LL << 60)) {
          	return -1;
        }
    	return ans;
    }

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 5696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 5696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -