This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
ll n, m, f, cur, dp[100000], X[100000];
array <ll, 5> A[100000];
struct SegTree1D{
vector <ll> st;
void init(ll sz) {
st.resize(4*sz);
fill(st.begin(), st.end(), (ll)1e18);
}
void update(ll id, ll l, ll r, ll q, ll w) {
if (l == r) {
st[id] = min(st[id], w);
return;
}
ll mid = (l+r)/2;
if (q <= mid) update(id*2, l, mid, q, w);
else update(id*2+1, mid+1, r, q, w);
st[id] = min(st[id*2], st[id*2+1]);
}
ll query(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql) return 1e18;
else if (ql <= l && r <= qr) return st[id];
ll mid = (l+r)/2;
return min(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
}
};
struct SegTree2D{
vector <ll> V[400000];
SegTree1D st[400000];
void build(ll id, ll l, ll r) {
st[id].init(r-l+1);
if (l == r) {
V[id].push_back(X[l]);
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
int i = 0, j = 0;
while (i < V[id*2].size() && j < V[id*2+1].size()) {
if (V[id*2][i] <= V[id*2+1][j]) V[id].push_back(V[id*2][i++]);
else V[id].push_back(V[id*2+1][j++]);
}
while (i < V[id*2].size()) V[id].push_back(V[id*2][i++]);
while (j < V[id*2+1].size()) V[id].push_back(V[id*2+1][j++]);
}
void update(ll id, ll l, ll r, ll x, ll q, ll w) {
auto it = lower_bound(V[id].begin(), V[id].end(), q);
st[id].update(1, 0, V[id].size()-1, it-V[id].begin(), w);
if (l == r) return;
ll mid = (l+r)/2;
if (x <= mid) update(id*2, l, mid, x, q, w);
else update(id*2+1, mid+1, r, x, q, w);
}
ll query(ll id, ll l, ll r, ll ql, ll qr, ll x) {
if (qr < l || r < ql) return 1e18;
else if (ql <= l && r <= qr) {
auto it = lower_bound(V[id].begin(), V[id].end(), x);
if (it != V[id].end()) return st[id].query(1, 0, V[id].size()-1, it-V[id].begin(), V[id].size()-1);
else return 1e18;
}
ll mid = (l+r)/2;
return min(query(id*2, l, mid, ql, qr, x), query(id*2+1, mid+1, r, ql, qr, x));
}
}STA, STB;
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
f = 1e18;
cin >> n >> m;
for (int i=0; i<m; ++i) {
for (int j=0; j<4; ++j) {
cin >> A[i][j];
}
}
sort(A, A+m);
for (int i=0; i<m; ++i) A[i][4] = i;
for (int i=0; i<m; ++i) X[i] = A[i][2]+A[i][0];
STA.build(1, 0, m-1);
for (int i=0; i<m; ++i) X[i] = A[i][2]-A[i][0];
STB.build(1, 0, m-1);
sort(A, A+m, [](auto a, auto b) {
return (a[2] == n ? 1e9 : a[2]+a[0]) < (b[2] == n ? 1e9 : b[2]+b[0]);
});
for (int i=0; i<m; ++i) {
cur = STA.query(1, 0, m-1, 0, A[i][4], A[i][1]+A[i][0]-1);
if (A[i][4] != m-1) cur = min(cur, STB.query(1, 0, m-1, A[i][4]+1, m-1, A[i][1]-A[i][0]-1));
dp[i] = cur+A[i][3];
if (A[i][1] == 1) dp[i] = A[i][3];
if (A[i][2] == n) f = min(f, dp[i]);
STA.update(1, 0, m-1, A[i][4], A[i][2]+A[i][0], dp[i]);
STB.update(1, 0, m-1, A[i][4], A[i][2]-A[i][0], dp[i]);
}
if (f >= 1e18) cout << "-1\n";
else cout << f << '\n';
}
Compilation message (stderr)
treatment.cpp: In member function 'void SegTree2D::build(long long int, long long int, long long int)':
treatment.cpp:48:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | while (i < V[id*2].size() && j < V[id*2+1].size()) {
| ~~^~~~~~~~~~~~~~~~
treatment.cpp:48:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | while (i < V[id*2].size() && j < V[id*2+1].size()) {
| ~~^~~~~~~~~~~~~~~~~~
treatment.cpp:52:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | while (i < V[id*2].size()) V[id].push_back(V[id*2][i++]);
| ~~^~~~~~~~~~~~~~~~
treatment.cpp:53:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while (j < V[id*2+1].size()) V[id].push_back(V[id*2+1][j++]);
| ~~^~~~~~~~~~~~~~~~~~
# | 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... |