Submission #778440

#	Time	Username	Problem	Language	Result	Execution time	Memory
778440		Josia	Sky Walking (IOI19_walk)	C++17	0 / 100	70 ms	4644 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) {
		// cerr << rl << " " << rr << "\n";
		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) {
		// cerr << rl << " " << rl << "\n";
		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);

		// cerr << v << " " << v1 << " " << v2 << "\n";

		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) {
	deque<tuple<int, int, bool>> events;

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

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


	seg tree1, tree2;


	// tree2.update(0, 0, 1e9, 2, 100);
	// for (int i = 0; i<tree2.tree.size(); i++) {
	// 	cerr << tree2.tree[i].val << " " << tree2.tree[i].c1 << " " << tree2.tree[i].c2 << "\n";
	// }
	// cerr << "\n\n\n";
	// cerr << tree2.query(0, 0, 1e9, 0, 0) << "\n";

	// return 0;



	// tree1.update(0, 0, 1e9, 0, 0);
	// tree2.update(0, 0, 1e9, 0, 1e9);

	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);
			}
			else {
				int val = 1e18;

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

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

				val = min(val, tree1.query(0, 0, 1e9, get<1>(events[0]), 1e9)-get<1>(events[0]));
				val = min(val, tree2.query(0, 0, 1e9, 0, get<1>(events[0]))+get<1>(events[0])-(int)1e9);
				// cerr << tree1.query(0, 0, 1e9, get<1>(events[0]), 1e9) << " " << tree2.query(0, 0, 1e9, 0, get<1>(events[0])) << "\n";
				// for (int i = 0; i<=get<1>(events[0]); i++) cerr << tree2.query(0, 0, 1e9, i, i) << " ";
				// cerr << "\n";
				// 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();
		}
	}



	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:76: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]
   76 |  for (int i = 0; i<l.size(); i++) {
      |                  ~^~~~~~~~~
walk.cpp:101: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]
  101 |  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