oj.uz

Submission #825815

# Submission time Handle Problem Language Result Execution time Memory
825815 2023-08-15T08:28:55 Z tomruk Sky Walking (IOI19_walk) C++17
33 / 100
 1287 ms 123532 KB 
#include "walk.h"
#include <bits/stdc++.h>
#define N 100005
using namespace std;
map<int,vector<int>> adj[N];
map<int,long long> d[N];
vector<int> vv[N];
vector<int> add[N];
vector<int> del[N];
long long min_distance(vector<int> p, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g){
	int n = p.size();
	int m = l.size();
	vector<pair<int,int>> v;
	for(int i = 0;i<n;i++){
		v.push_back({h[i],i});
		adj[i][0].push_back(i);
	}
	for(int i = 0;i<m;i++){
		vv[r[i]].push_back(i);
		v.push_back({y[i],~i});
		add[r[i]].push_back(i);
		del[l[i]].push_back(i);
	}
	set<pair<int,int>> act;
	for(int i = n-1;i>=0;i--){
		for(auto u:add[i]){
			act.insert({y[u],u});
		}
		// cout << "asdasd" << endl;
		// cout << i << endl;
		// for(auto u:act){
		// 	cout << u.first << " " << u.second << endl;
		// }
		for(auto u:vv[i]){
			// cout << u << endl;
			auto it = act.lower_bound({y[u],u});
			if(next(it) != act.end()){
				adj[i][next(it)->first].push_back(r[next(it)->second]);
				adj[r[next(it)->second]][next(it)->first].push_back(i);
			}
			if(it != act.begin()){
				adj[i][prev(it)->first].push_back(r[prev(it)->second]);
				adj[r[prev(it)->second]][prev(it)->first].push_back(i);
			}
		}
		for(auto u:del[i]){
			act.erase({y[u],u});
		}
	}
	sort(v.rbegin(),v.rend());
	set<int> active;
	for(auto u:v){
		if(u.second < 0){
			u.second = ~u.second;
			auto it = active.lower_bound(max(s,l[u.second]));
			auto it2 = active.lower_bound(min(g,r[u.second]));
			adj[*it][y[u.second]].push_back(*it2);
			adj[*it2][y[u.second]].push_back(*it);
			// while(1){
			// 	auto it2 = it;
			// 	it2++;
			// 	if(it2 == active.end() || *it2 > r[u.second])
			// 		break;
			// 	adj[*it][y[u.second]].push_back(*it2);
			// 	adj[*it2][y[u.second]].push_back(*it);
			// 	it = it2;
			// }
		}
		else{
			active.insert(u.second);
		}
	}
	priority_queue<pair<long long,pair<int,int>>> q;
	d[s][0] = 0;
	q.push({-d[s][0],{s,0}});
	while(q.size()){
		auto tp = q.top();
		q.pop();
		tp.first *= -1;
		int x = tp.second.first;
		int y = tp.second.second;
		if(tp.first != d[x][y])
			continue;
		// cout << x << ' ' << y << endl;
		// cout << tp.first << endl;
		for(auto u:adj[x][y]){
			long long nw = abs(p[x] - p[u]) + tp.first;
			if(d[u].count(y) == 0 || d[u][y] > nw){
				d[u][y] = nw;
				q.push({-d[u][y],{u,y}});
			}
		}
		auto it = adj[x].find(y);
		if(next(it) != adj[x].end()){
			long long nw = abs(y - next(it)->first) + tp.first;
			if(d[x].count(next(it)->first) == 0 || d[x][next(it)->first] > nw){
				d[x][next(it)->first] = nw;
				q.push({-d[x][next(it)->first],{x,next(it)->first}});
			}
		}
		if(it != adj[x].begin()){
			long long nw = abs(y - prev(it)->first) + tp.first;
			if(d[x].count(prev(it)->first) == 0 || d[x][prev(it)->first] > nw){
				d[x][prev(it)->first] = nw;
				q.push({-d[x][prev(it)->first],{x,prev(it)->first}});
			}
		}
	}
	return (d[g].count(0)?d[g][0]:-1);
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 16724 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 95 ms 32868 KB Output is correct
2 Correct 822 ms 88820 KB Output is correct
3 Correct 715 ms 95748 KB Output is correct
4 Correct 927 ms 123048 KB Output is correct
5 Correct 1195 ms 121324 KB Output is correct
6 Correct 1053 ms 115416 KB Output is correct
7 Correct 469 ms 83936 KB Output is correct
8 Correct 321 ms 91912 KB Output is correct
9 Correct 850 ms 108932 KB Output is correct
10 Correct 460 ms 90600 KB Output is correct
11 Correct 32 ms 26424 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 32868 KB Output is correct
2 Correct 822 ms 88820 KB Output is correct
3 Correct 715 ms 95748 KB Output is correct
4 Correct 927 ms 123048 KB Output is correct
5 Correct 1195 ms 121324 KB Output is correct
6 Correct 1053 ms 115416 KB Output is correct
7 Correct 469 ms 83936 KB Output is correct
8 Correct 321 ms 91912 KB Output is correct
9 Correct 850 ms 108932 KB Output is correct
10 Correct 460 ms 90600 KB Output is correct
11 Correct 32 ms 26424 KB Output is correct
12 Correct 765 ms 95464 KB Output is correct
13 Correct 504 ms 91836 KB Output is correct
14 Correct 1145 ms 121132 KB Output is correct
15 Correct 778 ms 111748 KB Output is correct
16 Correct 754 ms 111604 KB Output is correct
17 Correct 833 ms 123532 KB Output is correct
18 Correct 712 ms 111764 KB Output is correct
19 Correct 757 ms 111644 KB Output is correct
20 Correct 438 ms 81536 KB Output is correct
21 Correct 69 ms 37272 KB Output is correct
22 Correct 577 ms 102460 KB Output is correct
23 Correct 522 ms 101200 KB Output is correct
24 Correct 488 ms 94316 KB Output is correct
25 Correct 520 ms 96680 KB Output is correct
26 Correct 423 ms 96244 KB Output is correct
27 Correct 1287 ms 122404 KB Output is correct
28 Correct 440 ms 91248 KB Output is correct
29 Correct 1104 ms 115244 KB Output is correct
30 Correct 476 ms 83808 KB Output is correct
31 Correct 915 ms 108760 KB Output is correct
32 Correct 376 ms 88324 KB Output is correct
33 Correct 512 ms 95176 KB Output is correct
34 Correct 432 ms 94048 KB Output is correct
35 Correct 387 ms 99508 KB Output is correct
36 Correct 362 ms 92040 KB Output is correct
37 Correct 282 ms 82220 KB Output is correct
38 Correct 378 ms 100712 KB Output is correct
39 Correct 449 ms 98248 KB Output is correct
40 Correct 309 ms 95932 KB Output is correct
41 Correct 297 ms 88948 KB Output is correct

Subtask #5
0 / 43.0

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