Submission #778671

#	Time	Username	Problem	Language	Result	Execution time	Memory
778671		Josia	Sky Walking (IOI19_walk)	C++17	0 / 100	434 ms	90188 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

#define int int64_t

struct seg {
	struct node {
		int val=1000000000000000000;
		int c1=-1;
		int c2=-1;
	};


	vector<node> tree{(node){1000000000000000000, -1, -1}};

	void update(int v, int rl, int rr, int pos, int x) {
		if (rl == rr) {
			tree[v].val = x;
			return;
		}
		int rm = (rl+rr)/2;

		if (pos <= rm) {
			if (tree[v].c1 == -1) {
				tree[v].c1=tree.size();
				tree.push_back(node());
			}
			update(tree[v].c1, rl, rm, pos, x);
		}
		else {
			if (tree[v].c2 == -1) {
				tree[v].c2=tree.size();
				tree.push_back(node());
			}
			update(tree[v].c2, rm+1, rr, pos, x);
		}

		int v1 = 1e18;
		int v2 = 1e18;
		if (tree[v].c1 != -1) v1 = tree[tree[v].c1].val;
		if (tree[v].c2 != -1) v2 = tree[tree[v].c2].val;

		tree[v].val = min(v1, v2);
	}

	int query(int v, int rl, int rr, int ql, int qr) {
		if (ql > qr) return 1e18;
		if (ql == rl && qr == rr) {return tree[v].val;}

		int rm = (rl + rr) / 2;

		int v1 = 1e18;
		int v2 = 1e18;
		if (tree[v].c1 != -1) v1 = query(tree[v].c1, rl, rm, ql, min(qr, rm));
		if (tree[v].c2 != -1) v2 = query(tree[v].c2, rm+1, rr, max(ql, rm+1), qr);

		return min(v1, v2);
	}
};




long long min_distance(std::vector<signed> x, std::vector<signed> h, std::vector<signed> l, std::vector<signed> r, std::vector<signed> y, signed s, signed g) {
	if (x.size() == 1) return 0;
	
	deque<tuple<int, int, bool>> Oevents, events;


	for (int i = 0; i<l.size(); i++) {
		Oevents.push_back({l[i], y[i], 1});
		Oevents.push_back({r[i], y[i], 0});
	}

	sort(Oevents.begin(), Oevents.end());

	vector<bool> skip(Oevents.size());

	for (int i = 0; i<Oevents.size()-1; i++) {
		if (get<0>(Oevents[i]) == get<0>(Oevents[i+1]) && get<1>(Oevents[i]) == get<1>(Oevents[i+1])&& get<2>(Oevents[i]) != get<2>(Oevents[i+1])) {
			skip[i] = 1;
			skip[i+1] = 1;
		}
	}



	for (int i = 0; i<Oevents.size(); i++) {
		if (skip[i]) continue;
		if (!get<2>(Oevents[i])) {
			events.push_back({get<0>(Oevents[i])+1, get<1>(Oevents[i]), get<2>(Oevents[i])});
		}
		else events.push_back(Oevents[i]);
	}

	

	sort(events.begin(), events.end());


	seg tree1, tree2;

	for (int i = 0; i<x.size(); i++) {
		while(events.size() && get<0>(events[0]) == i) {
			if (!get<2>(events[0])) {
				tree1.update(0, 0, 1e9, get<1>(events[0]), 1e18);
				tree2.update(0, 0, 1e9, get<1>(events[0]), 1e18);
				// cerr << "r " << get<1>(events[0]) << "\n";
			}
			else {
				int val = 1e18;

				if (i == 0) val = get<1>(events[0]);

				// cerr << get<1>(events[0]) << " ";

				val = min(val, tree1.query(0, 0, 1e9, get<1>(events[0]), h[i])-get<1>(events[0]));
				val = min(val, tree2.query(0, 0, 1e9, 0, min(get<1>(events[0]), (int)h[i]))+get<1>(events[0])-(int)1e9);

				// cerr << val << "\n";

				tree1.update(0, 0, 1e9, get<1>(events[0]), val+get<1>(events[0]));
				tree2.update(0, 0, 1e9, get<1>(events[0]), val+1e9-get<1>(events[0]));
			}
			events.pop_front();
		}
	}

	if (tree1.query(0, 0, 1e9, 0, 1e9) + x.back() - x[0] > 9e17) return -1;

	return tree1.query(0, 0, 1e9, 0, 1e9) + x.back() - x[0];
}

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:71:19: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 0; i<l.size(); i++) {
      |                  ~^~~~~~~~~
walk.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::deque<std::tuple<long int, long int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int i = 0; i<Oevents.size()-1; i++) {
      |                  ~^~~~~~~~~~~~~~~~~
walk.cpp:89:19: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::deque<std::tuple<long int, long int, bool> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |  for (int i = 0; i<Oevents.size(); i++) {
      |                  ~^~~~~~~~~~~~~~~
walk.cpp:104:19: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |  for (int i = 0; i<x.size(); i++) {
      |                  ~^~~~~~~~~

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