oj.uz

Submission #823455

# Submission time Handle Problem Language Result Execution time Memory
823455 2023-08-12T14:22:56 Z I_Love_EliskaM_ Sky Walking (IOI19_walk) C++17
39 / 100
 1463 ms 229912 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 st;
	forn(i,n) st.set(i,-h[i]);

	sgt bottom, top;
	bottom.set(0,0);
	top.set(0,0);
	vector<vector<int>> del(n);
	vector<vector<pi>> add(n);
	del[0].pb(0);
	add[n-1].pb({0,inf});
	forn(i,m) {
		add[l[i]].pb({y[i],-st.query(l[i],r[i]+1)});
		del[r[i]].pb(y[i]);
	}
	forn(i,n) {
		vector<pi> toset;
		for(auto&it:add[i]) {
			int y=it.f, z=it.s;
			int f = bottom.query(0,y+1);
			int s = top.query(y,z+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;
	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 12 ms 28500 KB Output is correct
2 Correct 16 ms 28388 KB Output is correct
3 Correct 14 ms 28428 KB Output is correct
4 Correct 15 ms 28488 KB Output is correct
5 Correct 14 ms 28524 KB Output is correct
6 Correct 15 ms 28532 KB Output is correct
7 Correct 16 ms 28632 KB Output is correct
8 Correct 15 ms 28492 KB Output is correct
9 Correct 15 ms 28524 KB Output is correct
10 Correct 16 ms 28628 KB Output is correct
11 Correct 12 ms 28532 KB Output is correct
12 Correct 17 ms 28500 KB Output is correct
13 Correct 13 ms 28412 KB Output is correct
14 Correct 12 ms 28472 KB Output is correct
15 Correct 12 ms 28500 KB Output is correct
16 Correct 12 ms 28500 KB Output is correct
17 Correct 12 ms 28588 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28500 KB Output is correct
2 Correct 16 ms 28400 KB Output is correct
3 Correct 1256 ms 166056 KB Output is correct
4 Correct 977 ms 172748 KB Output is correct
5 Correct 617 ms 153320 KB Output is correct
6 Correct 483 ms 138192 KB Output is correct
7 Correct 620 ms 153360 KB Output is correct
8 Correct 1463 ms 204804 KB Output is correct
9 Correct 707 ms 151832 KB Output is correct
10 Correct 1276 ms 229912 KB Output is correct
11 Correct 503 ms 100964 KB Output is correct
12 Correct 304 ms 75088 KB Output is correct
13 Correct 1025 ms 203864 KB Output is correct
14 Correct 218 ms 74552 KB Output is correct
15 Correct 265 ms 76252 KB Output is correct
16 Correct 250 ms 77272 KB Output is correct
17 Correct 271 ms 76052 KB Output is correct
18 Correct 358 ms 87264 KB Output is correct
19 Correct 28 ms 30792 KB Output is correct
20 Correct 94 ms 52008 KB Output is correct
21 Correct 266 ms 73356 KB Output is correct
22 Correct 308 ms 75292 KB Output is correct
23 Correct 265 ms 89844 KB Output is correct
24 Correct 248 ms 75816 KB Output is correct
25 Correct 279 ms 75740 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 47172 KB Output is correct
2 Correct 415 ms 123772 KB Output is correct
3 Correct 418 ms 110536 KB Output is correct
4 Correct 534 ms 134408 KB Output is correct
5 Correct 570 ms 135568 KB Output is correct
6 Correct 596 ms 137340 KB Output is correct
7 Correct 279 ms 90452 KB Output is correct
8 Correct 300 ms 75064 KB Output is correct
9 Correct 547 ms 132952 KB Output is correct
10 Correct 227 ms 54412 KB Output is correct
11 Correct 51 ms 34748 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 47172 KB Output is correct
2 Correct 415 ms 123772 KB Output is correct
3 Correct 418 ms 110536 KB Output is correct
4 Correct 534 ms 134408 KB Output is correct
5 Correct 570 ms 135568 KB Output is correct
6 Correct 596 ms 137340 KB Output is correct
7 Correct 279 ms 90452 KB Output is correct
8 Correct 300 ms 75064 KB Output is correct
9 Correct 547 ms 132952 KB Output is correct
10 Correct 227 ms 54412 KB Output is correct
11 Correct 51 ms 34748 KB Output is correct
12 Correct 406 ms 118376 KB Output is correct
13 Correct 399 ms 130940 KB Output is correct
14 Correct 511 ms 130200 KB Output is correct
15 Correct 420 ms 90832 KB Output is correct
16 Correct 339 ms 80132 KB Output is correct
17 Correct 359 ms 80108 KB Output is correct
18 Correct 451 ms 90864 KB Output is correct
19 Correct 335 ms 80200 KB Output is correct
20 Correct 271 ms 89500 KB Output is correct
21 Correct 66 ms 42344 KB Output is correct
22 Correct 283 ms 110004 KB Output is correct
23 Correct 308 ms 111236 KB Output is correct
24 Correct 410 ms 118720 KB Output is correct
25 Correct 353 ms 121144 KB Output is correct
26 Incorrect 234 ms 74556 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 28500 KB Output is correct
2 Correct 16 ms 28388 KB Output is correct
3 Correct 14 ms 28428 KB Output is correct
4 Correct 15 ms 28488 KB Output is correct
5 Correct 14 ms 28524 KB Output is correct
6 Correct 15 ms 28532 KB Output is correct
7 Correct 16 ms 28632 KB Output is correct
8 Correct 15 ms 28492 KB Output is correct
9 Correct 15 ms 28524 KB Output is correct
10 Correct 16 ms 28628 KB Output is correct
11 Correct 12 ms 28532 KB Output is correct
12 Correct 17 ms 28500 KB Output is correct
13 Correct 13 ms 28412 KB Output is correct
14 Correct 12 ms 28472 KB Output is correct
15 Correct 12 ms 28500 KB Output is correct
16 Correct 12 ms 28500 KB Output is correct
17 Correct 12 ms 28588 KB Output is correct
18 Correct 12 ms 28500 KB Output is correct
19 Correct 16 ms 28400 KB Output is correct
20 Correct 1256 ms 166056 KB Output is correct
21 Correct 977 ms 172748 KB Output is correct
22 Correct 617 ms 153320 KB Output is correct
23 Correct 483 ms 138192 KB Output is correct
24 Correct 620 ms 153360 KB Output is correct
25 Correct 1463 ms 204804 KB Output is correct
26 Correct 707 ms 151832 KB Output is correct
27 Correct 1276 ms 229912 KB Output is correct
28 Correct 503 ms 100964 KB Output is correct
29 Correct 304 ms 75088 KB Output is correct
30 Correct 1025 ms 203864 KB Output is correct
31 Correct 218 ms 74552 KB Output is correct
32 Correct 265 ms 76252 KB Output is correct
33 Correct 250 ms 77272 KB Output is correct
34 Correct 271 ms 76052 KB Output is correct
35 Correct 358 ms 87264 KB Output is correct
36 Correct 28 ms 30792 KB Output is correct
37 Correct 94 ms 52008 KB Output is correct
38 Correct 266 ms 73356 KB Output is correct
39 Correct 308 ms 75292 KB Output is correct
40 Correct 265 ms 89844 KB Output is correct
41 Correct 248 ms 75816 KB Output is correct
42 Correct 279 ms 75740 KB Output is correct
43 Correct 100 ms 47172 KB Output is correct
44 Correct 415 ms 123772 KB Output is correct
45 Correct 418 ms 110536 KB Output is correct
46 Correct 534 ms 134408 KB Output is correct
47 Correct 570 ms 135568 KB Output is correct
48 Correct 596 ms 137340 KB Output is correct
49 Correct 279 ms 90452 KB Output is correct
50 Correct 300 ms 75064 KB Output is correct
51 Correct 547 ms 132952 KB Output is correct
52 Correct 227 ms 54412 KB Output is correct
53 Correct 51 ms 34748 KB Output is correct
54 Correct 406 ms 118376 KB Output is correct
55 Correct 399 ms 130940 KB Output is correct
56 Correct 511 ms 130200 KB Output is correct
57 Correct 420 ms 90832 KB Output is correct
58 Correct 339 ms 80132 KB Output is correct
59 Correct 359 ms 80108 KB Output is correct
60 Correct 451 ms 90864 KB Output is correct
61 Correct 335 ms 80200 KB Output is correct
62 Correct 271 ms 89500 KB Output is correct
63 Correct 66 ms 42344 KB Output is correct
64 Correct 283 ms 110004 KB Output is correct
65 Correct 308 ms 111236 KB Output is correct
66 Correct 410 ms 118720 KB Output is correct
67 Correct 353 ms 121144 KB Output is correct
68 Incorrect 234 ms 74556 KB Output isn't correct
69 Halted 0 ms 0 KB -