oj.uz

Submission #737335

# Submission time Handle Problem Language Result Execution time Memory
737335 2023-05-07T05:02:15 Z bobthebuilder Sky Walking (IOI19_walk) C++17
24 / 100
 857 ms 608104 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(ss.find(v[p].s));
			++p;
		}
		int a=l[x.s],b=r[x.s];
		auto it=ss.lower_bound(a);
		int pp=-1;
		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;
			++it;
		}
	}
	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 50 ms 94284 KB Output is correct
2 Correct 45 ms 94112 KB Output is correct
3 Correct 48 ms 94156 KB Output is correct
4 Correct 50 ms 94220 KB Output is correct
5 Correct 44 ms 94216 KB Output is correct
6 Correct 45 ms 94232 KB Output is correct
7 Correct 46 ms 94236 KB Output is correct
8 Correct 47 ms 94280 KB Output is correct
9 Correct 45 ms 94136 KB Output is correct
10 Correct 48 ms 94300 KB Output is correct
11 Correct 47 ms 94152 KB Output is correct
12 Correct 47 ms 94212 KB Output is correct
13 Correct 46 ms 94136 KB Output is correct
14 Correct 44 ms 94180 KB Output is correct
15 Correct 44 ms 94148 KB Output is correct
16 Correct 47 ms 94256 KB Output is correct
17 Correct 47 ms 94236 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 94108 KB Output is correct
2 Correct 51 ms 94136 KB Output is correct
3 Correct 469 ms 177140 KB Output is correct
4 Correct 704 ms 189232 KB Output is correct
5 Correct 428 ms 177344 KB Output is correct
6 Correct 410 ms 168028 KB Output is correct
7 Correct 439 ms 177232 KB Output is correct
8 Correct 571 ms 200128 KB Output is correct
9 Correct 503 ms 176604 KB Output is correct
10 Correct 857 ms 224400 KB Output is correct
11 Correct 375 ms 143600 KB Output is correct
12 Correct 362 ms 134456 KB Output is correct
13 Correct 753 ms 212516 KB Output is correct
14 Correct 240 ms 129760 KB Output is correct
15 Correct 285 ms 131968 KB Output is correct
16 Correct 266 ms 133432 KB Output is correct
17 Correct 292 ms 131824 KB Output is correct
18 Correct 176 ms 131096 KB Output is correct
19 Correct 52 ms 95952 KB Output is correct
20 Correct 115 ms 111912 KB Output is correct
21 Correct 315 ms 132836 KB Output is correct
22 Correct 329 ms 139668 KB Output is correct
23 Correct 245 ms 138172 KB Output is correct
24 Correct 286 ms 134612 KB Output is correct
25 Correct 337 ms 132968 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 109584 KB Output is correct
2 Runtime error 679 ms 608104 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 109584 KB Output is correct
2 Runtime error 679 ms 608104 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 94284 KB Output is correct
2 Correct 45 ms 94112 KB Output is correct
3 Correct 48 ms 94156 KB Output is correct
4 Correct 50 ms 94220 KB Output is correct
5 Correct 44 ms 94216 KB Output is correct
6 Correct 45 ms 94232 KB Output is correct
7 Correct 46 ms 94236 KB Output is correct
8 Correct 47 ms 94280 KB Output is correct
9 Correct 45 ms 94136 KB Output is correct
10 Correct 48 ms 94300 KB Output is correct
11 Correct 47 ms 94152 KB Output is correct
12 Correct 47 ms 94212 KB Output is correct
13 Correct 46 ms 94136 KB Output is correct
14 Correct 44 ms 94180 KB Output is correct
15 Correct 44 ms 94148 KB Output is correct
16 Correct 47 ms 94256 KB Output is correct
17 Correct 47 ms 94236 KB Output is correct
18 Correct 47 ms 94108 KB Output is correct
19 Correct 51 ms 94136 KB Output is correct
20 Correct 469 ms 177140 KB Output is correct
21 Correct 704 ms 189232 KB Output is correct
22 Correct 428 ms 177344 KB Output is correct
23 Correct 410 ms 168028 KB Output is correct
24 Correct 439 ms 177232 KB Output is correct
25 Correct 571 ms 200128 KB Output is correct
26 Correct 503 ms 176604 KB Output is correct
27 Correct 857 ms 224400 KB Output is correct
28 Correct 375 ms 143600 KB Output is correct
29 Correct 362 ms 134456 KB Output is correct
30 Correct 753 ms 212516 KB Output is correct
31 Correct 240 ms 129760 KB Output is correct
32 Correct 285 ms 131968 KB Output is correct
33 Correct 266 ms 133432 KB Output is correct
34 Correct 292 ms 131824 KB Output is correct
35 Correct 176 ms 131096 KB Output is correct
36 Correct 52 ms 95952 KB Output is correct
37 Correct 115 ms 111912 KB Output is correct
38 Correct 315 ms 132836 KB Output is correct
39 Correct 329 ms 139668 KB Output is correct
40 Correct 245 ms 138172 KB Output is correct
41 Correct 286 ms 134612 KB Output is correct
42 Correct 337 ms 132968 KB Output is correct
43 Correct 121 ms 109584 KB Output is correct
44 Runtime error 679 ms 608104 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -