oj.uz

Submission #823403

# Submission time Handle Problem Language Result Execution time Memory
823403 2023-08-12T13:20:49 Z I_Love_EliskaM_ Sky Walking (IOI19_walk) C++17
39 / 100
 1622 ms 233908 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 = 4e18;
#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;
		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);
			int s = top.query(y,h[i]+1);
			if (min(f,s)==inf) 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;
	ll a = x[n-1];
	ll b = x[0];
	a-=b;
	int f = top.s+a;
	return f;

	#undef int
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28500 KB Output is correct
2 Correct 15 ms 28440 KB Output is correct
3 Correct 17 ms 28412 KB Output is correct
4 Correct 15 ms 28428 KB Output is correct
5 Correct 16 ms 28564 KB Output is correct
6 Correct 18 ms 28596 KB Output is correct
7 Correct 16 ms 28508 KB Output is correct
8 Correct 15 ms 28500 KB Output is correct
9 Correct 17 ms 28492 KB Output is correct
10 Correct 18 ms 28592 KB Output is correct
11 Correct 15 ms 28500 KB Output is correct
12 Correct 16 ms 28524 KB Output is correct
13 Correct 16 ms 28500 KB Output is correct
14 Correct 15 ms 28500 KB Output is correct
15 Correct 16 ms 28500 KB Output is correct
16 Correct 15 ms 28500 KB Output is correct
17 Correct 15 ms 28632 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28488 KB Output is correct
2 Correct 15 ms 28500 KB Output is correct
3 Correct 1189 ms 168080 KB Output is correct
4 Correct 972 ms 176740 KB Output is correct
5 Correct 637 ms 156848 KB Output is correct
6 Correct 525 ms 141740 KB Output is correct
7 Correct 607 ms 156980 KB Output is correct
8 Correct 1622 ms 206740 KB Output is correct
9 Correct 756 ms 155424 KB Output is correct
10 Correct 1443 ms 233908 KB Output is correct
11 Correct 531 ms 103696 KB Output is correct
12 Correct 333 ms 79020 KB Output is correct
13 Correct 1167 ms 207928 KB Output is correct
14 Correct 227 ms 78180 KB Output is correct
15 Correct 276 ms 79564 KB Output is correct
16 Correct 268 ms 80188 KB Output is correct
17 Correct 269 ms 78660 KB Output is correct
18 Correct 349 ms 89820 KB Output is correct
19 Correct 22 ms 30940 KB Output is correct
20 Correct 99 ms 53872 KB Output is correct
21 Correct 264 ms 76196 KB Output is correct
22 Correct 328 ms 78252 KB Output is correct
23 Correct 264 ms 92728 KB Output is correct
24 Correct 272 ms 78788 KB Output is correct
25 Correct 280 ms 78232 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 47168 KB Output is correct
2 Correct 473 ms 122704 KB Output is correct
3 Correct 390 ms 108904 KB Output is correct
4 Correct 487 ms 127552 KB Output is correct
5 Correct 481 ms 128412 KB Output is correct
6 Correct 510 ms 130700 KB Output is correct
7 Correct 225 ms 84096 KB Output is correct
8 Correct 282 ms 75100 KB Output is correct
9 Correct 488 ms 126560 KB Output is correct
10 Correct 181 ms 47748 KB Output is correct
11 Correct 38 ms 33904 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 47168 KB Output is correct
2 Correct 473 ms 122704 KB Output is correct
3 Correct 390 ms 108904 KB Output is correct
4 Correct 487 ms 127552 KB Output is correct
5 Correct 481 ms 128412 KB Output is correct
6 Correct 510 ms 130700 KB Output is correct
7 Correct 225 ms 84096 KB Output is correct
8 Correct 282 ms 75100 KB Output is correct
9 Correct 488 ms 126560 KB Output is correct
10 Correct 181 ms 47748 KB Output is correct
11 Correct 38 ms 33904 KB Output is correct
12 Correct 423 ms 116692 KB Output is correct
13 Correct 396 ms 124112 KB Output is correct
14 Correct 490 ms 123044 KB Output is correct
15 Correct 394 ms 83828 KB Output is correct
16 Correct 283 ms 73080 KB Output is correct
17 Correct 290 ms 73164 KB Output is correct
18 Correct 383 ms 83848 KB Output is correct
19 Correct 287 ms 73176 KB Output is correct
20 Correct 230 ms 83172 KB Output is correct
21 Correct 48 ms 35980 KB Output is correct
22 Correct 248 ms 103176 KB Output is correct
23 Correct 292 ms 104444 KB Output is correct
24 Correct 424 ms 118640 KB Output is correct
25 Correct 283 ms 114272 KB Output is correct
26 Incorrect 225 ms 74504 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28500 KB Output is correct
2 Correct 15 ms 28440 KB Output is correct
3 Correct 17 ms 28412 KB Output is correct
4 Correct 15 ms 28428 KB Output is correct
5 Correct 16 ms 28564 KB Output is correct
6 Correct 18 ms 28596 KB Output is correct
7 Correct 16 ms 28508 KB Output is correct
8 Correct 15 ms 28500 KB Output is correct
9 Correct 17 ms 28492 KB Output is correct
10 Correct 18 ms 28592 KB Output is correct
11 Correct 15 ms 28500 KB Output is correct
12 Correct 16 ms 28524 KB Output is correct
13 Correct 16 ms 28500 KB Output is correct
14 Correct 15 ms 28500 KB Output is correct
15 Correct 16 ms 28500 KB Output is correct
16 Correct 15 ms 28500 KB Output is correct
17 Correct 15 ms 28632 KB Output is correct
18 Correct 15 ms 28488 KB Output is correct
19 Correct 15 ms 28500 KB Output is correct
20 Correct 1189 ms 168080 KB Output is correct
21 Correct 972 ms 176740 KB Output is correct
22 Correct 637 ms 156848 KB Output is correct
23 Correct 525 ms 141740 KB Output is correct
24 Correct 607 ms 156980 KB Output is correct
25 Correct 1622 ms 206740 KB Output is correct
26 Correct 756 ms 155424 KB Output is correct
27 Correct 1443 ms 233908 KB Output is correct
28 Correct 531 ms 103696 KB Output is correct
29 Correct 333 ms 79020 KB Output is correct
30 Correct 1167 ms 207928 KB Output is correct
31 Correct 227 ms 78180 KB Output is correct
32 Correct 276 ms 79564 KB Output is correct
33 Correct 268 ms 80188 KB Output is correct
34 Correct 269 ms 78660 KB Output is correct
35 Correct 349 ms 89820 KB Output is correct
36 Correct 22 ms 30940 KB Output is correct
37 Correct 99 ms 53872 KB Output is correct
38 Correct 264 ms 76196 KB Output is correct
39 Correct 328 ms 78252 KB Output is correct
40 Correct 264 ms 92728 KB Output is correct
41 Correct 272 ms 78788 KB Output is correct
42 Correct 280 ms 78232 KB Output is correct
43 Correct 93 ms 47168 KB Output is correct
44 Correct 473 ms 122704 KB Output is correct
45 Correct 390 ms 108904 KB Output is correct
46 Correct 487 ms 127552 KB Output is correct
47 Correct 481 ms 128412 KB Output is correct
48 Correct 510 ms 130700 KB Output is correct
49 Correct 225 ms 84096 KB Output is correct
50 Correct 282 ms 75100 KB Output is correct
51 Correct 488 ms 126560 KB Output is correct
52 Correct 181 ms 47748 KB Output is correct
53 Correct 38 ms 33904 KB Output is correct
54 Correct 423 ms 116692 KB Output is correct
55 Correct 396 ms 124112 KB Output is correct
56 Correct 490 ms 123044 KB Output is correct
57 Correct 394 ms 83828 KB Output is correct
58 Correct 283 ms 73080 KB Output is correct
59 Correct 290 ms 73164 KB Output is correct
60 Correct 383 ms 83848 KB Output is correct
61 Correct 287 ms 73176 KB Output is correct
62 Correct 230 ms 83172 KB Output is correct
63 Correct 48 ms 35980 KB Output is correct
64 Correct 248 ms 103176 KB Output is correct
65 Correct 292 ms 104444 KB Output is correct
66 Correct 424 ms 118640 KB Output is correct
67 Correct 283 ms 114272 KB Output is correct
68 Incorrect 225 ms 74504 KB Output isn't correct
69 Halted 0 ms 0 KB -