oj.uz

Submission #838071

# Submission time Handle Problem Language Result Execution time Memory
838071 2023-08-26T07:42:11 Z penguinman Sky Walking (IOI19_walk) C++17
15 / 100
 719 ms 68528 KB 
#include "walk.h"
#include <bits/stdc++.h>

#ifndef EVAL
#include "grader.cpp"
#endif

using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()

constexpr ll inf = (1ll<<60);

ll solve_subtask_1_2(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g){

}

template<typename T>
struct li_chao_tree{
	ll N;
	vector<std::pair<T,T>> lines;
	vector<T> x;
	std::map<ll,ll> rev;
	li_chao_tree(vector<T> X, T xINF){
		N = 1;
		while(N <= x.size()) N *= 2;
		lines.resize(2*N, mp(0,inf));
		x.resize(N);
		rep(i,0,N){
			if(i < X.size()){
				x[i] = X[i];
				rev[x[i]] = i;
			}
			else x[i] = xINF;
		}
	}
	ll ID(T X){
		return rev[X];
	}
	T value(std::pair<T,T> line, T X){
		return line.first*X+line.second;
	}
	void add_segment(ll a, ll b, std::pair<T,T> line, ll now = 1, ll l = 0, ll r = -1){
		if(r == -1) r = N;
		if(b <= l || r <= a) return;
		if(a <= l && r <= b){
			if(N <= now){
				if(value(lines[now], x[l]) > value(line, x[l])) lines[now] = line;
				return;
			}
			ll m = (l+r)/2;
			bool left = (value(lines[now],x[l]) < value(line, x[l]));
			bool mid = (value(lines[now],x[m]) < value(line, x[m]));
			bool right = (value(lines[now],x[r]) < value(line, x[r]));
			if(left && mid && right){
				std::swap(line, lines[now]);
				return;
			}
			if(!left && !mid && !right){
				return;
			}
			if(left && mid){
				std::swap(line, lines[now]);
				add_segment(a,b,line,now*2+1,m,r);
				return;
			}
			if(mid && right){
				std::swap(line, lines[now]);
				add_segment(a,b,line,now*2,l,m);
				return;
			}
			if(left){
				add_segment(a,b,line,now*2,l,m);
				return;
			}
			if(right){
				add_segment(a,b,line,now*2+1,m,r);
				return;
			}
		}
		else{
			add_segment(a,b,line,now*2,l,(l+r)/2);
			add_segment(a,b,line,now*2+1,(l+r)/2,r);
		}
	}
	T calc(ll idx, T X){
		T ret = inf;
		idx += N;
		while(idx){
			ret = std::min(idx, value(lines[idx], X));
			idx /= 2;
		}
		return ret;
	}
};

template<typename T>
struct segment_tree{
	ll N;
	vector<T> node;
	ll valINF;
	segment_tree(int n, ll valINF_): valINF(valINF_){
		N = 1;
		while(N <= n) N *= 2;
		node.resize(2*N, valINF);
	}
	void set(ll idx, T val){
		idx += N;
		node[idx] = val;
		idx /= 2;
		while(idx){
			node[idx] = compare(node[idx*2], node[idx*2+1]);
			idx /= 2;
		}
	}
	T calc(ll a, ll b, ll now = 1, ll l = 0, ll r = -1){
		if(r == -1) r = N;
		if(b <= l || r <= a) return valINF;
		if(a <= l && r <= b) return node[now];
		return compare(calc(a,b,now*2,l,(l+r)/2), calc(a,b,now*2+1,(l+r)/2,r));
	}
	T compare(T l, T r){
		return std::min(l, r);
	}
};

void dec(std::map<ll,ll> &map, ll el){
	map[el]--;
	if(map[el] == 0) map.erase(el);
}


ll solve_subtask_3_4(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g){
	ll N = x.size();
	vi y_mem;
	std::map<ll,ll> mem;
	ll M = 0;
	{
		mem[0] = 0;
		for(auto el: h) mem[el] = 0;
		for(auto el: y) mem[el] = 0;
		for(auto &el: mem){
			y_mem.pb(el.first);
			el.second = M++;
		}
	}

	segment_tree<ll> left(M, inf), right(M, inf);

	vector<std::map<ll,ll>> value(M);
	rep(i,0,M) value[i][inf] = 1;

	vii erase_idx(N), erase_val(N);

	vii add(N);
	rep(i,0,l.size()){
		add[l[i]].pb(i);
	}

	rep(t,0,N){
		for(auto i: add[t]){
			ll val = left.calc(0, mem[y[i]]+1)+y[i];
			val = std::min(val, right.calc(mem[y[i]], mem[h[t]]+1)-y[i]);
			if(t == 0) val = y[i];
			value[mem[y[i]]][val]++;
			left.set(mem[y[i]], (*value[mem[y[i]]].begin()).first-y[i]);
			right.set(mem[y[i]], (*value[mem[y[i]]].begin()).first+y[i]);
			erase_idx[r[i]].pb(y[i]);
			erase_val[r[i]].pb(val);
		}
		if(t == N-1) break;
		rep(i,0,erase_idx[t].size()){
			ll Y = erase_idx[t][i];
			ll V = erase_val[t][i];
			dec(value[mem[Y]], V);
			left.set(mem[Y], (*value[mem[Y]].begin()).first-Y);
			right.set(mem[Y], (*value[mem[Y]].begin()).first+Y);
		}
	}
	ll ans = right.calc(0,M)+x[N-1]-x[0];
	if(ans >= inf/2) ans = -1;
	return ans;
}

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) {
	ll N = x.size();
	//if(s == 0 && g == N-1) 
	return solve_subtask_3_4(x,h,l,r,y,s,g);
	return -1;
}

Compilation message

walk.cpp: In function 'll solve_subtask_1_2(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:30:1: warning: no return statement in function returning non-void [-Wreturn-type]
   30 | }
      | ^
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:200:5: warning: unused variable 'N' [-Wunused-variable]
  200 |  ll N = x.size();
      |     ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4948 KB Output is correct
2 Correct 395 ms 29512 KB Output is correct
3 Correct 372 ms 30912 KB Output is correct
4 Correct 490 ms 41828 KB Output is correct
5 Correct 461 ms 46488 KB Output is correct
6 Correct 487 ms 44092 KB Output is correct
7 Correct 204 ms 26912 KB Output is correct
8 Correct 377 ms 44664 KB Output is correct
9 Correct 434 ms 46308 KB Output is correct
10 Correct 195 ms 31692 KB Output is correct
11 Correct 10 ms 4948 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4948 KB Output is correct
2 Correct 395 ms 29512 KB Output is correct
3 Correct 372 ms 30912 KB Output is correct
4 Correct 490 ms 41828 KB Output is correct
5 Correct 461 ms 46488 KB Output is correct
6 Correct 487 ms 44092 KB Output is correct
7 Correct 204 ms 26912 KB Output is correct
8 Correct 377 ms 44664 KB Output is correct
9 Correct 434 ms 46308 KB Output is correct
10 Correct 195 ms 31692 KB Output is correct
11 Correct 10 ms 4948 KB Output is correct
12 Correct 414 ms 32780 KB Output is correct
13 Correct 661 ms 63992 KB Output is correct
14 Correct 719 ms 68528 KB Output is correct
15 Correct 217 ms 27032 KB Output is correct
16 Correct 356 ms 51400 KB Output is correct
17 Correct 354 ms 51288 KB Output is correct
18 Correct 220 ms 27076 KB Output is correct
19 Correct 341 ms 51260 KB Output is correct
20 Correct 327 ms 50864 KB Output is correct
21 Correct 72 ms 32120 KB Output is correct
22 Correct 376 ms 52400 KB Output is correct
23 Correct 333 ms 51828 KB Output is correct
24 Correct 355 ms 51280 KB Output is correct
25 Correct 381 ms 57796 KB Output is correct
26 Correct 361 ms 53928 KB Output is correct
27 Correct 677 ms 68052 KB Output is correct
28 Correct 585 ms 63620 KB Output is correct
29 Correct 652 ms 66284 KB Output is correct
30 Correct 307 ms 51044 KB Output is correct
31 Correct 624 ms 68060 KB Output is correct
32 Correct 193 ms 24000 KB Output is correct
33 Incorrect 152 ms 26312 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -