oj.uz

Submission #823422

# Submission time Handle Problem Language Result Execution time Memory
823422 2023-08-12T13:52:45 Z I_Love_EliskaM_ Sky Walking (IOI19_walk) C++17
24 / 100
 1665 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 = 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) return -1;
			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 16 ms 28372 KB Output is correct
2 Correct 16 ms 28416 KB Output is correct
3 Correct 16 ms 28500 KB Output is correct
4 Correct 16 ms 28500 KB Output is correct
5 Correct 15 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 16 ms 28564 KB Output is correct
9 Correct 16 ms 28520 KB Output is correct
10 Correct 15 ms 28628 KB Output is correct
11 Correct 15 ms 28500 KB Output is correct
12 Correct 15 ms 28500 KB Output is correct
13 Correct 16 ms 28480 KB Output is correct
14 Correct 15 ms 28440 KB Output is correct
15 Correct 15 ms 28432 KB Output is correct
16 Correct 15 ms 28500 KB Output is correct
17 Correct 16 ms 28560 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28504 KB Output is correct
2 Correct 18 ms 28500 KB Output is correct
3 Correct 1256 ms 166148 KB Output is correct
4 Correct 1029 ms 172900 KB Output is correct
5 Correct 620 ms 153396 KB Output is correct
6 Correct 541 ms 138164 KB Output is correct
7 Correct 615 ms 153460 KB Output is correct
8 Correct 1665 ms 204620 KB Output is correct
9 Correct 792 ms 151816 KB Output is correct
10 Correct 1463 ms 229912 KB Output is correct
11 Correct 528 ms 100960 KB Output is correct
12 Correct 354 ms 75072 KB Output is correct
13 Correct 1233 ms 203764 KB Output is correct
14 Correct 234 ms 74536 KB Output is correct
15 Correct 296 ms 76264 KB Output is correct
16 Correct 302 ms 77236 KB Output is correct
17 Correct 270 ms 75980 KB Output is correct
18 Correct 370 ms 87272 KB Output is correct
19 Correct 22 ms 30816 KB Output is correct
20 Correct 102 ms 51960 KB Output is correct
21 Correct 276 ms 73376 KB Output is correct
22 Correct 308 ms 75088 KB Output is correct
23 Correct 277 ms 89824 KB Output is correct
24 Correct 267 ms 75848 KB Output is correct
25 Correct 312 ms 75532 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 47200 KB Output is correct
2 Incorrect 422 ms 122720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 47200 KB Output is correct
2 Incorrect 422 ms 122720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 28372 KB Output is correct
2 Correct 16 ms 28416 KB Output is correct
3 Correct 16 ms 28500 KB Output is correct
4 Correct 16 ms 28500 KB Output is correct
5 Correct 15 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 16 ms 28564 KB Output is correct
9 Correct 16 ms 28520 KB Output is correct
10 Correct 15 ms 28628 KB Output is correct
11 Correct 15 ms 28500 KB Output is correct
12 Correct 15 ms 28500 KB Output is correct
13 Correct 16 ms 28480 KB Output is correct
14 Correct 15 ms 28440 KB Output is correct
15 Correct 15 ms 28432 KB Output is correct
16 Correct 15 ms 28500 KB Output is correct
17 Correct 16 ms 28560 KB Output is correct
18 Correct 15 ms 28504 KB Output is correct
19 Correct 18 ms 28500 KB Output is correct
20 Correct 1256 ms 166148 KB Output is correct
21 Correct 1029 ms 172900 KB Output is correct
22 Correct 620 ms 153396 KB Output is correct
23 Correct 541 ms 138164 KB Output is correct
24 Correct 615 ms 153460 KB Output is correct
25 Correct 1665 ms 204620 KB Output is correct
26 Correct 792 ms 151816 KB Output is correct
27 Correct 1463 ms 229912 KB Output is correct
28 Correct 528 ms 100960 KB Output is correct
29 Correct 354 ms 75072 KB Output is correct
30 Correct 1233 ms 203764 KB Output is correct
31 Correct 234 ms 74536 KB Output is correct
32 Correct 296 ms 76264 KB Output is correct
33 Correct 302 ms 77236 KB Output is correct
34 Correct 270 ms 75980 KB Output is correct
35 Correct 370 ms 87272 KB Output is correct
36 Correct 22 ms 30816 KB Output is correct
37 Correct 102 ms 51960 KB Output is correct
38 Correct 276 ms 73376 KB Output is correct
39 Correct 308 ms 75088 KB Output is correct
40 Correct 277 ms 89824 KB Output is correct
41 Correct 267 ms 75848 KB Output is correct
42 Correct 312 ms 75532 KB Output is correct
43 Correct 98 ms 47200 KB Output is correct
44 Incorrect 422 ms 122720 KB Output isn't correct
45 Halted 0 ms 0 KB -