oj.uz

Submission #737364

# Submission time Handle Problem Language Result Execution time Memory
737364 2023-05-07T05:51:34 Z bobthebuilder Sky Walking (IOI19_walk) C++17
0 / 100
 936 ms 243308 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});
	}
	vector<pii> vv;
	sort(ALL(v));
	REP(i,m){
		vv.pb({y[i],i});
	}
	sort(ALL(vv));
	reverse(ALL(vv)),reverse(ALL(v));
	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;
		}
		if(s==0 and g==n-1) for(int x:del) ss.erase(x);
	}
	for(int z:{s,g}){
		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 46 ms 94164 KB Output is correct
2 Correct 44 ms 94192 KB Output is correct
3 Correct 44 ms 94244 KB Output is correct
4 Runtime error 130 ms 190804 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94152 KB Output is correct
2 Correct 45 ms 94164 KB Output is correct
3 Correct 507 ms 176576 KB Output is correct
4 Correct 712 ms 180536 KB Output is correct
5 Correct 471 ms 169408 KB Output is correct
6 Correct 459 ms 160568 KB Output is correct
7 Correct 523 ms 169436 KB Output is correct
8 Correct 618 ms 197200 KB Output is correct
9 Correct 557 ms 168476 KB Output is correct
10 Correct 936 ms 214252 KB Output is correct
11 Correct 403 ms 138312 KB Output is correct
12 Correct 346 ms 122604 KB Output is correct
13 Correct 570 ms 147764 KB Output is correct
14 Runtime error 303 ms 243308 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 108944 KB Output is correct
2 Correct 323 ms 140692 KB Output is correct
3 Correct 399 ms 144316 KB Output is correct
4 Correct 613 ms 159748 KB Output is correct
5 Correct 572 ms 160384 KB Output is correct
6 Correct 564 ms 158048 KB Output is correct
7 Correct 376 ms 134268 KB Output is correct
8 Correct 293 ms 122468 KB Output is correct
9 Correct 551 ms 156456 KB Output is correct
10 Correct 320 ms 138672 KB Output is correct
11 Runtime error 144 ms 199260 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 108944 KB Output is correct
2 Correct 323 ms 140692 KB Output is correct
3 Correct 399 ms 144316 KB Output is correct
4 Correct 613 ms 159748 KB Output is correct
5 Correct 572 ms 160384 KB Output is correct
6 Correct 564 ms 158048 KB Output is correct
7 Correct 376 ms 134268 KB Output is correct
8 Correct 293 ms 122468 KB Output is correct
9 Correct 551 ms 156456 KB Output is correct
10 Correct 320 ms 138672 KB Output is correct
11 Runtime error 144 ms 199260 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 94164 KB Output is correct
2 Correct 44 ms 94192 KB Output is correct
3 Correct 44 ms 94244 KB Output is correct
4 Runtime error 130 ms 190804 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -