#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll T[100005];
ll L[100005];
ll R[100005];
ll C[100005];
vector<array<ll, 2>> adj[800005];
ll dis[200005];
bool vis[200005];
typedef pair<ll, ll> P;
struct SegTree {
struct Node {
vector<array<ll, 2>> S1, S2;
int p1, p2;
Node() : p1(0), p2(0) {}
};
vector<Node> seg;
int MAX;
SegTree(int N) {
int i;
for(i=1;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
}
void Edit(int n, int a) {
n += MAX/2;
seg[n].S1.push_back({L[a] + T[a], 2*a});
seg[n].S2.push_back({L[a] - T[a], 2*a});
}
void cons() {
for(int i = MAX/2-1;i>=1;i--) {
seg[i].S1.resize(seg[2*i].S1.size() + seg[2*i+1].S1.size());
merge(seg[2*i].S1.begin(),seg[2*i].S1.end(),seg[2*i+1].S1.begin(),seg[2*i+1].S1.end(),seg[i].S1.begin());
seg[i].S2.resize(seg[2*i].S2.size() + seg[2*i+1].S2.size());
merge(seg[2*i].S2.begin(),seg[2*i].S2.end(),seg[2*i+1].S2.begin(),seg[2*i+1].S2.end(),seg[i].S2.begin());
}
}
void make_edge(int s, int e, int k, int n, int ns, int ne, bool type) {
if(e<=ns||ne<=s) return;
if(s<=ns&&ne<=e) {
if(type) {
while(seg[n].p2 < seg[n].S2.size()) {
auto m = seg[n].S2[seg[n].p2];
if(m[0]>R[k]-T[k]+1) break;
adj[2*k+1].push_back({m[1], 0});
seg[n].p2++;
}
}
else {
while(seg[n].p1 < seg[n].S1.size()) {
auto m = seg[n].S1[seg[n].p1];
if(m[0]>R[k]+T[k]+1) break;
adj[2*k+1].push_back({m[1], 0});
seg[n].p1++;
}
}
return;
}
int mid = ns + ne >> 1;
make_edge(s, e, k, 2*n, ns, mid, type);
make_edge(s, e, k, 2*n+1, mid, ne, type);
}
};
vector<ll> idt;
int it(int n) {
return lower_bound(idt.begin(),idt.end(),n) - idt.begin();
}
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
int i, j;
for(i=1;i<=M;i++) {
cin >> T[i] >> L[i] >> R[i] >> C[i];
idt.push_back(T[i]);
}
sort(idt.begin(),idt.end());
idt.erase(unique(idt.begin(),idt.end()),idt.end());
//0 is left, 1 is right
//2i is input, 2i+1 is output
for(i=1;i<=M;i++) {
adj[2*i].push_back({2*i+1, C[i]});
if(L[i]==1) adj[0].push_back({2*i, 0});
if(R[i]==N) adj[2*i+1].push_back({1, 0});
}
/*for(i=1;i<=M;i++) {
for(j=1;j<=M;j++) {
if(i==j) continue;
if(T[i] >= T[j]) {
int t = T[i] - T[j];
if(R[j] == N || L[i] <= R[j] - t + 1) {
adj[2*j+1].push_back({2*i, 0});
}
}
if(T[i] <= T[j]) {
int t = T[j] - T[i];
if(L[i] == 1 || L[i] - 1 + t <= R[j]) {
adj[2*j+1].push_back({2*i, 0});
}
}
}
}*/
/*for(i=0;i<=2*M+1;i++) {
cout << i << " : ";
for(auto n2 : adj[i]) {
cout << "(" << n2[0] << ", " << n2[1] << ") ";
}
cout << '\n';
}*/
SegTree tree(idt.size() + 3);
int MAX = tree.MAX;
for(i=1;i<=M;i++) {
tree.Edit(it(T[i]), i);
}
tree.cons();
for(i=0;i<=2*M+1;i++) dis[i] = INF;
dis[0] = 0;
priority_queue<P, vector<P>, greater<P>> PQ;
PQ.push(P(0, 0));
while(!PQ.empty()) {
auto k = PQ.top();
PQ.pop();
int id = k.second;
if(vis[id]) continue;
vis[id] = true;
if(id != 0 && id != 1 && id % 2 == 1) {
int x = id / 2;
tree.make_edge(0, it(T[x])+1, x, 1, 0, MAX/2, true);
tree.make_edge(it(T[x]), idt.size(), x, 1, 0, MAX/2, false);
}
for(auto n : adj[id]) {
if(dis[n[0]] > dis[id] + n[1]) {
dis[n[0]] = dis[id] + n[1];
PQ.push(P(dis[n[0]], n[0]));
}
}
}
cout << (dis[1]==INF?-1:dis[1]);
}
Compilation message
treatment.cpp: In member function 'void SegTree::make_edge(int, int, int, int, int, int, bool)':
treatment.cpp:44:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | while(seg[n].p2 < seg[n].S2.size()) {
treatment.cpp:52:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | while(seg[n].p1 < seg[n].S1.size()) {
treatment.cpp:61:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int mid = ns + ne >> 1;
| ~~~^~~~
treatment.cpp: In function 'int main()':
treatment.cpp:76:12: warning: unused variable 'j' [-Wunused-variable]
76 | int i, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
37248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
19028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
19028 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
19028 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
37248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
