oj.uz

Submission #737345

# Submission time Handle Problem Language Result Execution time Memory
737345 2023-05-07T05:33:13 Z bobthebuilder Sky Walking (IOI19_walk) C++17
24 / 100
 873 ms 607236 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 45 ms 94156 KB Output is correct
2 Correct 47 ms 94176 KB Output is correct
3 Correct 45 ms 94220 KB Output is correct
4 Correct 44 ms 94232 KB Output is correct
5 Correct 45 ms 94236 KB Output is correct
6 Correct 48 ms 94192 KB Output is correct
7 Correct 50 ms 94412 KB Output is correct
8 Correct 46 ms 94196 KB Output is correct
9 Correct 46 ms 94156 KB Output is correct
10 Correct 45 ms 94284 KB Output is correct
11 Correct 49 ms 94304 KB Output is correct
12 Correct 49 ms 94172 KB Output is correct
13 Correct 55 ms 94188 KB Output is correct
14 Correct 46 ms 94132 KB Output is correct
15 Correct 46 ms 94164 KB Output is correct
16 Correct 54 ms 94124 KB Output is correct
17 Correct 48 ms 94280 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 94112 KB Output is correct
2 Correct 47 ms 94156 KB Output is correct
3 Correct 522 ms 177128 KB Output is correct
4 Correct 735 ms 189000 KB Output is correct
5 Correct 469 ms 173608 KB Output is correct
6 Correct 460 ms 164260 KB Output is correct
7 Correct 460 ms 173676 KB Output is correct
8 Correct 595 ms 197928 KB Output is correct
9 Correct 609 ms 173048 KB Output is correct
10 Correct 873 ms 220208 KB Output is correct
11 Correct 404 ms 140872 KB Output is correct
12 Correct 381 ms 130448 KB Output is correct
13 Correct 839 ms 208508 KB Output is correct
14 Correct 273 ms 126524 KB Output is correct
15 Correct 290 ms 129076 KB Output is correct
16 Correct 322 ms 131016 KB Output is correct
17 Correct 319 ms 129824 KB Output is correct
18 Correct 181 ms 128956 KB Output is correct
19 Correct 60 ms 95948 KB Output is correct
20 Correct 117 ms 110372 KB Output is correct
21 Correct 302 ms 130468 KB Output is correct
22 Correct 367 ms 136884 KB Output is correct
23 Correct 259 ms 135680 KB Output is correct
24 Correct 293 ms 131832 KB Output is correct
25 Correct 358 ms 130616 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 109600 KB Output is correct
2 Runtime error 726 ms 607236 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 125 ms 109600 KB Output is correct
2 Runtime error 726 ms 607236 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 45 ms 94156 KB Output is correct
2 Correct 47 ms 94176 KB Output is correct
3 Correct 45 ms 94220 KB Output is correct
4 Correct 44 ms 94232 KB Output is correct
5 Correct 45 ms 94236 KB Output is correct
6 Correct 48 ms 94192 KB Output is correct
7 Correct 50 ms 94412 KB Output is correct
8 Correct 46 ms 94196 KB Output is correct
9 Correct 46 ms 94156 KB Output is correct
10 Correct 45 ms 94284 KB Output is correct
11 Correct 49 ms 94304 KB Output is correct
12 Correct 49 ms 94172 KB Output is correct
13 Correct 55 ms 94188 KB Output is correct
14 Correct 46 ms 94132 KB Output is correct
15 Correct 46 ms 94164 KB Output is correct
16 Correct 54 ms 94124 KB Output is correct
17 Correct 48 ms 94280 KB Output is correct
18 Correct 49 ms 94112 KB Output is correct
19 Correct 47 ms 94156 KB Output is correct
20 Correct 522 ms 177128 KB Output is correct
21 Correct 735 ms 189000 KB Output is correct
22 Correct 469 ms 173608 KB Output is correct
23 Correct 460 ms 164260 KB Output is correct
24 Correct 460 ms 173676 KB Output is correct
25 Correct 595 ms 197928 KB Output is correct
26 Correct 609 ms 173048 KB Output is correct
27 Correct 873 ms 220208 KB Output is correct
28 Correct 404 ms 140872 KB Output is correct
29 Correct 381 ms 130448 KB Output is correct
30 Correct 839 ms 208508 KB Output is correct
31 Correct 273 ms 126524 KB Output is correct
32 Correct 290 ms 129076 KB Output is correct
33 Correct 322 ms 131016 KB Output is correct
34 Correct 319 ms 129824 KB Output is correct
35 Correct 181 ms 128956 KB Output is correct
36 Correct 60 ms 95948 KB Output is correct
37 Correct 117 ms 110372 KB Output is correct
38 Correct 302 ms 130468 KB Output is correct
39 Correct 367 ms 136884 KB Output is correct
40 Correct 259 ms 135680 KB Output is correct
41 Correct 293 ms 131832 KB Output is correct
42 Correct 358 ms 130616 KB Output is correct
43 Correct 125 ms 109600 KB Output is correct
44 Runtime error 726 ms 607236 KB Execution killed with signal 11
45 Halted 0 ms 0 KB -