oj.uz

Submission #1050789

# Submission time Handle Problem Language Result Execution time Memory
1050789 2024-08-09T14:31:23 Z NotLinux Sky Walking (IOI19_walk) C++17
15 / 100
 1183 ms 701220 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);
		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 82 ms 3672 KB Output is correct
2 Correct 952 ms 404768 KB Output is correct
3 Correct 877 ms 406516 KB Output is correct
4 Correct 967 ms 415316 KB Output is correct
5 Correct 1014 ms 415252 KB Output is correct
6 Correct 910 ms 415796 KB Output is correct
7 Correct 419 ms 212400 KB Output is correct
8 Correct 777 ms 419312 KB Output is correct
9 Correct 785 ms 416052 KB Output is correct
10 Correct 336 ms 33364 KB Output is correct
11 Correct 47 ms 4188 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 3672 KB Output is correct
2 Correct 952 ms 404768 KB Output is correct
3 Correct 877 ms 406516 KB Output is correct
4 Correct 967 ms 415316 KB Output is correct
5 Correct 1014 ms 415252 KB Output is correct
6 Correct 910 ms 415796 KB Output is correct
7 Correct 419 ms 212400 KB Output is correct
8 Correct 777 ms 419312 KB Output is correct
9 Correct 785 ms 416052 KB Output is correct
10 Correct 336 ms 33364 KB Output is correct
11 Correct 47 ms 4188 KB Output is correct
12 Correct 908 ms 420956 KB Output is correct
13 Correct 365 ms 412964 KB Output is correct
14 Correct 1183 ms 701220 KB Output is correct
15 Correct 541 ms 143176 KB Output is correct
16 Correct 674 ms 362008 KB Output is correct
17 Correct 700 ms 361824 KB Output is correct
18 Correct 524 ms 143096 KB Output is correct
19 Correct 644 ms 361580 KB Output is correct
20 Correct 571 ms 357068 KB Output is correct
21 Incorrect 166 ms 278048 KB Output isn't correct
22 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 -