# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
390462 | parsabahrami | Treatment Project (JOI20_treatment) | C++17 | 169 ms | 20204 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/* There's someone in my head but it's not me */
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
#define SZ(x) (int) x.size()
#define F first
#define S second
const int N = 2e5 + 10;
ll dp[N]; vector<pii> adj[N]; vector<int> cp; int w[N], l[N], r[N], T[N], M[N], n, m;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d%d", &T[i], &l[i], &r[i], &w[i]);
assert(T[i] < 2);
r[i]++;
cp.push_back(r[i]);
cp.push_back(l[i]);
}
cp.push_back(1), cp.push_back(n + 1);
sort(cp.begin(), cp.end());
cp.resize(unique(cp.begin(), cp.end()) - cp.begin());
for (int i = 1; i <= m; i++) {
l[i] = lower_bound(begin(cp), end(cp), l[i]) - begin(cp);
r[i] = lower_bound(begin(cp), end(cp), r[i]) - begin(cp);
adj[r[i]].push_back({l[i], w[i]});
}
for (int i = 0; i + 1 < SZ(cp); i++) {
adj[i].emplace_back(i + 1, 0);
}
priority_queue<pair<ll, int>> pq;
fill(dp, dp + N, 1e18);
pq.emplace(dp[SZ(cp) - 1] = 0, SZ(cp) - 1);
while (SZ(pq)) {
int v = pq.top().S; pq.pop();
if (M[v]) continue;
M[v] = 1;
for (auto u : adj[v])
if (dp[u.F] > dp[v] + u.S)
dp[u.F] = dp[v] + u.S, pq.emplace(-dp[u.F], u.F);
}
printf("%lld\n", dp[0] >= 1e18 ? -1 : dp[0]);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |