oj.uz

Submission #1050562

# Submission time Handle Problem Language Result Execution time Memory
1050562 2024-08-09T11:09:12 Z NotLinux Sky Walking (IOI19_walk) C++17
15 / 100
 935 ms 679864 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(0 , N , X[i+1] - X[i]);
			segt_down.add(0 , 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 344 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 344 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 78 ms 4184 KB Output is correct
2 Correct 836 ms 401872 KB Output is correct
3 Correct 771 ms 401936 KB Output is correct
4 Correct 853 ms 410024 KB Output is correct
5 Correct 884 ms 409804 KB Output is correct
6 Correct 825 ms 409616 KB Output is correct
7 Correct 369 ms 210028 KB Output is correct
8 Correct 719 ms 412120 KB Output is correct
9 Correct 697 ms 411996 KB Output is correct
10 Correct 331 ms 30800 KB Output is correct
11 Correct 8 ms 4772 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 4184 KB Output is correct
2 Correct 836 ms 401872 KB Output is correct
3 Correct 771 ms 401936 KB Output is correct
4 Correct 853 ms 410024 KB Output is correct
5 Correct 884 ms 409804 KB Output is correct
6 Correct 825 ms 409616 KB Output is correct
7 Correct 369 ms 210028 KB Output is correct
8 Correct 719 ms 412120 KB Output is correct
9 Correct 697 ms 411996 KB Output is correct
10 Correct 331 ms 30800 KB Output is correct
11 Correct 8 ms 4772 KB Output is correct
12 Correct 806 ms 414464 KB Output is correct
13 Correct 918 ms 486436 KB Output is correct
14 Correct 921 ms 454860 KB Output is correct
15 Correct 485 ms 140560 KB Output is correct
16 Correct 596 ms 338140 KB Output is correct
17 Correct 603 ms 338100 KB Output is correct
18 Correct 447 ms 140864 KB Output is correct
19 Correct 614 ms 338088 KB Output is correct
20 Correct 502 ms 345236 KB Output is correct
21 Correct 23 ms 20392 KB Output is correct
22 Correct 600 ms 365928 KB Output is correct
23 Correct 595 ms 371044 KB Output is correct
24 Correct 617 ms 381516 KB Output is correct
25 Correct 648 ms 474868 KB Output is correct
26 Correct 674 ms 424568 KB Output is correct
27 Correct 935 ms 470796 KB Output is correct
28 Correct 883 ms 479036 KB Output is correct
29 Correct 867 ms 487620 KB Output is correct
30 Correct 471 ms 344428 KB Output is correct
31 Correct 918 ms 679864 KB Output is correct
32 Correct 306 ms 21580 KB Output is correct
33 Incorrect 314 ms 23728 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 344 KB Output isn't correct
2 Halted 0 ms 0 KB -