oj.uz

Submission #778671

# Submission time Handle Problem Language Result Execution time Memory
778671 2023-07-10T14:38:59 Z Josia Sky Walking (IOI19_walk) C++17
0 / 100
 434 ms 90188 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3984 KB Output is correct
2 Correct 415 ms 86436 KB Output is correct
3 Correct 402 ms 86492 KB Output is correct
4 Correct 402 ms 87924 KB Output is correct
5 Correct 434 ms 87992 KB Output is correct
6 Correct 431 ms 88008 KB Output is correct
7 Correct 175 ms 45052 KB Output is correct
8 Incorrect 343 ms 90188 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3984 KB Output is correct
2 Correct 415 ms 86436 KB Output is correct
3 Correct 402 ms 86492 KB Output is correct
4 Correct 402 ms 87924 KB Output is correct
5 Correct 434 ms 87992 KB Output is correct
6 Correct 431 ms 88008 KB Output is correct
7 Correct 175 ms 45052 KB Output is correct
8 Incorrect 343 ms 90188 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -