oj.uz

Submission #1050537

# Submission time Handle Problem Language Result Execution time Memory
1050537 2024-08-09T10:36:31 Z NotLinux Sky Walking (IOI19_walk) C++17
15 / 100
 1018 ms 683952 KB 
#include <bits/stdc++.h>
#include "walk.h"
using namespace std;
#define sz(x) (long long)x.size()
#define all(x) x.begin() , x.end()
const long long N = 1e18 + 7;
const long long inf = 2e18 + 7;
struct Segt{// range add update , range min query , polong long set update
	struct Node{
		long long left , right;
		long long val , lzt;
		Node():left(-1) , right(-1) , val(inf) , lzt(0ll){}
	} dummy;
	vector < Node > tree;
	long long create_node(){
		tree.push_back(dummy);
		return sz(tree) - 1;
	}
	Segt(){
		tree.resize(1);
	}
	void push(long long ind , long long l , long long r){
		if(tree[ind].lzt){
			tree[ind].val += tree[ind].lzt;
			if(tree[ind].left == -1)tree[ind].left = create_node();
			tree[tree[ind].left].lzt += tree[ind].lzt;
			if(tree[ind].right == -1)tree[ind].right = create_node();
			tree[tree[ind].right].lzt += tree[ind].lzt;
			tree[ind].lzt = 0;
		}
	}
	void set(long long ind , long long l , long long r , long long p , long long v){
		push(ind,l,r);
		if(l == r){
			tree[ind].val = v;
			return;			
		}
		long long mid = (l + r) / 2;
		if(tree[ind].left == -1)tree[ind].left = create_node();
		if(tree[ind].right == -1)tree[ind].right = create_node();
		if(mid >= p){
			set(tree[ind].left , l , mid , p , v);
		}
		else{
			set(tree[ind].right , mid+1 , r , p , v);
		}
		push(tree[ind].left , l , mid);
		push(tree[ind].right , mid+1 , r);
		tree[ind].val = min(tree[tree[ind].left].val , tree[tree[ind].right].val);
	}
	void set(long long p , long long v){
		set(0 , 0 , N , p , v);
	}
	void add(long long ind , long long l , long long r , long long ql , long long qr , long long qv){
		push(ind,l,r);
		if(l >= ql and r <= qr){
			tree[ind].lzt += qv;
			push(ind,l,r);
			return;
		}
		else if(l > qr or r < ql){
			return;
		}
		long long mid = (l + r) / 2;
		if(tree[ind].left == -1)tree[ind].left = create_node();
		if(tree[ind].right == -1)tree[ind].right = create_node();
		add(tree[ind].left , l , mid , ql , qr , qv);
		add(tree[ind].right , mid+1 , r , ql , qr , qv);
		tree[ind].val = min(tree[tree[ind].left].val , tree[tree[ind].right].val);
	}
	void add(long long l , long long r , long long v){
		add(0 , 0 , N , l , r , v);
	}
	long long query(long long ind , long long l , long long r , long long ql , long long qr){
		if(ind == -1)return inf;
		push(ind,l,r);
		if(l >= ql and r <= qr){
			return tree[ind].val;
		}
		else if(l > qr or r < ql)return inf;
		else{
			long long mid = (l + r) / 2;
			return min(query(tree[ind].left , l , mid , ql , qr) , query(tree[ind].right , mid+1 , r , ql , qr));
		}
	}
	long long query(long long l , long long r){
		return query(0 , 0 , N , l , r);
	}
};
long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int S, int G) {
	vector < long long > range_start[sz(X)] , range_end[sz(X)];
	for(long long i = 0;i<sz(L);i++){
		range_start[L[i]].push_back(i);
		range_end[R[i]].push_back(i);
	}
	Segt segt_top , segt_down;
	segt_top.set(0 , 0);
	segt_down.set(0 , 0);
	long long ans = inf;
	for(long long i = 0;i<sz(X);i++){
		set < long long > fuck;
		vector < long long > make_updates;
		for(auto itr : range_start[i]){
			// cout << "STARTED : " << L[itr] << " , " << R[itr] << " , " << Y[itr] << endl;
			fuck.insert(Y[itr]);
			long long min_distance = min(segt_top.query(Y[itr] , H[i]) - Y[itr], segt_down.query(0 , Y[itr]) + Y[itr]);
			// cout << "min_distance : " << min_distance << endl;
			make_updates.push_back(min_distance);
		}
		for(long long j = 0;j<sz(range_start[i]);j++){
			segt_top.set(Y[range_start[i][j]] , make_updates[j] + Y[range_start[i][j]]);
			segt_down.set(Y[range_start[i][j]] , make_updates[j] - Y[range_start[i][j]]);
		}
		if(i != (sz(X)-1)){
			for(auto itr : range_end[i]){
				if(fuck.count(Y[itr]) == 0){
					// cout << "ENDED : " << L[itr] << " , " << R[itr] << endl;
					segt_top.set(Y[itr] , inf);
					segt_down.set(Y[itr] , inf);
				}
			}
		}
		if(i == 0){
			segt_top.set(0 , inf);
			segt_down.set(0 , inf);
		}
		if(i != (sz(X)-1)){
			segt_top.add(1 , N , X[i+1] - X[i]);
			segt_down.add(1 , N , X[i+1] - X[i]);
		}
		// cout << "Segt : ";for(long long i = 0;i<=10;i++)cout << segt_top.query(i,i) << " ";cout << endl;
		// cout << X[i] << " : " << segt_top.query(0 , N) << endl;
		// if(segt_top.query(0 , N) >= inf){
		// 	cout << "stop : " << X[i] << endl;
		// 	return 0ll;
		// }
	}
	long long ret = segt_top.query(0 , H[sz(H) - 1]); 
	if(ret < inf)return ret;
	else return -1;
}
// signed main() {
// 	long long n, m;
// 	cin >> n >> m;
// 	vector<long long> x(n), h(n);
// 	for (long long i = 0; i < n; i++)
// 		cin >> x[i] >> h[i];
// 	vector<long long> l(m), r(m), y(m);
// 	for (long long i = 0; i < m; i++)
// 		cin >> l[i] >> r[i] >> y[i];
// 	long long s, g;
// 	cin >> s >> g;
// 	long long result = min_distance(x, h, l, r, y, s, g);
// 	cout << "result : " << result << endl;
// }

Compilation message

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:99:12: warning: unused variable 'ans' [-Wunused-variable]
   99 |  long long ans = inf;
      |            ^~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 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 87 ms 3672 KB Output is correct
2 Correct 752 ms 399544 KB Output is correct
3 Correct 727 ms 401692 KB Output is correct
4 Correct 887 ms 408280 KB Output is correct
5 Correct 905 ms 406452 KB Output is correct
6 Correct 859 ms 408740 KB Output is correct
7 Correct 428 ms 208316 KB Output is correct
8 Correct 794 ms 410380 KB Output is correct
9 Correct 750 ms 409392 KB Output is correct
10 Correct 418 ms 28476 KB Output is correct
11 Correct 66 ms 4004 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 3672 KB Output is correct
2 Correct 752 ms 399544 KB Output is correct
3 Correct 727 ms 401692 KB Output is correct
4 Correct 887 ms 408280 KB Output is correct
5 Correct 905 ms 406452 KB Output is correct
6 Correct 859 ms 408740 KB Output is correct
7 Correct 428 ms 208316 KB Output is correct
8 Correct 794 ms 410380 KB Output is correct
9 Correct 750 ms 409392 KB Output is correct
10 Correct 418 ms 28476 KB Output is correct
11 Correct 66 ms 4004 KB Output is correct
12 Correct 756 ms 416920 KB Output is correct
13 Correct 939 ms 484136 KB Output is correct
14 Correct 941 ms 452556 KB Output is correct
15 Correct 538 ms 138364 KB Output is correct
16 Correct 674 ms 335896 KB Output is correct
17 Correct 686 ms 335832 KB Output is correct
18 Correct 534 ms 138372 KB Output is correct
19 Correct 657 ms 335956 KB Output is correct
20 Correct 549 ms 343408 KB Output is correct
21 Correct 145 ms 18860 KB Output is correct
22 Correct 671 ms 366488 KB Output is correct
23 Correct 647 ms 368952 KB Output is correct
24 Correct 663 ms 379528 KB Output is correct
25 Correct 703 ms 472752 KB Output is correct
26 Correct 746 ms 428824 KB Output is correct
27 Correct 1018 ms 473268 KB Output is correct
28 Correct 914 ms 481084 KB Output is correct
29 Correct 962 ms 489960 KB Output is correct
30 Correct 555 ms 347676 KB Output is correct
31 Correct 999 ms 683952 KB Output is correct
32 Correct 401 ms 22440 KB Output is correct
33 Incorrect 469 ms 24256 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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