oj.uz

Submission #737928

# Submission time Handle Problem Language Result Execution time Memory
737928 2023-05-08T01:38:10 Z bobthebuilder Sky Walking (IOI19_walk) C++17
33 / 100
 619 ms 165640 KB 
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define lowb(x) (x&(-x))
#define ALL(_x) _x.begin(),_x.end()
#define pii pair<ll,int>
#define f first
#define s second
#define SORT_UNIQUE(x) sort(ALL(x)),x.erase(unique(ALL(x)),x.end())
#define ll long long
const ll INF64=4e18;
const int maxn=2e6+5;
vector<pii> gr[maxn];
void add(int a,int b,int w){
	gr[a].pb({b,w}),gr[b].pb({a,w});
}
vector<pii> pts[maxn];
ll dist[maxn];
long long min_distance(std::vector<int> xx, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	int n=sz(xx),m=sz(l);
	vector<pii> v;
	REP(i,n){
		v.pb({h[i],i});
	}
	sort(ALL(v)),reverse(ALL(v));;
	for(int zz:{s,g}){
		m=sz(l);
		vector<pii> vv;
		REP(i,m){
			vv.pb({y[i],i});
		}
		set<int> ss;
		sort(ALL(vv));
		reverse(ALL(vv));
		int p=0;
		for(auto x:vv){
			if(r[x.s]<=zz or l[x.s]>=zz) continue;
			while(p<n and v[p].f>=x.f){
				ss.insert(v[p].s);
				++p;
			}
			int a=(*prev(ss.upper_bound(zz))),b=(*ss.lower_bound(zz));
			l.pb(l[x.s]),r.pb(a),y.pb(x.f);
			l.pb(a),r.pb(b),y.pb(x.f);
			l.pb(b),r.pb(r[x.s]),y.pb(x.f);
		}
	}
	vector<pii> vv;
	REP(i,m){
		vv.pb({y[i],i});
	}
	sort(ALL(vv));
	reverse(ALL(vv));
	int cur=0;
	set<int> ss;
	int p=0;
	for(auto x:vv){
		while(p<n and v[p].f>=x.f){
			ss.insert(v[p].s);
			++p;
		}
		int a=l[x.s],b=r[x.s];
		ss.insert(a),ss.insert(b);
		auto it=ss.lower_bound(a);
		int pp=-1;
		vector<int> del;
		while(it!=ss.end() and (*it)<=b){
			int z=(*it);
			if(sz(pts[z])){
			auto pv=pts[z].back();
			add(pv.s,cur,pv.f-x.f);
			}
			pts[z].pb({x.f,cur});
			if(pp!=-1) add(cur-1,cur,xx[z]-xx[pp]);
			pp=z;
			++cur;
			if(z!=a and z!=b){
				del.pb(z);
			}
			++it;
		}
		for(int x:del) ss.erase(x);
	}
	for(int z:{s,g}){
		if(!sz(pts[z])){
			return -1;
		}
		auto pv=pts[z].back();
		add(pv.s,cur++,pv.f);
	}
	REP(i,cur) dist[i]=INF64;
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,cur-2});
	dist[cur-2]=0;
	while(sz(pq)){
		int z=pq.top().s;
		if(pq.top().f>dist[z]){
			pq.pop();
			continue;
		}
		pq.pop();
		for(auto x:gr[z]){
			if(dist[x.f]>dist[z]+x.s){
				dist[x.f]=dist[z]+x.s;
				pq.push({dist[x.f],x.f});
			}
		}
	}
	if(dist[cur-1]==INF64) dist[cur-1]=-1;
	return dist[cur-1];
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94164 KB Output is correct
2 Correct 45 ms 94224 KB Output is correct
3 Correct 46 ms 94184 KB Output is correct
4 Correct 46 ms 94192 KB Output is correct
5 Incorrect 46 ms 94148 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94160 KB Output is correct
2 Correct 45 ms 94112 KB Output is correct
3 Correct 372 ms 137632 KB Output is correct
4 Incorrect 618 ms 149044 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 109440 KB Output is correct
2 Correct 309 ms 142260 KB Output is correct
3 Correct 382 ms 146132 KB Output is correct
4 Correct 610 ms 163608 KB Output is correct
5 Correct 606 ms 165112 KB Output is correct
6 Correct 586 ms 162132 KB Output is correct
7 Correct 369 ms 137216 KB Output is correct
8 Correct 330 ms 126320 KB Output is correct
9 Correct 549 ms 160604 KB Output is correct
10 Correct 316 ms 141916 KB Output is correct
11 Correct 68 ms 98992 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 109440 KB Output is correct
2 Correct 309 ms 142260 KB Output is correct
3 Correct 382 ms 146132 KB Output is correct
4 Correct 610 ms 163608 KB Output is correct
5 Correct 606 ms 165112 KB Output is correct
6 Correct 586 ms 162132 KB Output is correct
7 Correct 369 ms 137216 KB Output is correct
8 Correct 330 ms 126320 KB Output is correct
9 Correct 549 ms 160604 KB Output is correct
10 Correct 316 ms 141916 KB Output is correct
11 Correct 68 ms 98992 KB Output is correct
12 Correct 388 ms 145988 KB Output is correct
13 Correct 419 ms 157732 KB Output is correct
14 Correct 588 ms 164480 KB Output is correct
15 Correct 503 ms 147632 KB Output is correct
16 Correct 577 ms 156180 KB Output is correct
17 Correct 619 ms 165640 KB Output is correct
18 Correct 501 ms 147708 KB Output is correct
19 Correct 431 ms 151488 KB Output is correct
20 Correct 382 ms 136676 KB Output is correct
21 Correct 135 ms 108424 KB Output is correct
22 Correct 358 ms 148240 KB Output is correct
23 Correct 378 ms 145692 KB Output is correct
24 Correct 318 ms 133104 KB Output is correct
25 Correct 373 ms 142912 KB Output is correct
26 Correct 259 ms 123308 KB Output is correct
27 Correct 579 ms 164672 KB Output is correct
28 Correct 470 ms 156608 KB Output is correct
29 Correct 590 ms 161748 KB Output is correct
30 Correct 394 ms 137300 KB Output is correct
31 Correct 535 ms 159936 KB Output is correct
32 Correct 295 ms 133672 KB Output is correct
33 Correct 310 ms 133316 KB Output is correct
34 Correct 275 ms 135416 KB Output is correct
35 Correct 325 ms 135860 KB Output is correct
36 Correct 342 ms 130428 KB Output is correct
37 Correct 295 ms 125180 KB Output is correct
38 Correct 315 ms 125464 KB Output is correct
39 Correct 249 ms 129736 KB Output is correct
40 Correct 274 ms 125832 KB Output is correct
41 Correct 302 ms 125576 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 94164 KB Output is correct
2 Correct 45 ms 94224 KB Output is correct
3 Correct 46 ms 94184 KB Output is correct
4 Correct 46 ms 94192 KB Output is correct
5 Incorrect 46 ms 94148 KB Output isn't correct
6 Halted 0 ms 0 KB -