Submission #4341599


Source Code Expand

Copy
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R

struct pyNode {
	long long int x, y, index;
	long long int cost;
	bool operator<(const pyNode& p)const {
		if (y < p.y)return true;
		if (y > p.y)return false;
		return x < p.x;
	}
};

struct pxNode {
	long long int x, y, index;
	long long int cost;
	bool operator<(const pxNode& p)const {
		if (x < p.x)return true;
		if (x > p.x)return false;
		return y < p.y;
	}
};

class Segment_Tree {
	vector<long long int>v;
	vector<long long int>add;
	vector<long long int>modi;
	vector<int>l;
	vector<int>r;
	int num;
	long long int ret;
	bool is_min;
	void Left(int place) {
		if (place >= v.size() / 2) {
			l[place] = place - v.size() / 2;
			return;
		}
		Left(place * 2);
		Left(place * 2 + 1);
		l[place] = l[place * 2];
		return;
	}
	void Right(int place) {
		if (place >= v.size() / 2) {
			r[place] = place - v.size() / 2;
			return;
		}
		Right(place * 2);
		Right(place * 2 + 1);
		r[place] = r[place * 2 + 1];
		return;
	}
	long long int Update(int place) {
		if (place >= v.size() / 2) {
			return v[place];
		}
		if (is_min) {
			v[place] = min(Update(place * 2), Update(place * 2 + 1));
			return v[place];
		}
		v[place] = max(Update(place * 2), Update(place * 2 + 1));
		return v[place];
	}
	void Modify(int a, int b, long long int num, int place) {
		if (l[place] >= a && r[place] <= b) {
			modi[place] = min(modi[place],num);
			v[place] = min(v[place], modi[place]);
			add[place] = 0;
			return;
		}
		if (l[place] > b || r[place] < a)return;
		if (modi[place] != LLONG_MAX) {
			modi[place * 2] = min(modi[place * 2], modi[place]);
			modi[place * 2 + 1] = min(modi[place * 2 + 1], modi[place]);
			//modi[place * 2] = modi[place * 2 + 1] = modi[place];
			v[place * 2] = min(v[place * 2], modi[place*2]);
			v[place * 2 + 1] = min(v[place * 2 + 1], modi[place*2+1]);
			//v[place * 2] = v[place * 2 + 1] = modi[place];
			add[place * 2] = add[place * 2 + 1] = 0;
			modi[place] = LLONG_MAX;
		}
		add[place * 2] += add[place];
		add[place * 2 + 1] += add[place];
		add[place] = 0;
		Modify(a, b, num, place * 2);
		Modify(a, b, num, place * 2 + 1);
		if (is_min)v[place] = min(v[place * 2] + add[place * 2], v[place * 2 + 1] + add[place * 2 + 1]);
		else v[place] = max(v[place * 2] + add[place * 2], v[place * 2 + 1] + add[place * 2 + 1]);
		return;
	}
	void Add(int a, int b, long long int num, int place) {
		if (l[place] >= a && r[place] <= b) {
			if (modi[place] != LLONG_MAX) {
				if (place * 2 < v.size()) {
					modi[place * 2] = min(modi[place * 2], modi[place]);
					modi[place * 2 + 1] = min(modi[place * 2 + 1], modi[place]);
					//modi[place * 2] = modi[place * 2 + 1] = modi[place];
					v[place * 2] = min(v[place * 2], modi[place * 2]);
					v[place * 2 + 1] = min(v[place * 2 + 1], modi[place * 2 + 1]);
					//v[place * 2] = v[place * 2 + 1] = modi[place];
					add[place * 2] = add[place * 2 + 1] = 0;
				}
				modi[place] = LLONG_MAX;
			}
			add[place] += num;
			return;
		}
		if (l[place] > b || r[place] < a)return;
		if (modi[place] != LLONG_MAX) {
			modi[place * 2] = min(modi[place * 2], modi[place]);
			modi[place * 2 + 1] = min(modi[place * 2 + 1], modi[place]);
			//modi[place * 2] = modi[place * 2 + 1] = modi[place];
			v[place * 2] = min(v[place * 2], modi[place*2]);
			v[place * 2 + 1] = min(v[place * 2 + 1], modi[place*2+1]);
			//v[place * 2] = v[place * 2 + 1] = modi[place];
			add[place * 2] = add[place * 2 + 1] = 0;
			modi[place] = LLONG_MAX;
		}
		add[place * 2] += add[place];
		add[place * 2 + 1] += add[place];
		add[place] = 0;
		Add(a, b, num, place * 2);
		Add(a, b, num, place * 2 + 1);
		if (is_min)v[place] = min(v[place * 2] + add[place * 2], v[place * 2 + 1] + add[place * 2 + 1]);
		else v[place] = max(v[place * 2] + add[place * 2], v[place * 2 + 1] + add[place * 2 + 1]);
		return;
	}
	void RMQ(int a, int b, int place) {
		if (l[place] >= a && r[place] <= b) {
			if (modi[place] != LLONG_MAX) {
				if (place * 2 < v.size()) {
					modi[place * 2] = min(modi[place * 2], modi[place]);
					modi[place * 2 + 1] = min(modi[place * 2 + 1], modi[place]);
					//modi[place * 2] = modi[place * 2 + 1] = modi[place];
					v[place * 2] = min(v[place * 2], modi[place * 2]);
					v[place * 2 + 1] = min(v[place * 2 + 1], modi[place * 2 + 1]);
					//v[place * 2] = v[place * 2 + 1] = modi[place];
					add[place * 2] = add[place * 2 + 1] = 0;
				}
				modi[place] = LLONG_MAX;
			}
			if (is_min)ret = min(ret, v[place] + add[place]);
			else ret = max(ret, v[place] + add[place]);
			return;
		}
		if (l[place]>b || r[place]<a) return;
		if (modi[place] != LLONG_MAX) {
			modi[place * 2] = min(modi[place * 2], modi[place]);
			modi[place * 2 + 1] = min(modi[place * 2 + 1], modi[place]);
			//modi[place * 2] = modi[place * 2 + 1] = modi[place];
			v[place * 2] = min(v[place * 2], modi[place * 2]);
			v[place * 2 + 1] = min(v[place * 2 + 1], modi[place * 2 + 1]);
			//v[place * 2] = v[place * 2 + 1] = modi[place];
			add[place * 2] = add[place * 2 + 1] = 0;
			modi[place] = LLONG_MAX;
		}
		add[place * 2] += add[place];
		add[place * 2 + 1] += add[place];
		add[place] = 0;
		RMQ(a, b, place * 2);
		RMQ(a, b, place * 2 + 1);
		if (is_min)v[place] = min(v[place * 2] + add[place * 2], v[place * 2 + 1] + add[place * 2 + 1]);
		else v[place] = max(v[place * 2] + add[place * 2], v[place * 2 + 1] + add[place * 2 + 1]);
		return;
	}
public:
	Segment_Tree(int n, bool min) {
		n++;
		num = 1;
		while (num < n * 2) {
			num *= 2;
		}
		l.resize(num);
		r.resize(num);
		is_min = min;
		if (min) {
			v.resize(num, MOD*MOD);
		}
		else v.resize(num, -MOD * MOD);
		add.resize(num, 0);
		modi.resize(num, MOD*MOD);
		Left(1);
		Right(1);
	}
	void Insert(int place, long long int num, bool update) {
		place += v.size() / 2;
		v[place] = num;
		if (!update)return;
		place /= 2;
		while (place) {
			if (is_min)v[place] = min(v[place * 2], v[place * 2 + 1]);
			else v[place] = max(v[place * 2], v[place * 2 + 1]);
			place /= 2;
		}
	}
	void Modify(int a, int b, long long int num) {
		Modify(a, b, num, 1);
	}
	void Add(int a, int b, long long int num) {
		Add(a, b, num, 1);
	}
	void Init() {
		Update(1);
	}
	long long int RMQ(int a, int b) {
		if (is_min)ret = LLONG_MAX;
		else ret = LLONG_MIN;
		RMQ(a, b, 1);
		return ret;
	}
};

pyNode converter(pxNode n) {
	pyNode ret;
	ret.x = n.x;
	ret.y = n.y;
	ret.index = n.index;
	ret.cost = n.cost;
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> L >> R;
	L--;
	R--;
	vector<pxNode>px(N);
	map<int, int>m;
	for (int i = 0; i < N; i++) {
		cin >> W >> H >> K;
		m[H]++;
		px[i] = { W,H,i,K };
	}
	K = 0;
	for (auto &i : m)i.second = K++;
	for (auto &i : px)i.y = m[i.y];
	if (px[R] < px[L])swap(L, R);
	int sy, sx, gy, gx, sc, gc;
	sx = px[L].x;
	sy = px[L].y;
	gx = px[R].x;
	gy = px[R].y;
	sc = px[L].cost;
	gc = px[R].cost;
	sort(px.begin(), px.end());
	Segment_Tree sg(m.size(), true);
	int miny = m.size();
	long long int ans = MOD * MOD;
	for (int i = 0; i < N; i++) {
		long long int cost = MOD * MOD;
		if (px[i].index == L)cost = 0;
		else if (px[i].x <= sx && px[i].y <= sy)cost = sc;
		else {
			cost = min(cost, sg.RMQ(0, px[i].y) + px[i].cost);
		}
		if (px[i].index == R) {
			ans = min(ans, cost);
		}
		miny = min(miny, (int)px[i].y);
		sg.Modify(px[i].y, m.size() - 1, cost);
		long long int add_cost = cost + px[i].cost;
		if (px[i].x >= gx && px[i].y >= gy)	ans = min(ans, add_cost);
		if (px[i].x <= gx && px[i].y <= gy)ans = min(ans, cost + gc);
		sg.Modify(miny, m.size() - 1, add_cost);
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task F - Flights
User olphe
Language C++14 (GCC 5.4.1)
Score 900
Code Size 8322 Byte
Status
Exec Time 273 ms
Memory 16256 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample-01.txt, sample-02.txt
All 900 / 900 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, sample-01.txt, sample-02.txt
Case Name Status Exec Time Memory
01-01.txt 2 ms 384 KB
01-02.txt 239 ms 16256 KB
01-03.txt 273 ms 16256 KB
01-04.txt 271 ms 16256 KB
01-05.txt 190 ms 9856 KB
01-06.txt 191 ms 9856 KB
01-07.txt 184 ms 9856 KB
01-08.txt 184 ms 9856 KB
01-09.txt 186 ms 9856 KB
01-10.txt 181 ms 9856 KB
01-11.txt 192 ms 9856 KB
01-12.txt 190 ms 9856 KB
01-13.txt 179 ms 9856 KB
01-14.txt 183 ms 9856 KB
01-15.txt 184 ms 9856 KB
01-16.txt 176 ms 9856 KB
01-17.txt 190 ms 9856 KB
01-18.txt 185 ms 9856 KB
01-19.txt 176 ms 9856 KB
01-20.txt 182 ms 9856 KB
01-21.txt 183 ms 9856 KB
01-22.txt 176 ms 9856 KB
01-23.txt 178 ms 9856 KB
sample-01.txt 1 ms 256 KB
sample-02.txt 1 ms 256 KB