oj.uz

Submission #737343

# Submission time Handle Problem Language Result Execution time Memory
737343 2023-05-07T05:30:04 Z bobthebuilder Sky Walking (IOI19_walk) C++17
25 / 100
 617 ms 171940 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});
		pts[i].pb({0,i});
	}
	vector<pii> vv;
	sort(ALL(v));
	REP(i,m){
		vv.pb({y[i],i});
	}
	sort(ALL(vv));
	int p=0;
	set<int> ss;
	REP(i,n) ss.insert(i);
	int cur=n;
	for(auto x:vv){
		while(p<n and v[p].f<x.f){
			ss.erase(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);
			auto pv=pts[z].back();
			add(pv.s,cur,x.f-pv.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);
	}
	REP(i,cur) dist[i]=INF64;
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,s});
	dist[s]=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[g]==INF64) dist[g]=-1;
	return dist[g];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94164 KB Output is correct
2 Correct 44 ms 94208 KB Output is correct
3 Correct 44 ms 94204 KB Output is correct
4 Correct 44 ms 94128 KB Output is correct
5 Correct 44 ms 94136 KB Output is correct
6 Correct 44 ms 94160 KB Output is correct
7 Correct 45 ms 94164 KB Output is correct
8 Correct 46 ms 94240 KB Output is correct
9 Correct 46 ms 94216 KB Output is correct
10 Correct 46 ms 94164 KB Output is correct
11 Correct 47 ms 94132 KB Output is correct
12 Correct 55 ms 94148 KB Output is correct
13 Correct 47 ms 94144 KB Output is correct
14 Correct 47 ms 94220 KB Output is correct
15 Correct 48 ms 94120 KB Output is correct
16 Correct 47 ms 94176 KB Output is correct
17 Correct 46 ms 94168 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94152 KB Output is correct
2 Correct 45 ms 94168 KB Output is correct
3 Correct 349 ms 136376 KB Output is correct
4 Incorrect 568 ms 151220 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 137 ms 109324 KB Output is correct
2 Correct 291 ms 140404 KB Output is correct
3 Correct 361 ms 146708 KB Output is correct
4 Correct 564 ms 170624 KB Output is correct
5 Correct 571 ms 171796 KB Output is correct
6 Correct 557 ms 169380 KB Output is correct
7 Correct 351 ms 144828 KB Output is correct
8 Correct 353 ms 137036 KB Output is correct
9 Correct 505 ms 167356 KB Output is correct
10 Correct 304 ms 145888 KB Output is correct
11 Correct 72 ms 101232 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 109324 KB Output is correct
2 Correct 291 ms 140404 KB Output is correct
3 Correct 361 ms 146708 KB Output is correct
4 Correct 564 ms 170624 KB Output is correct
5 Correct 571 ms 171796 KB Output is correct
6 Correct 557 ms 169380 KB Output is correct
7 Correct 351 ms 144828 KB Output is correct
8 Correct 353 ms 137036 KB Output is correct
9 Correct 505 ms 167356 KB Output is correct
10 Correct 304 ms 145888 KB Output is correct
11 Correct 72 ms 101232 KB Output is correct
12 Correct 369 ms 146652 KB Output is correct
13 Correct 406 ms 168996 KB Output is correct
14 Correct 579 ms 171688 KB Output is correct
15 Correct 509 ms 155236 KB Output is correct
16 Correct 552 ms 165796 KB Output is correct
17 Correct 617 ms 171940 KB Output is correct
18 Correct 518 ms 155116 KB Output is correct
19 Correct 550 ms 165700 KB Output is correct
20 Correct 354 ms 143844 KB Output is correct
21 Correct 149 ms 116964 KB Output is correct
22 Correct 382 ms 155076 KB Output is correct
23 Correct 372 ms 152012 KB Output is correct
24 Correct 317 ms 139864 KB Output is correct
25 Correct 375 ms 149644 KB Output is correct
26 Correct 256 ms 129724 KB Output is correct
27 Correct 568 ms 171940 KB Output is correct
28 Correct 430 ms 166076 KB Output is correct
29 Correct 545 ms 168348 KB Output is correct
30 Correct 354 ms 144332 KB Output is correct
31 Correct 504 ms 167424 KB Output is correct
32 Correct 301 ms 139060 KB Output is correct
33 Correct 304 ms 139968 KB Output is correct
34 Correct 276 ms 140564 KB Output is correct
35 Correct 349 ms 142692 KB Output is correct
36 Incorrect 396 ms 137100 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94164 KB Output is correct
2 Correct 44 ms 94208 KB Output is correct
3 Correct 44 ms 94204 KB Output is correct
4 Correct 44 ms 94128 KB Output is correct
5 Correct 44 ms 94136 KB Output is correct
6 Correct 44 ms 94160 KB Output is correct
7 Correct 45 ms 94164 KB Output is correct
8 Correct 46 ms 94240 KB Output is correct
9 Correct 46 ms 94216 KB Output is correct
10 Correct 46 ms 94164 KB Output is correct
11 Correct 47 ms 94132 KB Output is correct
12 Correct 55 ms 94148 KB Output is correct
13 Correct 47 ms 94144 KB Output is correct
14 Correct 47 ms 94220 KB Output is correct
15 Correct 48 ms 94120 KB Output is correct
16 Correct 47 ms 94176 KB Output is correct
17 Correct 46 ms 94168 KB Output is correct
18 Correct 46 ms 94152 KB Output is correct
19 Correct 45 ms 94168 KB Output is correct
20 Correct 349 ms 136376 KB Output is correct
21 Incorrect 568 ms 151220 KB Output isn't correct
22 Halted 0 ms 0 KB -