oj.uz

Submission #1067140

# Submission time Handle Problem Language Result Execution time Memory
1067140 2024-08-20T11:56:33 Z jamjanek Sky Walking (IOI19_walk) C++14
33 / 100
 721 ms 164076 KB 
#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
struct node{long long val, l,r;};
vector<node>pre,suf;
const long long base = 1<<30;
void dodaj_synow(vector<node>&tree, long long w){
	if(!tree[w].l){
		tree[w].l = tree.size();
		tree.push_back({1000000000000000000});
	}
	if(!tree[w].r){
		tree[w].r = tree.size();
		tree.push_back({1000000000000000000});
	}
	
}
void ustaw(vector<node>&tree,int w, long long l, long long p, long long a, long long val){
	if(a<l || p<a)return;
	if(l==p)tree[w].val = val;
	else{
		dodaj_synow(tree, w);
		ustaw(tree,tree[w].l, l, (l+p)/2, a, val);
		ustaw(tree,tree[w].r, (l+p)/2+1, p, a, val);
		tree[w].val = min(tree[tree[w].l].val, tree[tree[w].r].val);
	}
}
long long odczyt(vector<node>&tree,int w, long long l, long long p, long long a, long long b){
	if(b<l || p<a)return 1000000000000000000;
	if(a<=l && p<=b){
		//printf("w = %lld\n", w);
		return tree[w].val;
	}
	else{
		dodaj_synow(tree, w);
		long long val = min(
			odczyt(tree,tree[w].l, l, (l+p)/2, a, b),
			odczyt(tree,tree[w].r, (l+p)/2+1, p, a, b)
		);
		tree[w].val = min(tree[tree[w].l].val, tree[tree[w].r].val);
		return val;
	}
}

map<int,int>stosy;
long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	pre.push_back({1000000000000000000});
	suf.push_back({1000000000000000000});
	int n = x.size();
	int m = l.size();
	int i;
	vector<pair<int,pair<int, int>>>zdarzenia;
	zdarzenia.push_back({x[0],{1,0}});
	for(i=0;i<m;i++){
		zdarzenia.push_back({x[l[i]], {-1, y[i]}});
		zdarzenia.push_back({x[r[i]], {1, y[i]}});
	}
	stosy[0]=1;
	sort(zdarzenia.begin(), zdarzenia.end());
	long long wynik = 1000000000000000000;

	ustaw(pre,0,0,base-1,0, 0);
	ustaw(suf,0,0,base-1,0, 0);
	for(auto j: zdarzenia){
		if(j.first==x[n-1])
			wynik = min(wynik, odczyt(suf,0, 0, base-1, j.second.second, j.second.second)+x[n-1] - x[0]);
		if(j.second.first==1){
			//usuwanie
			if(--stosy[j.second.second]==0){
				ustaw(pre,0,0,base-1,j.second.second, 1000000000000000000);
				ustaw(suf,0,0,base-1,j.second.second, 1000000000000000000);
			}
		}
		if(j.second.first==-1){
			stosy[j.second.second]++;
			//dodawanie
			long long val = min({1000000000000000000ll,
				odczyt(suf,0,0,base-1,j.second.second,1000000000)+j.first-j.second.second,
				odczyt(pre,0,0,base-1,0,j.second.second)+j.first+j.second.second
				});
//			printf("%lld %lld\n", val, odczyt(suf,0,0,base-1,j.second.second,1000000000));
			ustaw(pre,0,0,base-1,j.second.second, val-j.first-j.second.second);
			ustaw(suf,0,0,base-1,j.second.second, val-j.first+j.second.second);
		}
//		printf("%d %d %d\n", j.first, j.second.second, j.second.first);
//		for(auto ij:pre)printf("%lld %lld %lld\n", ij.l, ij.r, ij.val);printf("\n");
//		for(auto ij:suf)printf("%lld %lld %lld\n", ij.l, ij.r, ij.val);
	}
	if(wynik<10000000000000000)
		return wynik;
	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 86 ms 4056 KB Output is correct
2 Correct 633 ms 159984 KB Output is correct
3 Correct 625 ms 160260 KB Output is correct
4 Correct 651 ms 163828 KB Output is correct
5 Correct 721 ms 164076 KB Output is correct
6 Correct 694 ms 163740 KB Output is correct
7 Correct 286 ms 83124 KB Output is correct
8 Correct 559 ms 163700 KB Output is correct
9 Correct 648 ms 163880 KB Output is correct
10 Correct 310 ms 19200 KB Output is correct
11 Correct 7 ms 2136 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 4056 KB Output is correct
2 Correct 633 ms 159984 KB Output is correct
3 Correct 625 ms 160260 KB Output is correct
4 Correct 651 ms 163828 KB Output is correct
5 Correct 721 ms 164076 KB Output is correct
6 Correct 694 ms 163740 KB Output is correct
7 Correct 286 ms 83124 KB Output is correct
8 Correct 559 ms 163700 KB Output is correct
9 Correct 648 ms 163880 KB Output is correct
10 Correct 310 ms 19200 KB Output is correct
11 Correct 7 ms 2136 KB Output is correct
12 Correct 613 ms 160288 KB Output is correct
13 Correct 655 ms 163684 KB Output is correct
14 Correct 650 ms 163736 KB Output is correct
15 Correct 370 ms 62568 KB Output is correct
16 Correct 372 ms 61548 KB Output is correct
17 Correct 359 ms 61548 KB Output is correct
18 Correct 349 ms 62560 KB Output is correct
19 Correct 379 ms 61540 KB Output is correct
20 Correct 295 ms 82872 KB Output is correct
21 Correct 20 ms 6544 KB Output is correct
22 Correct 402 ms 103164 KB Output is correct
23 Correct 420 ms 104960 KB Output is correct
24 Correct 411 ms 112904 KB Output is correct
25 Correct 533 ms 162688 KB Output is correct
26 Correct 466 ms 163052 KB Output is correct
27 Correct 715 ms 163736 KB Output is correct
28 Correct 653 ms 163832 KB Output is correct
29 Correct 669 ms 163708 KB Output is correct
30 Correct 296 ms 83124 KB Output is correct
31 Correct 635 ms 163732 KB Output is correct
32 Correct 266 ms 14944 KB Output is correct
33 Correct 264 ms 15300 KB Output is correct
34 Correct 280 ms 18756 KB Output is correct
35 Correct 309 ms 51096 KB Output is correct
36 Correct 289 ms 36480 KB Output is correct
37 Correct 241 ms 9928 KB Output is correct
38 Correct 241 ms 10696 KB Output is correct
39 Correct 294 ms 23224 KB Output is correct
40 Correct 239 ms 11716 KB Output is correct
41 Correct 229 ms 9924 KB Output is correct

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 -