oj.uz

Submission #737344

# Submission time Handle Problem Language Result Execution time Memory
737344 2023-05-07T05:32:05 Z bobthebuilder Sky Walking (IOI19_walk) C++17
25 / 100
 864 ms 220592 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;
		}
		if(s==0 and g==n-1) 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 46 ms 94152 KB Output is correct
2 Correct 48 ms 94160 KB Output is correct
3 Correct 54 ms 94204 KB Output is correct
4 Correct 47 ms 94108 KB Output is correct
5 Correct 50 ms 94284 KB Output is correct
6 Correct 46 ms 94180 KB Output is correct
7 Correct 44 ms 94284 KB Output is correct
8 Correct 45 ms 94168 KB Output is correct
9 Correct 46 ms 94192 KB Output is correct
10 Correct 48 ms 94284 KB Output is correct
11 Correct 48 ms 94156 KB Output is correct
12 Correct 45 ms 94192 KB Output is correct
13 Correct 45 ms 94156 KB Output is correct
14 Correct 45 ms 94224 KB Output is correct
15 Correct 48 ms 94148 KB Output is correct
16 Correct 46 ms 94220 KB Output is correct
17 Correct 45 ms 94244 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94208 KB Output is correct
2 Correct 46 ms 94124 KB Output is correct
3 Correct 529 ms 177084 KB Output is correct
4 Correct 746 ms 188884 KB Output is correct
5 Correct 468 ms 174108 KB Output is correct
6 Correct 419 ms 164744 KB Output is correct
7 Correct 456 ms 174012 KB Output is correct
8 Correct 609 ms 198420 KB Output is correct
9 Correct 518 ms 173312 KB Output is correct
10 Correct 864 ms 220592 KB Output is correct
11 Correct 418 ms 141208 KB Output is correct
12 Correct 446 ms 130804 KB Output is correct
13 Incorrect 695 ms 155000 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 109340 KB Output is correct
2 Correct 308 ms 140328 KB Output is correct
3 Correct 393 ms 144684 KB Output is correct
4 Correct 624 ms 166680 KB Output is correct
5 Correct 629 ms 167732 KB Output is correct
6 Correct 565 ms 165292 KB Output is correct
7 Correct 406 ms 141784 KB Output is correct
8 Correct 375 ms 133096 KB Output is correct
9 Correct 494 ms 163464 KB Output is correct
10 Correct 312 ms 142456 KB Output is correct
11 Correct 70 ms 100440 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 109340 KB Output is correct
2 Correct 308 ms 140328 KB Output is correct
3 Correct 393 ms 144684 KB Output is correct
4 Correct 624 ms 166680 KB Output is correct
5 Correct 629 ms 167732 KB Output is correct
6 Correct 565 ms 165292 KB Output is correct
7 Correct 406 ms 141784 KB Output is correct
8 Correct 375 ms 133096 KB Output is correct
9 Correct 494 ms 163464 KB Output is correct
10 Correct 312 ms 142456 KB Output is correct
11 Correct 70 ms 100440 KB Output is correct
12 Correct 422 ms 144636 KB Output is correct
13 Correct 414 ms 164924 KB Output is correct
14 Correct 622 ms 167612 KB Output is correct
15 Correct 562 ms 151296 KB Output is correct
16 Correct 550 ms 161664 KB Output is correct
17 Correct 650 ms 168028 KB Output is correct
18 Correct 550 ms 151300 KB Output is correct
19 Correct 576 ms 161860 KB Output is correct
20 Correct 356 ms 140824 KB Output is correct
21 Correct 157 ms 114992 KB Output is correct
22 Correct 382 ms 151588 KB Output is correct
23 Correct 385 ms 148284 KB Output is correct
24 Correct 322 ms 136096 KB Output is correct
25 Correct 387 ms 145932 KB Output is correct
26 Correct 256 ms 125980 KB Output is correct
27 Correct 597 ms 167984 KB Output is correct
28 Correct 450 ms 162052 KB Output is correct
29 Correct 574 ms 164168 KB Output is correct
30 Correct 373 ms 141320 KB Output is correct
31 Correct 547 ms 163448 KB Output is correct
32 Correct 327 ms 135928 KB Output is correct
33 Correct 311 ms 136628 KB Output is correct
34 Correct 292 ms 137404 KB Output is correct
35 Correct 328 ms 139620 KB Output is correct
36 Incorrect 384 ms 134212 KB Output isn't correct
37 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94152 KB Output is correct
2 Correct 48 ms 94160 KB Output is correct
3 Correct 54 ms 94204 KB Output is correct
4 Correct 47 ms 94108 KB Output is correct
5 Correct 50 ms 94284 KB Output is correct
6 Correct 46 ms 94180 KB Output is correct
7 Correct 44 ms 94284 KB Output is correct
8 Correct 45 ms 94168 KB Output is correct
9 Correct 46 ms 94192 KB Output is correct
10 Correct 48 ms 94284 KB Output is correct
11 Correct 48 ms 94156 KB Output is correct
12 Correct 45 ms 94192 KB Output is correct
13 Correct 45 ms 94156 KB Output is correct
14 Correct 45 ms 94224 KB Output is correct
15 Correct 48 ms 94148 KB Output is correct
16 Correct 46 ms 94220 KB Output is correct
17 Correct 45 ms 94244 KB Output is correct
18 Correct 47 ms 94208 KB Output is correct
19 Correct 46 ms 94124 KB Output is correct
20 Correct 529 ms 177084 KB Output is correct
21 Correct 746 ms 188884 KB Output is correct
22 Correct 468 ms 174108 KB Output is correct
23 Correct 419 ms 164744 KB Output is correct
24 Correct 456 ms 174012 KB Output is correct
25 Correct 609 ms 198420 KB Output is correct
26 Correct 518 ms 173312 KB Output is correct
27 Correct 864 ms 220592 KB Output is correct
28 Correct 418 ms 141208 KB Output is correct
29 Correct 446 ms 130804 KB Output is correct
30 Incorrect 695 ms 155000 KB Output isn't correct
31 Halted 0 ms 0 KB -