oj.uz

Submission #1050791

# Submission time Handle Problem Language Result Execution time Memory
1050791 2024-08-09T14:34:20 Z NotLinux Sky Walking (IOI19_walk) C++17
15 / 100
 1061 ms 688844 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){
			if(tree[ind].val != inf)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) {
	const int tar = 2036;
	int bruh0 = 0 , bruh1 = 0;
	for(int i = 0;i<sz(X);i++){
		if(X[i] == tar){
			bruh0 = H[i];
			// cout << X[i] << " - height : " << H[i] << endl;
		}
	}
	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);
	map < int , int > fuck2;
	auto merge = [&](vector < long long > &a , vector < long long > &b){
		if(sz(a) > sz(b))swap(a,b);
		for(auto itr : a)b.push_back(itr);
		a.clear();
	};
	for(long long i = 0;i<sz(X);i++){
		// bool is_reached = (segt_top.query(0 , H[i]) != inf) or (segt_down.query(0 , H[i]) != inf);
		bool is_reached = 1;
		if(is_reached){
			vector < pair < int , long long > > make_updates;
			// cout << "X : " << X[i] << " " << H[i] << endl;
			for(auto itr : range_start[i]){
				fuck2[Y[itr]]++;
				long long segres1 = segt_top.query(Y[itr] , H[i]) , segres2 = segt_down.query(0 , Y[itr]);
				if(segres1 != inf or segres2 != inf){
					long long min_distance = min(segt_top.query(Y[itr] , H[i]) - Y[itr], segt_down.query(0 , Y[itr]) + Y[itr]);
					// cout << "new edge : " << X[i] << " : " << L[itr] << " " << R[itr] << " " << Y[itr] << " : " << min_distance << endl;
					// cout << "res : " << segt_top.query(Y[itr] , H[i]) << " , " << segt_down.query(0 , Y[itr]) << endl;
					make_updates.push_back({itr , min_distance});
				}
				// else cout << "failed : " << L[itr] << " " << R[itr] << " " << Y[itr] << endl;
			}
			for(long long j = 0;j<sz(make_updates);j++){
				segt_top.set(Y[make_updates[j].first] , make_updates[j].second + Y[make_updates[j].first]);
				segt_down.set(Y[make_updates[j].first] , make_updates[j].second - Y[make_updates[j].first]);
			}
			if(i != (sz(X)-1)){
				for(auto itr : range_end[i]){
					fuck2[Y[itr]]--;
					if(fuck2[Y[itr]] == 0){
						segt_top.set(Y[itr] , inf);
						segt_down.set(Y[itr] , inf);
						// cout << "SETTED " << Y[itr] << " to inf" << endl;
					}
				}
			}
			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 << "starts : ";for(auto itr : range_start[i])cout << R[itr] << "," << Y[itr] << "," << fuck2[Y[itr]] << "   ";cout << endl;
			// cout << "ends : ";for(auto itr : range_end[i])cout << L[itr] << "," << Y[itr] << "," << fuck2[Y[itr]] << "   ";cout << endl;
			// cout << "minimum : " << segt_top.query(0 , H[i]) << " , " << segt_down.query(0 , H[i]) << endl;
			// if(segt_top.query(0 , N) >= inf and sz(range_start[i]) > 0 and X[i] != 2043 and X[i] != 2044 and X[i] != 2045 and X[i] != 2046 and X[i] != 2047 and X[i] != 2048 and X[i] != 2049 and X[i] != 2050 and X[i] != 2051 and X[i] != 2052){
			// 	cout << "stop : " << X[i] << endl;
			// 	return 0ll;
			// }
			// else cout << "continue : " << X[i] << " , " << (segt_top.query(0 , N) < inf) << endl;
		}
		else{
			if(i != (sz(X)-1))merge(range_start[i] , range_start[i+1]);
		}
	}
	long long ret = segt_top.query(0 , H[sz(H) - 1]); 
	if(ret < inf)return ret;
	else return -1;
}

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:92:6: warning: variable 'bruh0' set but not used [-Wunused-but-set-variable]
   92 |  int bruh0 = 0 , bruh1 = 0;
      |      ^~~~~
walk.cpp:92:18: warning: unused variable 'bruh1' [-Wunused-variable]
   92 |  int bruh0 = 0 , bruh1 = 0;
      |                  ^~~~~

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 79 ms 3852 KB Output is correct
2 Correct 937 ms 402428 KB Output is correct
3 Correct 886 ms 406292 KB Output is correct
4 Correct 904 ms 411408 KB Output is correct
5 Correct 951 ms 410184 KB Output is correct
6 Correct 850 ms 412236 KB Output is correct
7 Correct 348 ms 210100 KB Output is correct
8 Correct 730 ms 413648 KB Output is correct
9 Correct 734 ms 413420 KB Output is correct
10 Correct 314 ms 31044 KB Output is correct
11 Correct 8 ms 4188 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3852 KB Output is correct
2 Correct 937 ms 402428 KB Output is correct
3 Correct 886 ms 406292 KB Output is correct
4 Correct 904 ms 411408 KB Output is correct
5 Correct 951 ms 410184 KB Output is correct
6 Correct 850 ms 412236 KB Output is correct
7 Correct 348 ms 210100 KB Output is correct
8 Correct 730 ms 413648 KB Output is correct
9 Correct 734 ms 413420 KB Output is correct
10 Correct 314 ms 31044 KB Output is correct
11 Correct 8 ms 4188 KB Output is correct
12 Correct 863 ms 419508 KB Output is correct
13 Correct 795 ms 488380 KB Output is correct
14 Correct 1061 ms 456468 KB Output is correct
15 Correct 500 ms 139360 KB Output is correct
16 Correct 610 ms 337140 KB Output is correct
17 Correct 653 ms 338336 KB Output is correct
18 Correct 527 ms 139464 KB Output is correct
19 Correct 626 ms 337268 KB Output is correct
20 Correct 565 ms 345004 KB Output is correct
21 Correct 31 ms 18204 KB Output is correct
22 Correct 545 ms 369920 KB Output is correct
23 Correct 476 ms 375168 KB Output is correct
24 Correct 522 ms 385500 KB Output is correct
25 Correct 527 ms 479912 KB Output is correct
26 Correct 510 ms 434604 KB Output is correct
27 Correct 998 ms 478440 KB Output is correct
28 Correct 740 ms 486400 KB Output is correct
29 Correct 998 ms 495236 KB Output is correct
30 Correct 480 ms 349168 KB Output is correct
31 Correct 987 ms 688844 KB Output is correct
32 Correct 294 ms 26684 KB Output is correct
33 Incorrect 340 ms 26036 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 -