oj.uz

Submission #219376

# Submission time Handle Problem Language Result Execution time Memory
219376 2020-04-05T08:07:47 Z maruii Treatment Project (JOI20_treatment) C++14
4 / 100
 118 ms 10472 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
#define ff first
#define ss second
#define eack emplace_back
#define all(x) (x).begin(), (x).end()

const ll INF = 1e18;
int N, M;
ll ans = INF;
map<int, vector<pair<pii, int>>> MP;

struct X {
	set<pil> S;
	void add(pil v) {
		auto it = S.lower_bound(pil(v.ff, 0));
		if (it != S.end() && it->ss <= v.ss) return;
		if (it == S.begin()) {
			if (it->ff == v.ff) S.erase(it);
			S.insert(v);
			return;
		}
		if (it->ff == v.ff) S.erase(it--);
		else --it;
		while (1) {
			if (it->ss >= v.ss) {
				if (it == S.begin()) {
					S.erase(it);
					break;
				}
				S.erase(it--);
			}
			else break;
		}
		S.insert(v);
	}

	void update(int s, int e, int v) {
		auto it = S.lower_bound(pil(s - 1, 0));
		if (it == S.end()) return;
		add(pil(e, it->ss + v));
	}
} a;

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= M; ++i) {
		int t, l, r, c; cin >> t >> l >> r >> c;
		MP[t].eack(pii(l, r), c);
	}
	vector<pair<pii, pii>> vec;
	for (auto &i : MP) {
		int t = i.ff;
		for (auto j : i.ss) vec.eack(pii(t, j.ss), j.ff);
		vector<pair<pii, int>> v;
		for (auto j : vec) v.eack(pii(j.ss.ss == N ? N : j.ss.ss - t + j.ff.ff, j.ss.ff == 1 ? 1 : j.ss.ff + t - j.ff.ff), j.ff.ss);
		sort(all(v));
		a.S.clear();
		a.S.insert(pil(0, 0));
		for (auto i : v) if (i.ff.ss < i.ff.ff) a.update(i.ff.ss, i.ff.ff, i.ss);
		auto it = a.S.lower_bound(pil(N, 0));
		if (it != a.S.end()) ans = min(ans, it->ss);
	}
	if (ans == INF) ans = -1;
	cout << ans;
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 10472 KB Output is correct
2 Correct 92 ms 6752 KB Output is correct
3 Correct 91 ms 7396 KB Output is correct
4 Correct 96 ms 7520 KB Output is correct
5 Correct 77 ms 5860 KB Output is correct
6 Correct 70 ms 5832 KB Output is correct
7 Correct 81 ms 5860 KB Output is correct
8 Correct 70 ms 5856 KB Output is correct
9 Correct 68 ms 5860 KB Output is correct
10 Correct 68 ms 5864 KB Output is correct
11 Correct 77 ms 5860 KB Output is correct
12 Correct 76 ms 5732 KB Output is correct
13 Correct 83 ms 5736 KB Output is correct
14 Correct 84 ms 5864 KB Output is correct
15 Correct 92 ms 5860 KB Output is correct
16 Correct 95 ms 5736 KB Output is correct
17 Correct 84 ms 5740 KB Output is correct
18 Correct 66 ms 5732 KB Output is correct

Subtask #2
0 / 5.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 10472 KB Output is correct
2 Correct 92 ms 6752 KB Output is correct
3 Correct 91 ms 7396 KB Output is correct
4 Correct 96 ms 7520 KB Output is correct
5 Correct 77 ms 5860 KB Output is correct
6 Correct 70 ms 5832 KB Output is correct
7 Correct 81 ms 5860 KB Output is correct
8 Correct 70 ms 5856 KB Output is correct
9 Correct 68 ms 5860 KB Output is correct
10 Correct 68 ms 5864 KB Output is correct
11 Correct 77 ms 5860 KB Output is correct
12 Correct 76 ms 5732 KB Output is correct
13 Correct 83 ms 5736 KB Output is correct
14 Correct 84 ms 5864 KB Output is correct
15 Correct 92 ms 5860 KB Output is correct
16 Correct 95 ms 5736 KB Output is correct
17 Correct 84 ms 5740 KB Output is correct
18 Correct 66 ms 5732 KB Output is correct
19 Incorrect 5 ms 384 KB Output isn't correct
20 Halted 0 ms 0 KB -