oj.uz

Submission #1050796

# Submission time Handle Problem Language Result Execution time Memory
1050796 2024-08-09T14:36:07 Z NotLinux Sky Walking (IOI19_walk) C++17
15 / 100
 1111 ms 697636 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]){
				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

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 1 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 3676 KB Output is correct
2 Correct 848 ms 404136 KB Output is correct
3 Correct 808 ms 404996 KB Output is correct
4 Correct 887 ms 411256 KB Output is correct
5 Correct 912 ms 410452 KB Output is correct
6 Correct 837 ms 411612 KB Output is correct
7 Correct 358 ms 210284 KB Output is correct
8 Correct 755 ms 414928 KB Output is correct
9 Correct 727 ms 412500 KB Output is correct
10 Correct 330 ms 31824 KB Output is correct
11 Correct 24 ms 3616 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 3676 KB Output is correct
2 Correct 848 ms 404136 KB Output is correct
3 Correct 808 ms 404996 KB Output is correct
4 Correct 887 ms 411256 KB Output is correct
5 Correct 912 ms 410452 KB Output is correct
6 Correct 837 ms 411612 KB Output is correct
7 Correct 358 ms 210284 KB Output is correct
8 Correct 755 ms 414928 KB Output is correct
9 Correct 727 ms 412500 KB Output is correct
10 Correct 330 ms 31824 KB Output is correct
11 Correct 24 ms 3616 KB Output is correct
12 Correct 839 ms 417920 KB Output is correct
13 Correct 375 ms 409748 KB Output is correct
14 Correct 1111 ms 697636 KB Output is correct
15 Correct 447 ms 139360 KB Output is correct
16 Correct 632 ms 357728 KB Output is correct
17 Correct 649 ms 357772 KB Output is correct
18 Correct 458 ms 139520 KB Output is correct
19 Correct 631 ms 357744 KB Output is correct
20 Correct 573 ms 354212 KB Output is correct
21 Incorrect 162 ms 275360 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 -