Submission #411471

#	Time	Username	Problem	Language	Result	Execution time	Memory
411471		aryan12	Pinball (JOI14_pinball)	C++17	0 / 100	1 ms	204 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 1e5 + 5, INF = 1e15;
int m, n;
vector<vector<int> > devices;
int seg[2][N * 12];
map<int, int> cc;

void Build(int left, int right, int pos, int d2) {
	if((left == 1 && d2 == 0) || (right == cc[n] && d2 == 1)) {
		//cout << "left = " << left << ", d2 = " << d2 << ", right = " << right << ", cc[n] = " << cc[n] << "\n";
		seg[d2][pos] = 0;
	}
	else {
		seg[d2][pos] = INF;
	}
	//cout << "left = " << left << ", right = " << right << ", d2 = " << d2 << ", val = " << seg[d2][pos] << "\n";
	//cout << "cc[n] = " << cc[n] << "\n";
	if(left == right)
		return;
	int mid = (left + right) >> 1;
	Build(left, mid, pos * 2, d2);
	Build(mid + 1, right, pos * 2 + 1, d2);
}

int Query(int left, int right, int pos, int d2, int qleft, int qright) {
	if(qleft <= left && right <= qright)
		return seg[d2][pos];
	if(qleft > right || left > qright)
		return INF;
	int mid = (left + right) >> 1;
	return min(Query(left, mid, pos * 2, d2, qleft, qright), Query(mid + 1, right, pos * 2 + 1, d2, qleft, qright));
}

void Update(int left, int right, int pos, int d2, int qpos, int qval) {
	if(left == right) {
		seg[d2][pos] = min(seg[d2][pos], qval);
		return;
	}
	int mid = (left + right) >> 1;
	if(mid >= qpos) {
		Update(left, mid, pos * 2, d2, qpos, qval);
	}
	else {
		Update(mid + 1, right, pos * 2 + 1, d2, qpos, qval);
	}
	seg[d2][pos] = min(seg[d2][pos * 2], seg[d2][pos * 2 + 1]);
}

/*void GetMyUpdate(int left, int right, int pos, int d2) {
	cout << "left = " << left << ", right = " << right << ", d2 = " << d2 << ", val = " << seg[d2][pos] << "\n";
	if(left == right)
		return;
	int mid = (left + right) >> 1;
	GetMyUpdate(left, mid, pos * 2, d2);
	GetMyUpdate(mid + 1, right, pos * 2 + 1, d2);
}*/

void Solve() {
	cin >> m >> n;
	vector<int> inputDevices(4);
	bool f1 = false, f2 = false;
	devices.push_back({INF, INF, INF, INF});
	for(int i = 1; i <= m; i++) {
		cin >> inputDevices[0] >> inputDevices[1] >> inputDevices[2] >> inputDevices[3];
		//cout << inputDevices[0] << " " << inputDevices[1] << " " << inputDevices[2] << " " << inputDevices[3] << "\n";
		cc[inputDevices[0]]++;
		cc[inputDevices[1]]++;
		cc[inputDevices[2]]++;
		if(inputDevices[0] == 1) {
			f1 = true;
		}
		if(inputDevices[1] == n) {
			f2 = true;
		}
		devices.push_back(inputDevices);
	}
	/*if(!f1 || !f2) {
		cout << "-1\n";
		return;
	}*/
	int cnt = 1;
	for(auto i: cc) {
		cc[i.first] = cnt++;
		//cout << "i.first = " << i.first << ", cnt = " << cnt - 1 << "\n";
	}
	/*cout << "Outputting the compressed values of devices[][]\n";
	for(int i = 1; i <= m; i++) {
		for(int j = 0; j < 3; j++) {
			devices[i][j] = cc[devices[i][j]];
			cout << devices[i][j] << " ";
		}
		cout << "\n";
	}*/
	Build(1, cnt - 1, 1, 0);
	Build(1, cnt - 1, 1, 1);
	int ans = INF;
	for(int i = 1; i <= m; i++) {
		int minToGetLeft = Query(1, cnt - 1, 1, 0, devices[i][0], devices[i][1]);
		int minToGetRight = Query(1, cnt - 1, 1, 1, devices[i][0], devices[i][1]);
		if(minToGetLeft != INF) {
			Update(1, cnt - 1, 1, 0, devices[i][2], minToGetLeft + devices[i][3]);
		}
		if(minToGetRight != INF) {
			Update(1, cnt - 1, 1, 1, devices[i][2], minToGetRight + devices[i][3]);
		}
		ans = min(ans, minToGetLeft + minToGetRight + devices[i][3]);
		/*cout << "---------------------------------------------------\n";
		cout << "Operation i = " << i << "\n";
		GetMyUpdate(1, cnt - 1, 1, 0);
		GetMyUpdate(1, cnt - 1, 1, 1);
		cout << "---------------------------------------------------\n";*/
	}
	if(ans >= INF - 1e9) {
		cout << "-1\n";
	}
	else {
		cout << ans << "\n";
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		Solve();
	}
	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'void Solve()':
pinball.cpp:64:7: warning: variable 'f1' set but not used [-Wunused-but-set-variable]
   64 |  bool f1 = false, f2 = false;
      |       ^~
pinball.cpp:64:19: warning: variable 'f2' set but not used [-Wunused-but-set-variable]
   64 |  bool f1 = false, f2 = false;
      |                   ^~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 49