oj.uz

Submission #838069

# Submission time Handle Problem Language Result Execution time Memory
838069 2023-08-26T07:40:58 Z penguinman Sky Walking (IOI19_walk) C++17
33 / 100
 664 ms 72508 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]], M)-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 1 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 414 ms 29580 KB Output is correct
3 Correct 358 ms 33072 KB Output is correct
4 Correct 429 ms 45972 KB Output is correct
5 Correct 440 ms 50368 KB Output is correct
6 Correct 468 ms 48172 KB Output is correct
7 Correct 187 ms 29816 KB Output is correct
8 Correct 354 ms 48676 KB Output is correct
9 Correct 392 ms 50436 KB Output is correct
10 Correct 206 ms 35148 KB Output is correct
11 Correct 13 ms 5716 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4948 KB Output is correct
2 Correct 414 ms 29580 KB Output is correct
3 Correct 358 ms 33072 KB Output is correct
4 Correct 429 ms 45972 KB Output is correct
5 Correct 440 ms 50368 KB Output is correct
6 Correct 468 ms 48172 KB Output is correct
7 Correct 187 ms 29816 KB Output is correct
8 Correct 354 ms 48676 KB Output is correct
9 Correct 392 ms 50436 KB Output is correct
10 Correct 206 ms 35148 KB Output is correct
11 Correct 13 ms 5716 KB Output is correct
12 Correct 451 ms 34856 KB Output is correct
13 Correct 626 ms 68096 KB Output is correct
14 Correct 613 ms 72508 KB Output is correct
15 Correct 243 ms 31004 KB Output is correct
16 Correct 302 ms 55412 KB Output is correct
17 Correct 307 ms 55316 KB Output is correct
18 Correct 209 ms 30888 KB Output is correct
19 Correct 352 ms 55380 KB Output is correct
20 Correct 287 ms 53780 KB Output is correct
21 Correct 71 ms 33984 KB Output is correct
22 Correct 395 ms 56068 KB Output is correct
23 Correct 329 ms 55620 KB Output is correct
24 Correct 381 ms 54932 KB Output is correct
25 Correct 388 ms 61488 KB Output is correct
26 Correct 351 ms 57652 KB Output is correct
27 Correct 664 ms 71988 KB Output is correct
28 Correct 546 ms 67608 KB Output is correct
29 Correct 641 ms 70208 KB Output is correct
30 Correct 282 ms 54020 KB Output is correct
31 Correct 565 ms 72112 KB Output is correct
32 Correct 149 ms 27064 KB Output is correct
33 Correct 154 ms 29588 KB Output is correct
34 Correct 224 ms 34324 KB Output is correct
35 Correct 206 ms 34192 KB Output is correct
36 Correct 168 ms 31736 KB Output is correct
37 Correct 72 ms 20612 KB Output is correct
38 Correct 84 ms 25676 KB Output is correct
39 Correct 219 ms 37332 KB Output is correct
40 Correct 155 ms 25156 KB Output is correct
41 Correct 78 ms 22208 KB Output is correct

Subtask #5
0 / 43.0

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