oj.uz

Submission #1050534

# Submission time Handle Problem Language Result Execution time Memory
1050534 2024-08-09T10:35:05 Z NotLinux Sky Walking (IOI19_walk) C++17
15 / 100
 827 ms 685500 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 = 1e9 + 7;
const long long inf = 1e18 + 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 0 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 0 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 57 ms 3676 KB Output is correct
2 Correct 647 ms 401876 KB Output is correct
3 Correct 599 ms 403220 KB Output is correct
4 Correct 705 ms 411452 KB Output is correct
5 Correct 728 ms 412600 KB Output is correct
6 Correct 671 ms 412532 KB Output is correct
7 Correct 306 ms 212896 KB Output is correct
8 Correct 563 ms 414860 KB Output is correct
9 Correct 608 ms 414268 KB Output is correct
10 Correct 239 ms 33552 KB Output is correct
11 Correct 36 ms 4768 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 3676 KB Output is correct
2 Correct 647 ms 401876 KB Output is correct
3 Correct 599 ms 403220 KB Output is correct
4 Correct 705 ms 411452 KB Output is correct
5 Correct 728 ms 412600 KB Output is correct
6 Correct 671 ms 412532 KB Output is correct
7 Correct 306 ms 212896 KB Output is correct
8 Correct 563 ms 414860 KB Output is correct
9 Correct 608 ms 414268 KB Output is correct
10 Correct 239 ms 33552 KB Output is correct
11 Correct 36 ms 4768 KB Output is correct
12 Correct 642 ms 416740 KB Output is correct
13 Correct 827 ms 488048 KB Output is correct
14 Correct 801 ms 456552 KB Output is correct
15 Correct 348 ms 141920 KB Output is correct
16 Correct 477 ms 339904 KB Output is correct
17 Correct 498 ms 339676 KB Output is correct
18 Correct 368 ms 141812 KB Output is correct
19 Correct 544 ms 340044 KB Output is correct
20 Correct 422 ms 345708 KB Output is correct
21 Correct 89 ms 21672 KB Output is correct
22 Correct 463 ms 369868 KB Output is correct
23 Correct 469 ms 372824 KB Output is correct
24 Correct 468 ms 383424 KB Output is correct
25 Correct 522 ms 476312 KB Output is correct
26 Correct 532 ms 430540 KB Output is correct
27 Correct 760 ms 474832 KB Output is correct
28 Correct 676 ms 482832 KB Output is correct
29 Correct 704 ms 491724 KB Output is correct
30 Correct 382 ms 347208 KB Output is correct
31 Correct 757 ms 685500 KB Output is correct
32 Correct 220 ms 24400 KB Output is correct
33 Incorrect 230 ms 24836 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 348 KB Output isn't correct
2 Halted 0 ms 0 KB -