oj.uz

Submission #823415

# Submission time Handle Problem Language Result Execution time Memory
823415 2023-08-12T13:36:11 Z I_Love_EliskaM_ Sky Walking (IOI19_walk) C++17
39 / 100
 1677 ms 229924 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 = 1e18;
#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);
			int s = top.query(y,sz);
			if (min(f,s)==inf) return -1;
			f+=y; s-=y;
			int x=min(f,s);
			toset.pb({y,x});
			//cout<<"! "<<i<<' '<<y<<' '<<x<<'\n';
		}
		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);
		}
	}
	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 15 ms 28500 KB Output is correct
2 Correct 15 ms 28452 KB Output is correct
3 Correct 16 ms 28460 KB Output is correct
4 Correct 17 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 15 ms 28520 KB Output is correct
8 Correct 15 ms 28500 KB Output is correct
9 Correct 15 ms 28448 KB Output is correct
10 Correct 16 ms 28628 KB Output is correct
11 Correct 18 ms 28496 KB Output is correct
12 Correct 15 ms 28500 KB Output is correct
13 Correct 19 ms 28412 KB Output is correct
14 Correct 16 ms 28456 KB Output is correct
15 Correct 20 ms 28480 KB Output is correct
16 Correct 16 ms 28504 KB Output is correct
17 Correct 16 ms 28628 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28516 KB Output is correct
2 Correct 15 ms 28500 KB Output is correct
3 Correct 1204 ms 166332 KB Output is correct
4 Correct 1008 ms 172780 KB Output is correct
5 Correct 617 ms 153344 KB Output is correct
6 Correct 577 ms 138124 KB Output is correct
7 Correct 594 ms 153340 KB Output is correct
8 Correct 1677 ms 204804 KB Output is correct
9 Correct 800 ms 151860 KB Output is correct
10 Correct 1490 ms 229924 KB Output is correct
11 Correct 552 ms 100888 KB Output is correct
12 Correct 365 ms 75152 KB Output is correct
13 Correct 1155 ms 203844 KB Output is correct
14 Correct 241 ms 74440 KB Output is correct
15 Correct 290 ms 76252 KB Output is correct
16 Correct 278 ms 77292 KB Output is correct
17 Correct 271 ms 75980 KB Output is correct
18 Correct 359 ms 87272 KB Output is correct
19 Correct 22 ms 30800 KB Output is correct
20 Correct 95 ms 51964 KB Output is correct
21 Correct 304 ms 73380 KB Output is correct
22 Correct 268 ms 75116 KB Output is correct
23 Correct 268 ms 89860 KB Output is correct
24 Correct 267 ms 75824 KB Output is correct
25 Correct 317 ms 75520 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 47168 KB Output is correct
2 Correct 400 ms 122604 KB Output is correct
3 Correct 411 ms 108916 KB Output is correct
4 Correct 469 ms 127636 KB Output is correct
5 Correct 506 ms 128520 KB Output is correct
6 Correct 487 ms 130564 KB Output is correct
7 Correct 227 ms 84064 KB Output is correct
8 Correct 282 ms 75088 KB Output is correct
9 Correct 492 ms 126584 KB Output is correct
10 Correct 186 ms 47772 KB Output is correct
11 Correct 36 ms 33992 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 47168 KB Output is correct
2 Correct 400 ms 122604 KB Output is correct
3 Correct 411 ms 108916 KB Output is correct
4 Correct 469 ms 127636 KB Output is correct
5 Correct 506 ms 128520 KB Output is correct
6 Correct 487 ms 130564 KB Output is correct
7 Correct 227 ms 84064 KB Output is correct
8 Correct 282 ms 75088 KB Output is correct
9 Correct 492 ms 126584 KB Output is correct
10 Correct 186 ms 47772 KB Output is correct
11 Correct 36 ms 33992 KB Output is correct
12 Correct 417 ms 116728 KB Output is correct
13 Correct 90 ms 43244 KB Output is correct
14 Correct 479 ms 123004 KB Output is correct
15 Correct 388 ms 83816 KB Output is correct
16 Correct 280 ms 73068 KB Output is correct
17 Correct 281 ms 73124 KB Output is correct
18 Correct 374 ms 83820 KB Output is correct
19 Correct 275 ms 73120 KB Output is correct
20 Correct 235 ms 83228 KB Output is correct
21 Correct 47 ms 36056 KB Output is correct
22 Correct 317 ms 103152 KB Output is correct
23 Correct 291 ms 104472 KB Output is correct
24 Correct 434 ms 118640 KB Output is correct
25 Correct 309 ms 114220 KB Output is correct
26 Incorrect 234 ms 74472 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 15 ms 28452 KB Output is correct
3 Correct 16 ms 28460 KB Output is correct
4 Correct 17 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 15 ms 28520 KB Output is correct
8 Correct 15 ms 28500 KB Output is correct
9 Correct 15 ms 28448 KB Output is correct
10 Correct 16 ms 28628 KB Output is correct
11 Correct 18 ms 28496 KB Output is correct
12 Correct 15 ms 28500 KB Output is correct
13 Correct 19 ms 28412 KB Output is correct
14 Correct 16 ms 28456 KB Output is correct
15 Correct 20 ms 28480 KB Output is correct
16 Correct 16 ms 28504 KB Output is correct
17 Correct 16 ms 28628 KB Output is correct
18 Correct 16 ms 28516 KB Output is correct
19 Correct 15 ms 28500 KB Output is correct
20 Correct 1204 ms 166332 KB Output is correct
21 Correct 1008 ms 172780 KB Output is correct
22 Correct 617 ms 153344 KB Output is correct
23 Correct 577 ms 138124 KB Output is correct
24 Correct 594 ms 153340 KB Output is correct
25 Correct 1677 ms 204804 KB Output is correct
26 Correct 800 ms 151860 KB Output is correct
27 Correct 1490 ms 229924 KB Output is correct
28 Correct 552 ms 100888 KB Output is correct
29 Correct 365 ms 75152 KB Output is correct
30 Correct 1155 ms 203844 KB Output is correct
31 Correct 241 ms 74440 KB Output is correct
32 Correct 290 ms 76252 KB Output is correct
33 Correct 278 ms 77292 KB Output is correct
34 Correct 271 ms 75980 KB Output is correct
35 Correct 359 ms 87272 KB Output is correct
36 Correct 22 ms 30800 KB Output is correct
37 Correct 95 ms 51964 KB Output is correct
38 Correct 304 ms 73380 KB Output is correct
39 Correct 268 ms 75116 KB Output is correct
40 Correct 268 ms 89860 KB Output is correct
41 Correct 267 ms 75824 KB Output is correct
42 Correct 317 ms 75520 KB Output is correct
43 Correct 91 ms 47168 KB Output is correct
44 Correct 400 ms 122604 KB Output is correct
45 Correct 411 ms 108916 KB Output is correct
46 Correct 469 ms 127636 KB Output is correct
47 Correct 506 ms 128520 KB Output is correct
48 Correct 487 ms 130564 KB Output is correct
49 Correct 227 ms 84064 KB Output is correct
50 Correct 282 ms 75088 KB Output is correct
51 Correct 492 ms 126584 KB Output is correct
52 Correct 186 ms 47772 KB Output is correct
53 Correct 36 ms 33992 KB Output is correct
54 Correct 417 ms 116728 KB Output is correct
55 Correct 90 ms 43244 KB Output is correct
56 Correct 479 ms 123004 KB Output is correct
57 Correct 388 ms 83816 KB Output is correct
58 Correct 280 ms 73068 KB Output is correct
59 Correct 281 ms 73124 KB Output is correct
60 Correct 374 ms 83820 KB Output is correct
61 Correct 275 ms 73120 KB Output is correct
62 Correct 235 ms 83228 KB Output is correct
63 Correct 47 ms 36056 KB Output is correct
64 Correct 317 ms 103152 KB Output is correct
65 Correct 291 ms 104472 KB Output is correct
66 Correct 434 ms 118640 KB Output is correct
67 Correct 309 ms 114220 KB Output is correct
68 Incorrect 234 ms 74472 KB Output isn't correct
69 Halted 0 ms 0 KB -