Submission #1067130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067130		jamjanek	Sky Walking (IOI19_walk)	C++14	0 / 100	81 ms	12040 KiB

walk

#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<<3;
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;
	}
}

set<pair<int,int>>poczatki;
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]}});
		poczatki.insert({y[i], x[l[i]]});
	}
	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(poczatki.find({j.second.second, j.first})==poczatki.end()){
				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){
			//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<=1000000000000000000)
		return wynik;
	else
		return -1;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 18
• Subtask 5: 0 / 43