oj.uz

Submission #823423

# Submission time Handle Problem Language Result Execution time Memory
823423 2023-08-12T13:55:50 Z I_Love_EliskaM_ Sky Walking (IOI19_walk) C++17
39 / 100
 1569 ms 230012 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
using ll = long long;
const ll inf = LLONG_MAX;
#define pi pair<ll,ll>
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()

#define int ll
const int sz=1<<30;
struct sgt {
	sgt *L, *R; int s;
	sgt() {
		L=R=NULL; s=inf;
	}
	void set(int l, int r, int i, int x) {
		if (r-l==1) {
			s=x; return;
		}
		int m=(l+r)>>1;
		if (i<m) {
			if (!L) L=new sgt();
			L->set(l,m,i,x);
		} else {
			if (!R) R=new sgt();
			R->set(m,r,i,x);
		}
		s = min(L?L->s:inf, R?R->s:inf);
	}
	void set(int i, int x) {
		set(0,sz,i,x);
	}
	int query(int l, int r, int lx, int rx) {
		if (rx<=l || r<=lx) return inf;
		if (lx<=l && r<=rx) return s;
		int m=(l+r)>>1;
		int lq=L?L->query(l,m,lx,rx):inf;
		int rq=R?R->query(m,r,lx,rx):inf;
		return min(lq,rq);
	}
	int query(int l, int r) {
		return query(0,sz,l,r);
	}
};

const int N=1e5+55;
vector<pi> adj[10*N];
ll d[10*N];

map<int,int> c[N]; int _z=0; const int Z=1e9+5;
int ind(int x, int y) {
	if (c[x].count(y)) return c[x][y];
	return c[x][y]=_z++;
}
#undef int

ll p12(vector<int>x, vector<int>h, vector<int>l, vector<int>r, vector<int>y, int s, int g) {
	int n=x.size(), m=l.size();
	
	vector<vector<int>> g1(n);
	vector<vector<int>> g2(m);
	g1[s].pb(0);
	g1[g].pb(0);

	vector<pi> v;
	forn(i,n) v.pb({h[i],i});
	forn(i,m) v.pb({y[i],-i-1});
	sort(rall(v));

	set<int> st; 
	for(auto&z:v) {
		int y=z.f, i=z.s;
		if (i>=0) {
			st.insert(i); continue;
		}
		i*=-1; --i;
		auto it=st.upper_bound(l[i]);
		vector<int> v;
		while (1) {
			int j=*it;
			v.pb(j);
			if (j==r[i]) break;
			++it;
		}
		if (v.size() > 10 && max(n,m)>50) return -2;
		g1[l[i]].pb(y);
		int last=l[i];
		for(auto&j:v) {
			adj[ind(last,y)].pb({ind(j,y),x[j]-x[last]});
			adj[ind(j,y)].pb({ind(last,y),x[j]-x[last]});
			g1[j].pb(y);
			last=j;
		}
	}

	forn(i,n) {
		sort(all(g1[i]));
		int sz=g1[i].size();
		forn(j,sz-1) {
			adj[ind(i,g1[i][j])].pb({ind(i,g1[i][j+1]),g1[i][j+1]-g1[i][j]});
			adj[ind(i,g1[i][j+1])].pb({ind(i,g1[i][j]),g1[i][j+1]-g1[i][j]});
		}
	}

	forn(i,_z) d[i]=inf;
	priority_queue<pair<ll,ll>> q; q.push({0,ind(s,0)});

	while(q.size()) {
		auto it=q.top(); q.pop();
		ll di=-it.f, u=it.s;
		if (d[u]<=di) continue;
		d[u]=di;
		//assert(adj[u].size()<=4);
		for(auto&e:adj[u]) {
			int v=e.f, w=e.s;
			if (d[v]!=inf) continue;
			q.push({-di-w,v});
		}
	}

	if (d[ind(g,0)]==inf) return -1;
	return d[ind(g,0)];
}

ll min_distance(vector<int>x, vector<int>h, vector<int>l, vector<int>r, vector<int>y, int s, int g) {
	int n=x.size(), m=l.size();

	auto z = p12(x,h,l,r,y,s,g);
	if (z!=-2) return z;
	
	#define int ll

	sgt bottom, top;
	bottom.set(0,0);
	top.set(0,0);
	vector<vector<int>> add(n), del(n);
	del[0].pb(0);
	add[n-1].pb(0);
	forn(i,m) {
		add[l[i]].pb(y[i]);
		del[r[i]].pb(y[i]);
	}
	forn(i,n) {
		vector<pi> toset;
		for(auto&y:add[i]) {
			int f = bottom.query(0,y+1);
			assert(y<=h[i]);
			int s = top.query(y,h[i]+1);
			if (min(f,s)==inf) continue;
			if (f==inf) {
				toset.pb({y,s-y});
				continue;
			}
			if (s==inf) {
				toset.pb({y,f+y});
				continue;
			}
			f+=y; s-=y;
			int x=min(f,s);
			toset.pb({y,x});
		}
		for(auto&y:del[i]) {
			bottom.set(y,inf);
			top.set(y,inf);
		}
		for(auto&x:toset) {
			bottom.set(x.f,x.s-x.f);
			top.set(x.f,x.s+x.f);
		}
	}
	if (top.s==inf) return -1;
	int f = top.s+x[n-1]-x[0];
	return f;

	#undef int
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28500 KB Output is correct
2 Correct 16 ms 28388 KB Output is correct
3 Correct 16 ms 28416 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 16 ms 28628 KB Output is correct
6 Correct 16 ms 28500 KB Output is correct
7 Correct 16 ms 28500 KB Output is correct
8 Correct 15 ms 28500 KB Output is correct
9 Correct 16 ms 28524 KB Output is correct
10 Correct 15 ms 28612 KB Output is correct
11 Correct 16 ms 28500 KB Output is correct
12 Correct 16 ms 28500 KB Output is correct
13 Correct 16 ms 28440 KB Output is correct
14 Correct 15 ms 28512 KB Output is correct
15 Correct 15 ms 28500 KB Output is correct
16 Correct 15 ms 28444 KB Output is correct
17 Correct 16 ms 28644 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 16 ms 28500 KB Output is correct
3 Correct 1161 ms 166052 KB Output is correct
4 Correct 1006 ms 172724 KB Output is correct
5 Correct 625 ms 153268 KB Output is correct
6 Correct 524 ms 138196 KB Output is correct
7 Correct 592 ms 153380 KB Output is correct
8 Correct 1569 ms 204872 KB Output is correct
9 Correct 774 ms 151804 KB Output is correct
10 Correct 1446 ms 230012 KB Output is correct
11 Correct 519 ms 101008 KB Output is correct
12 Correct 334 ms 75012 KB Output is correct
13 Correct 1177 ms 203988 KB Output is correct
14 Correct 227 ms 74480 KB Output is correct
15 Correct 281 ms 76284 KB Output is correct
16 Correct 265 ms 77220 KB Output is correct
17 Correct 276 ms 75984 KB Output is correct
18 Correct 353 ms 87256 KB Output is correct
19 Correct 24 ms 30808 KB Output is correct
20 Correct 94 ms 51980 KB Output is correct
21 Correct 278 ms 73548 KB Output is correct
22 Correct 270 ms 75096 KB Output is correct
23 Correct 285 ms 89836 KB Output is correct
24 Correct 259 ms 75780 KB Output is correct
25 Correct 282 ms 75692 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 47168 KB Output is correct
2 Correct 419 ms 122692 KB Output is correct
3 Correct 390 ms 108856 KB Output is correct
4 Correct 479 ms 127788 KB Output is correct
5 Correct 498 ms 128428 KB Output is correct
6 Correct 497 ms 130604 KB Output is correct
7 Correct 228 ms 84048 KB Output is correct
8 Correct 323 ms 75048 KB Output is correct
9 Correct 504 ms 126636 KB Output is correct
10 Correct 197 ms 47648 KB Output is correct
11 Correct 37 ms 33940 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 47168 KB Output is correct
2 Correct 419 ms 122692 KB Output is correct
3 Correct 390 ms 108856 KB Output is correct
4 Correct 479 ms 127788 KB Output is correct
5 Correct 498 ms 128428 KB Output is correct
6 Correct 497 ms 130604 KB Output is correct
7 Correct 228 ms 84048 KB Output is correct
8 Correct 323 ms 75048 KB Output is correct
9 Correct 504 ms 126636 KB Output is correct
10 Correct 197 ms 47648 KB Output is correct
11 Correct 37 ms 33940 KB Output is correct
12 Correct 417 ms 116668 KB Output is correct
13 Correct 387 ms 124140 KB Output is correct
14 Correct 560 ms 123060 KB Output is correct
15 Correct 363 ms 83852 KB Output is correct
16 Correct 297 ms 73088 KB Output is correct
17 Correct 305 ms 73100 KB Output is correct
18 Correct 371 ms 84024 KB Output is correct
19 Correct 285 ms 73068 KB Output is correct
20 Correct 253 ms 83212 KB Output is correct
21 Correct 60 ms 36084 KB Output is correct
22 Correct 250 ms 103144 KB Output is correct
23 Correct 257 ms 104392 KB Output is correct
24 Correct 451 ms 118704 KB Output is correct
25 Correct 270 ms 114192 KB Output is correct
26 Incorrect 236 ms 74480 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 28500 KB Output is correct
2 Correct 16 ms 28388 KB Output is correct
3 Correct 16 ms 28416 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 16 ms 28628 KB Output is correct
6 Correct 16 ms 28500 KB Output is correct
7 Correct 16 ms 28500 KB Output is correct
8 Correct 15 ms 28500 KB Output is correct
9 Correct 16 ms 28524 KB Output is correct
10 Correct 15 ms 28612 KB Output is correct
11 Correct 16 ms 28500 KB Output is correct
12 Correct 16 ms 28500 KB Output is correct
13 Correct 16 ms 28440 KB Output is correct
14 Correct 15 ms 28512 KB Output is correct
15 Correct 15 ms 28500 KB Output is correct
16 Correct 15 ms 28444 KB Output is correct
17 Correct 16 ms 28644 KB Output is correct
18 Correct 15 ms 28500 KB Output is correct
19 Correct 16 ms 28500 KB Output is correct
20 Correct 1161 ms 166052 KB Output is correct
21 Correct 1006 ms 172724 KB Output is correct
22 Correct 625 ms 153268 KB Output is correct
23 Correct 524 ms 138196 KB Output is correct
24 Correct 592 ms 153380 KB Output is correct
25 Correct 1569 ms 204872 KB Output is correct
26 Correct 774 ms 151804 KB Output is correct
27 Correct 1446 ms 230012 KB Output is correct
28 Correct 519 ms 101008 KB Output is correct
29 Correct 334 ms 75012 KB Output is correct
30 Correct 1177 ms 203988 KB Output is correct
31 Correct 227 ms 74480 KB Output is correct
32 Correct 281 ms 76284 KB Output is correct
33 Correct 265 ms 77220 KB Output is correct
34 Correct 276 ms 75984 KB Output is correct
35 Correct 353 ms 87256 KB Output is correct
36 Correct 24 ms 30808 KB Output is correct
37 Correct 94 ms 51980 KB Output is correct
38 Correct 278 ms 73548 KB Output is correct
39 Correct 270 ms 75096 KB Output is correct
40 Correct 285 ms 89836 KB Output is correct
41 Correct 259 ms 75780 KB Output is correct
42 Correct 282 ms 75692 KB Output is correct
43 Correct 96 ms 47168 KB Output is correct
44 Correct 419 ms 122692 KB Output is correct
45 Correct 390 ms 108856 KB Output is correct
46 Correct 479 ms 127788 KB Output is correct
47 Correct 498 ms 128428 KB Output is correct
48 Correct 497 ms 130604 KB Output is correct
49 Correct 228 ms 84048 KB Output is correct
50 Correct 323 ms 75048 KB Output is correct
51 Correct 504 ms 126636 KB Output is correct
52 Correct 197 ms 47648 KB Output is correct
53 Correct 37 ms 33940 KB Output is correct
54 Correct 417 ms 116668 KB Output is correct
55 Correct 387 ms 124140 KB Output is correct
56 Correct 560 ms 123060 KB Output is correct
57 Correct 363 ms 83852 KB Output is correct
58 Correct 297 ms 73088 KB Output is correct
59 Correct 305 ms 73100 KB Output is correct
60 Correct 371 ms 84024 KB Output is correct
61 Correct 285 ms 73068 KB Output is correct
62 Correct 253 ms 83212 KB Output is correct
63 Correct 60 ms 36084 KB Output is correct
64 Correct 250 ms 103144 KB Output is correct
65 Correct 257 ms 104392 KB Output is correct
66 Correct 451 ms 118704 KB Output is correct
67 Correct 270 ms 114192 KB Output is correct
68 Incorrect 236 ms 74480 KB Output isn't correct
69 Halted 0 ms 0 KB -