oj.uz

Submission #1026846

# Submission time Handle Problem Language Result Execution time Memory
1026846 2024-07-18T12:20:26 Z Gr1sen Sky Walking (IOI19_walk) C++17
0 / 100
 4000 ms 35384 KB 
#include "walk.h"
#include<vector>
#include<algorithm>
#include<iomanip>
#include<iostream>
#include<queue>
#include<map>

using namespace std;

#define ll long long
#define vi vector<ll>
#define pi pair<ll, ll>
#define ppi pair<pi, bool>
#define pq priority_queue<ppi>
#define vp vector<pi>
#define mm multimap<ll, ll>

struct building {
	ll x, h;
	bool visit;
	mm visit_yp;
};

struct skyWalk {
	ll x1, x2, h;
	ll visit;
	ll visit_x;
};

vector<building> B;
vector<skyWalk> W;

void oink(int p) {
	return;
	ll price = -1;
	auto bit = B[p].visit_yp.end();
	while (bit != B[p].visit_yp.begin()) {
		bit--;
		ll temp = (*bit).second + (*bit).first;
		if (price == -1 || price > temp) price = temp;
	}
	cerr << price << endl;
}

mm fixThis(mm a) {
	if (a.empty()) return a;
	cerr << "enter fix" << endl;
	mm b;
	auto it = a.begin();
	ll lcost = (*it).second, ly = (*it).first;
	it++;
	b.insert({ly, lcost});
	while (it != a.end()) {
		ll cost = (*it).second, y = (*it).first;
		if (cost >= lcost + abs(y-ly)) {it++; continue;};
		b.insert({y, cost});
		lcost = cost;
		ly = y;

		it++;
	}

	a.clear();
	it = b.end();
	it--;
	lcost = (*it).second, ly = (*it).first;
	a.insert({ly, lcost});
	while (it != b.begin()) {
		it--;
		ll cost = (*it).second, y = (*it).first;
		if (cost >= lcost + abs(y-ly)) continue;
		a.insert({y, cost});
		lcost = cost;
		ly = y;
	}
	cerr << "exiting fix " << endl;
	return a;
}

ll min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
	if (s > g) swap(s, g);
	for (ll i = 0; i < x.size(); i++) {
		B.push_back({x[i], h[i], 0});
	}
	for (ll i = 0; i < l.size(); i++) {
		W.push_back({B[l[i]].x, B[r[i]].x, y[i], -1});
	}
	B[s].visit = 1;
	B[s].visit_yp = {{0, 0}};

	//cerr << "oink" << endl;

	vp L;
	for (ll i = 0; i < B.size(); i++) {
		L.push_back({B[i].x, i});
	}
	for (ll i = 0; i < W.size(); i++) {
		L.push_back({W[i].x1, -i-1});
		L.push_back({W[i].x2, i+B.size()});
	}
	sort(L.begin(), L.end());

	mm M;

	cerr << "oink" << endl;

	for (ll i = L.size() -1; i > -1; i--) {
		cerr << i << " " << L[i].first << " " << L[i].second << endl;
		oink(g);
		pi a = L[i];
		if (a.second < 0) {
			ll id = -a.second-1;
			auto its = M.equal_range(W[id].h);
			auto it = its.first, end = its.second;
			while (it != end) {
				if ((*it).second == id) {
					M.erase(it);
					break;
				}
				it++;
			}
			continue;
		}
		if (a.second >= (ll) B.size()) {
			ll id = a.second-B.size();
			M.insert({W[id].h, id});
			continue;
		}
		ll id = a.second;
		auto it1 = M.upper_bound(B[id].h);
		if (it1 == M.begin() || M.empty()) continue;
		auto it2 = it1;
		while (it2 != M.begin()) {
			it2--;
			ll wid = (*it2).second;
			cerr << "wid = " << wid << endl;
			if (W[wid].visit == -1) continue;
			cerr << "W[wid].visit = " << W[wid].visit << endl;
			B[id].visit_yp.insert({(*it2).first, W[wid].visit+abs(W[wid].visit_x - a.first)});
			B[id].visit = 1;
		}
		if (!B[id].visit) continue;
		B[id].visit_yp = fixThis(B[id].visit_yp);
		auto bit = B[id].visit_yp.end();
		bit--;
		while (it1 != M.begin()) {
			it1--;
			ll wid = (*it1).second;
			ll hi = (*it1).first;
			ll price = (*bit).second + abs(hi-(*bit).first);
			while (1) {
				ll temp = (*bit).second + abs(hi-(*bit).first);
				if (price > temp) {
					price = temp;
					if (bit != B[id].visit_yp.begin()) break;
					bit--;
					break;
				}
				break;
			}
			W[wid].visit = price;
			W[wid].visit_x = a.first;
		}
	}

	cerr << "oink" << endl;

	for (ll i = 0; i < L.size(); i++) {
		cerr << i << " " << L[i].first << " " << L[i].second << endl;
		oink(g);
		pi a = L[i];
		if (a.second >= (ll) B.size()) {
			ll id = a.second-B.size();
			auto its = M.equal_range(W[id].h);
			auto it = its.first, end = its.second;
			while (it != end) {
				if ((*it).second == id) {
					M.erase(it);
					break;
				}
				it++;
			}
			continue;
		}
		if (a.second < 0) {
			ll id = -(a.second+1);
			//cerr << id << endl << W[id].h << endl;
			M.insert({W[id].h, id});
			continue;
		}
		ll id = a.second;
		auto it1 = M.upper_bound(B[id].h);
		if (it1 == M.begin() || M.empty()) continue;
		auto it2 = it1;
		while (it2 != M.begin()) {
			it2--;
			ll wid = (*it2).second;
			if (W[wid].visit == -1) continue;
			B[id].visit_yp.insert({(*it2).first, W[wid].visit+abs(W[wid].visit_x - a.first)});
			B[id].visit = 1;
		}
		if (!B[id].visit) continue;
		B[id].visit_yp = fixThis(B[id].visit_yp);
		auto bit = B[id].visit_yp.end();
		bit--;
		while (it1 != M.begin()) {
			it1--;
			ll wid = (*it1).second;
			ll hi = (*it1).first;
			ll price = (*bit).second + abs(hi-(*bit).first);
			while (1) {
				ll temp = (*bit).second + abs(hi-(*bit).first);
				if (price > temp) {
					price = temp;
					if (bit != B[id].visit_yp.begin()) break;
					bit--;
					break;
				}
				break;
			}
			W[wid].visit = price;
			W[wid].visit_x = a.first;
		}
	}
	cerr << "oink" << endl;

	for (ll i = L.size() -1; i > -1; i--) {
		cerr << i << " " << L[i].first << " " << L[i].second << endl;
		oink(g);
		pi a = L[i];
		if (a.second < 0) {
			ll id = -a.second-1;
			auto its = M.equal_range(W[id].h);
			auto it = its.first, end = its.second;
			while (it != end) {
				if ((*it).second == id) {
					M.erase(it);
					break;
				}
				it++;
			}
			continue;
		}
		if (a.second >= (ll) B.size()) {
			ll id = a.second-B.size();
			M.insert({W[id].h, id});
			continue;
		}
		ll id = a.second;
		auto it1 = M.upper_bound(B[id].h);
		if (it1 == M.begin() || M.empty()) continue;
		auto it2 = it1;
		while (it2 != M.begin()) {
			it2--;
			ll wid = (*it2).second;
			if (W[wid].visit == -1) continue;
			B[id].visit_yp.insert({(*it2).first, W[wid].visit+abs(W[wid].visit_x - a.first)});
			B[id].visit = 1;
		}
		if (!B[id].visit) continue;
		B[id].visit_yp = fixThis(B[id].visit_yp);
		auto bit = B[id].visit_yp.end();
		bit--;
		while (it1 != M.begin()) {
			it1--;
			ll wid = (*it1).second;
			ll hi = (*it1).first;
			ll price = (*bit).second + abs(hi-(*bit).first);
			while (1) {
				ll temp = (*bit).second + abs(hi-(*bit).first);
				if (price > temp) {
					price = temp;
					if (bit != B[id].visit_yp.begin()) break;
					bit--;
					break;
				}
				break;
			}
			W[wid].visit = price;
			W[wid].visit_x = a.first;
		}
	}


	ll price = -1;
	auto bit = B[g].visit_yp.end();
	while (bit != B[g].visit_yp.begin()) {
		bit--;
		ll temp = (*bit).second + (*bit).first;
		if (price == -1 || price > temp) price = temp;
	}
	return price;
}

/*
int main() {
    int n, m; cin >> n >> m;
    vector<int> x(n), h(n);
    for (int i = 0; i < n; i++) cin >> x[i] >> h[i];
    vector<int> l(m), r(m), y(m);
    for (int i = 0; i < m; i++) cin >> l[i] >> r[i] >> y[i];
    int s, g;
    cin >> s >> g;

    long long result = min_distance(x, h, l, r, y, s, g);

    cout << result << "\n";
}

//*/

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:83:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |  for (ll i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
walk.cpp:86:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for (ll i = 0; i < l.size(); i++) {
      |                 ~~^~~~~~~~~~
walk.cpp:95:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<building>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for (ll i = 0; i < B.size(); i++) {
      |                 ~~^~~~~~~~~~
walk.cpp:98:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<skyWalk>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |  for (ll i = 0; i < W.size(); i++) {
      |                 ~~^~~~~~~~~~
walk.cpp:169:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |  for (ll i = 0; i < L.size(); i++) {
      |                 ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 8 ms 348 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 8 ms 464 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 4 ms 456 KB Output is correct
13 Correct 3 ms 456 KB Output is correct
14 Correct 3 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Incorrect 6 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Execution timed out 4085 ms 35384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2214 ms 16808 KB Output is correct
2 Execution timed out 4054 ms 30728 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2214 ms 16808 KB Output is correct
2 Execution timed out 4054 ms 30728 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 8 ms 348 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 6 ms 344 KB Output is correct
8 Correct 5 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 8 ms 464 KB Output is correct
11 Correct 3 ms 344 KB Output is correct
12 Correct 4 ms 456 KB Output is correct
13 Correct 3 ms 456 KB Output is correct
14 Correct 3 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Incorrect 6 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -