oj.uz

Submission #778687

# Submission time Handle Problem Language Result Execution time Memory
778687 2023-07-10T14:57:24 Z Josia Sky Walking (IOI19_walk) C++17
15 / 100
 457 ms 92096 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;
	deque<tuple<int, bool, int>> 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<2>(Oevents[i]), get<1>(Oevents[i])});
		}
		else events.push_back({get<0>(Oevents[i]), get<2>(Oevents[i]), get<1>(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<1>(events[0])) {
				tree1.update(0, 0, 1e9, get<2>(events[0]), 1e18);
				tree2.update(0, 0, 1e9, get<2>(events[0]), 1e18);
				// cerr << "r " << get<2>(events[0]) << "\n";
			}
			else {
				int val = 1e18;

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

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

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

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

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

	if (tree1.query(0, 0, 1e9, 0, 1e9) + x.back() - x[0] > 1e17) 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:72: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]
   72 |  for (int i = 0; i<l.size(); i++) {
      |                  ~^~~~~~~~~
walk.cpp:81: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]
   81 |  for (int i = 0; i<Oevents.size()-1; i++) {
      |                  ~^~~~~~~~~~~~~~~~~
walk.cpp:90: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]
   90 |  for (int i = 0; i<Oevents.size(); i++) {
      |                  ~^~~~~~~~~~~~~~~
walk.cpp:105: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]
  105 |  for (int i = 0; i<x.size(); i++) {
      |                  ~^~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 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 1 ms 212 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 23 ms 3976 KB Output is correct
2 Correct 399 ms 86340 KB Output is correct
3 Correct 390 ms 86588 KB Output is correct
4 Correct 419 ms 87904 KB Output is correct
5 Correct 435 ms 88004 KB Output is correct
6 Correct 457 ms 87992 KB Output is correct
7 Correct 178 ms 45144 KB Output is correct
8 Correct 345 ms 87892 KB Output is correct
9 Correct 352 ms 91968 KB Output is correct
10 Correct 169 ms 22156 KB Output is correct
11 Correct 8 ms 2004 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3976 KB Output is correct
2 Correct 399 ms 86340 KB Output is correct
3 Correct 390 ms 86588 KB Output is correct
4 Correct 419 ms 87904 KB Output is correct
5 Correct 435 ms 88004 KB Output is correct
6 Correct 457 ms 87992 KB Output is correct
7 Correct 178 ms 45144 KB Output is correct
8 Correct 345 ms 87892 KB Output is correct
9 Correct 352 ms 91968 KB Output is correct
10 Correct 169 ms 22156 KB Output is correct
11 Correct 8 ms 2004 KB Output is correct
12 Correct 415 ms 88696 KB Output is correct
13 Correct 426 ms 92008 KB Output is correct
14 Correct 444 ms 92096 KB Output is correct
15 Correct 255 ms 54896 KB Output is correct
16 Correct 246 ms 42804 KB Output is correct
17 Correct 252 ms 42612 KB Output is correct
18 Correct 253 ms 54836 KB Output is correct
19 Correct 249 ms 42552 KB Output is correct
20 Correct 187 ms 47964 KB Output is correct
21 Correct 20 ms 5200 KB Output is correct
22 Correct 268 ms 63396 KB Output is correct
23 Correct 263 ms 64816 KB Output is correct
24 Correct 297 ms 90592 KB Output is correct
25 Correct 295 ms 89684 KB Output is correct
26 Correct 306 ms 90516 KB Output is correct
27 Correct 445 ms 91936 KB Output is correct
28 Correct 402 ms 91956 KB Output is correct
29 Correct 440 ms 91908 KB Output is correct
30 Correct 188 ms 48056 KB Output is correct
31 Correct 395 ms 91952 KB Output is correct
32 Correct 170 ms 19312 KB Output is correct
33 Incorrect 178 ms 19636 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

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