Submission #1050796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050796		NotLinux	Sky Walking (IOI19_walk)	C++17	15 / 100	1111 ms	697636 KiB

walk

#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]){
				if(R[itr] < i)continue;
				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 (stderr)

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
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43