oj.uz

Submission #1050648

# Submission time Handle Problem Language Result Execution time Memory
1050648 2024-08-09T12:05:50 Z NotLinux Sky Walking (IOI19_walk) C++17
15 / 100
 1082 ms 682108 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 = 1e18 + 7;
const long long inf = 2e18 + 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) {
	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);
	for(long long i = 0;i<sz(X);i++){
		set < long long > fuck;
		vector < long long > make_updates;
		for(auto itr : range_start[i]){
			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]);
			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){
					segt_top.set(Y[itr] , inf);
					segt_down.set(Y[itr] , inf);
				}
			}
		}
		if(i == 0 and fuck.count(0) == 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]);
		}
	}
	long long ret = segt_top.query(0 , H[sz(H) - 1]); 
	if(ret < inf)return ret;
	else return -1;
}

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 112 ms 4440 KB Output is correct
2 Correct 964 ms 402108 KB Output is correct
3 Correct 912 ms 402612 KB Output is correct
4 Correct 991 ms 410672 KB Output is correct
5 Correct 1020 ms 410792 KB Output is correct
6 Correct 938 ms 410084 KB Output is correct
7 Correct 437 ms 211480 KB Output is correct
8 Correct 869 ms 413900 KB Output is correct
9 Correct 840 ms 411244 KB Output is correct
10 Correct 408 ms 29764 KB Output is correct
11 Correct 9 ms 4516 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 4440 KB Output is correct
2 Correct 964 ms 402108 KB Output is correct
3 Correct 912 ms 402612 KB Output is correct
4 Correct 991 ms 410672 KB Output is correct
5 Correct 1020 ms 410792 KB Output is correct
6 Correct 938 ms 410084 KB Output is correct
7 Correct 437 ms 211480 KB Output is correct
8 Correct 869 ms 413900 KB Output is correct
9 Correct 840 ms 411244 KB Output is correct
10 Correct 408 ms 29764 KB Output is correct
11 Correct 9 ms 4516 KB Output is correct
12 Correct 947 ms 414928 KB Output is correct
13 Correct 1069 ms 486544 KB Output is correct
14 Correct 1010 ms 454940 KB Output is correct
15 Correct 581 ms 140628 KB Output is correct
16 Correct 733 ms 338364 KB Output is correct
17 Correct 729 ms 338248 KB Output is correct
18 Correct 587 ms 140516 KB Output is correct
19 Correct 739 ms 338036 KB Output is correct
20 Correct 594 ms 346928 KB Output is correct
21 Correct 25 ms 21168 KB Output is correct
22 Correct 723 ms 366160 KB Output is correct
23 Correct 723 ms 371304 KB Output is correct
24 Correct 712 ms 381876 KB Output is correct
25 Correct 764 ms 475036 KB Output is correct
26 Correct 786 ms 426996 KB Output is correct
27 Correct 1061 ms 473240 KB Output is correct
28 Correct 970 ms 481248 KB Output is correct
29 Correct 998 ms 489888 KB Output is correct
30 Correct 529 ms 345832 KB Output is correct
31 Correct 1082 ms 682108 KB Output is correct
32 Correct 429 ms 22860 KB Output is correct
33 Incorrect 452 ms 26048 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 -