oj.uz

Submission #303317

# Submission time Handle Problem Language Result Execution time Memory
303317 2020-09-20T07:57:28 Z ainta Sky Walking (IOI19_walk) C++17
15 / 100
 223 ms 23020 KB 
#include "walk.h"
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;
#define N_ 101000
#define SZ 131072

vector<ll>X, Y;
struct Seg{
	int ed, y;
};
vector<Seg>LeftSeg[N_], RightSeg[N_];
int n, m, H[N_];
ll INF = 1e18;

struct Tree{
	ll IT[SZ+SZ];
	void init(){
		for(int i=0;i<SZ+SZ;i++)IT[i]=INF;
	}
	void Put(int y, ll d){
		y+=SZ;
		IT[y] = d;
		while(y!=1){
			y>>=1;
			IT[y]=min(IT[y*2],IT[y*2+1]);
		}
	}
	ll Min(int b, int e){
		ll r=INF;
		b+=SZ,e+=SZ;
		while(b<=e){
			r=min(r,min(IT[b],IT[e]));
			b=(b+1)>>1,e=(e-1)>>1;
		}
		return r;
	}
}T1, T2;

ll U[N_];

long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	int i;
	for(auto &t : x)X.push_back(t);
	vector<pii>ordY;
	n = x.size();
	m = l.size();
	for(i=0;i<m;i++){
		ordY.push_back({y[i],i});
	}
	sort(ordY.begin(),ordY.end());
	for(i=0;i<m;i++){
		Y.push_back(ordY[i].first);
		int t = ordY[i].second;
		RightSeg[l[t]].push_back({r[t], i});
		LeftSeg[r[t]].push_back({l[t], i});
	}
	for(i=0;i<n;i++){
		H[i]=lower_bound(Y.begin(),Y.end(),h[i]+1)-Y.begin();
		H[i]--;
	}
	if(s>g)swap(s,g);

	T1.init();
	T2.init();
	vector<pll>Save;
	for(i=0;i<=s;i++){
		for(auto &t : RightSeg[i]){
			if(t.ed >= s && t.y <= H[s]){
				T1.Put(t.y, Y[t.y] + X[i] - Y[t.y]);
				T2.Put(t.y, Y[t.y] + X[i] + Y[t.y]);
				Save.push_back({t.y, Y[t.y]});
			}
		}
	}
	for(i=s-1;i>=0;i--){
		for(auto &t: RightSeg[i+1]){
			T1.Put(t.y, INF);
			T2.Put(t.y, INF);
		}
		for(auto &t : LeftSeg[i]){
			ll d = min(T1.Min(0,t.y) - X[i] + Y[t.y], T2.Min(t.y,H[i]) - X[i] - Y[t.y]);
			T1.Put(t.y, d + X[i] - Y[t.y]);
			T2.Put(t.y, d + X[i] + Y[t.y]);
		}
		for(auto &t : RightSeg[i]){
			if(t.ed > s && t.y > H[s]){
				ll d = min(T1.Min(0,t.y) - X[i] + Y[t.y], T2.Min(t.y,H[i]) - X[i] - Y[t.y]);
				Save.push_back({t.y, d + X[s] - X[i]});
			}
		}
	}
	T1.init();
	T2.init();
	for(auto &t : Save){
		T1.Put(t.first, t.second - X[s] - Y[t.first]);
		T2.Put(t.first, t.second - X[s] + Y[t.first]);
	}
	ll res = 1e18;
	for(i=s+1;i<=g;i++){
		for(auto &t : LeftSeg[i-1]){
			T1.Put(t.y, INF);
			T2.Put(t.y, INF);
		}
		if(i==g){
			res = min(res, T2.Min(0,H[i]) + X[i]);
		}
		for(auto &t : RightSeg[i]){
			ll d = min(T1.Min(0,t.y) + X[i] + Y[t.y], T2.Min(t.y,H[i]) + X[i] - Y[t.y]);
			T1.Put(t.y, d - X[i] - Y[t.y]);
			T2.Put(t.y, d - X[i] + Y[t.y]);
		}
	}
	for(i=0;i<m;i++){
		U[i] = T1.IT[SZ+i] + X[g] + Y[i];
	}
	T1.init();T2.init();
	for(i=0;i<=g;i++){
		for(auto &t : RightSeg[i]){
			if(t.ed > g && t.y <= H[g]){
				T1.Put(t.y, Y[t.y] - X[g] - Y[t.y]);
				T2.Put(t.y, Y[t.y] - X[g] + Y[t.y]);
			}
		}
	}
	int pv = H[g]+1;
	for(i=g+1;i<n;i++){
		for(auto &t : LeftSeg[i-1]){
			T1.Put(t.y, INF);
			T2.Put(t.y, INF);
		}
		while(pv <= H[i]){
			ll d = min(T1.Min(0,pv) + X[i] + Y[pv], T2.Min(pv,H[i]) + X[i] - Y[pv]);
			res = min(res, d + X[i]-X[g] + U[pv]);
			pv++;
		}
		for(auto &t : RightSeg[i]){
			ll d = min(T1.Min(0,t.y) + X[i] + Y[t.y], T2.Min(t.y,H[i]) + X[i] - Y[t.y]);
			T1.Put(t.y, d - X[i] - Y[t.y]);
			T2.Put(t.y, d - X[i] + Y[t.y]);
		}
	}
	if(res>1e16)res=-1;
	return res;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9088 KB Output is correct
2 Correct 7 ms 9216 KB Output is correct
3 Correct 8 ms 9216 KB Output is correct
4 Correct 7 ms 9088 KB Output is correct
5 Correct 7 ms 9216 KB Output is correct
6 Correct 8 ms 9088 KB Output is correct
7 Correct 7 ms 9088 KB Output is correct
8 Correct 8 ms 9216 KB Output is correct
9 Incorrect 7 ms 9088 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9216 KB Output is correct
2 Correct 7 ms 9088 KB Output is correct
3 Correct 147 ms 16876 KB Output is correct
4 Incorrect 214 ms 21992 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 13428 KB Output is correct
2 Correct 108 ms 16364 KB Output is correct
3 Correct 127 ms 16972 KB Output is correct
4 Correct 205 ms 20840 KB Output is correct
5 Correct 184 ms 19920 KB Output is correct
6 Correct 191 ms 20716 KB Output is correct
7 Correct 115 ms 17260 KB Output is correct
8 Correct 198 ms 23020 KB Output is correct
9 Correct 189 ms 21868 KB Output is correct
10 Correct 145 ms 20972 KB Output is correct
11 Correct 22 ms 10744 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 13428 KB Output is correct
2 Correct 108 ms 16364 KB Output is correct
3 Correct 127 ms 16972 KB Output is correct
4 Correct 205 ms 20840 KB Output is correct
5 Correct 184 ms 19920 KB Output is correct
6 Correct 191 ms 20716 KB Output is correct
7 Correct 115 ms 17260 KB Output is correct
8 Correct 198 ms 23020 KB Output is correct
9 Correct 189 ms 21868 KB Output is correct
10 Correct 145 ms 20972 KB Output is correct
11 Correct 22 ms 10744 KB Output is correct
12 Correct 142 ms 16984 KB Output is correct
13 Correct 214 ms 20844 KB Output is correct
14 Correct 188 ms 19948 KB Output is correct
15 Correct 190 ms 20460 KB Output is correct
16 Correct 201 ms 20332 KB Output is correct
17 Correct 210 ms 20328 KB Output is correct
18 Correct 191 ms 20584 KB Output is correct
19 Correct 203 ms 20332 KB Output is correct
20 Correct 125 ms 17004 KB Output is correct
21 Correct 49 ms 12140 KB Output is correct
22 Correct 159 ms 18880 KB Output is correct
23 Correct 162 ms 19304 KB Output is correct
24 Correct 159 ms 19560 KB Output is correct
25 Correct 163 ms 19312 KB Output is correct
26 Correct 154 ms 19944 KB Output is correct
27 Correct 202 ms 20268 KB Output is correct
28 Correct 223 ms 20996 KB Output is correct
29 Correct 215 ms 20848 KB Output is correct
30 Correct 130 ms 17132 KB Output is correct
31 Correct 203 ms 21864 KB Output is correct
32 Correct 153 ms 21092 KB Output is correct
33 Incorrect 160 ms 21864 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9088 KB Output is correct
2 Correct 7 ms 9216 KB Output is correct
3 Correct 8 ms 9216 KB Output is correct
4 Correct 7 ms 9088 KB Output is correct
5 Correct 7 ms 9216 KB Output is correct
6 Correct 8 ms 9088 KB Output is correct
7 Correct 7 ms 9088 KB Output is correct
8 Correct 8 ms 9216 KB Output is correct
9 Incorrect 7 ms 9088 KB Output isn't correct
10 Halted 0 ms 0 KB -