#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2")
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
ostream& operator<<(ostream &out, ii x){ out<<"("<<x.F<<","<<x.S<<")"; return out; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }
const ll INF = ll(1e18);
const int MOD = 998244353;
struct Project
{
ll t, l, r, cost;
};
istream& operator>>(istream& in, Project &p)
{
in >> p.t >> p.l >> p.r >> p.cost;
p.l--;
p.r--;
return in;
}
ll n;
int m;
vector<Project> projects;
vector<ll> dist;
vector<ll> l_plus_t, l_minus_t, times; // list of all values
vector<ll> c_times; // idx to compressed
vector<vector<int>> plus_groups, minus_groups;
vector<bool> vst;
class PointSegmentTree{
private:
bool at_least;
int size_;
vector<set<ii>> v;
void build(const vector<vector<int>> &groups, int k, int l, int r)
{
if (l == r)
{
for (int id : groups[l])
{
v[k].insert({projects[id].t, id});
}
return;
}
int mid = (l + r) / 2;
build(groups, k * 2, l, mid);
build(groups, k * 2 + 1, mid + 1, r);
v[k].insert(all(v[k * 2]));
v[k].insert(all(v[k * 2 + 1]));
}
void query(int s, int e, ll curt, vector<int> &res, int k, int l, int r)
{
if(e < l || r < s) return;
if(s <= l && r <= e)
{
while(!v[k].empty())
{
set<ii>::iterator it;
if (at_least)
{
it = --v[k].end();
if (it->first < curt) break;
}
else
{
it = v[k].begin();
if (it->first >= curt) break;
}
int id = it->second;
if (!vst[id])
{
vst[id] = true;
res.push_back(id);
}
v[k].erase(it);
}
return;
}
int mid = (l + r) >> 1;
query(s, e, curt, res, k*2, l, mid);
query(s, e, curt, res, k*2+1, mid+1, r);
}
public:
PointSegmentTree(int n, bool at_least){
size_ = n;
v.resize(size_*4);
this->at_least = at_least;
}
void build(const vector<vector<int>> &groups) {
build(groups, 1, 0, size_ - 1);
}
vector<int> query(int l, int r, ll curt){
vector<int> res;
query(l, r, curt, res, 1, 0, size_-1);
return res;
}
};
void compress(vector<ll> &v)
{
sort(v.begin(), v.end());
v.erase(unique(all(v)), v.end());
}
int getCompressed(const vector<ll> &v, ll val)
{
return upper_bound(all(v), val) - v.begin() - 1;
}
void computeCompressions()
{
c_times.resize(m);
for (const auto &p : projects)
{
l_plus_t.push_back(p.l + p.t);
l_minus_t.push_back(p.l - p.t);
times.push_back(p.t);
}
compress(l_plus_t);
compress(l_minus_t);
compress(times);
plus_groups.resize(l_plus_t.size());
minus_groups.resize(l_minus_t.size());
forn(i,0,m)
{
const Project &p = projects[i];
int plus_id = getCompressed(l_plus_t, p.l + p.t);
int minus_id = getCompressed(l_minus_t, p.l - p.t);
plus_groups[plus_id].pb(i);
minus_groups[minus_id].pb(i);
c_times[i] = getCompressed(times, p.t);
}
}
void dijkstra()
{
priority_queue<ii, vector<ii>, greater<ii>> q; // (distance, node)
fill(dist.begin(), dist.end(), INF);
computeCompressions();
PointSegmentTree st_plus(l_plus_t.size(), true);
PointSegmentTree st_minus(l_minus_t.size(), false);
st_plus.build(plus_groups);
st_minus.build(minus_groups);
// initial nodes
for (int i = 0; i < m; i++)
{
auto p = projects[i];
if (p.l != 0) continue;
dist[i] = p.cost;
q.push({dist[i], i});
}
// dijkstra loop
while (!q.empty())
{
auto [cur_dist, u] = q.top();
q.pop();
if (cur_dist > dist[u]) continue;
const Project &p = projects[u];
auto next_p = st_plus.query(0, getCompressed(l_plus_t, p.r + p.t + 1), p.t);
auto next_minus = st_minus.query(0, getCompressed(l_minus_t, p.r - p.t + 1), p.t);
next_p.insert(next_p.end(), all(next_minus));
for (int id : next_p)
{
dist[id] = cur_dist + projects[id].cost;
q.push({dist[id], id});
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
// freopen("test.in", "r", stdin);
cin >> n >> m;
vst.resize(m, false);
projects.resize(m);
dist.resize(m);
forn(i, 0, m) cin >> projects[i];
dijkstra();
ll ans = INF;
forn(i, 0, m)
{
if (projects[i].r == n - 1)
{
ans = min(ans, dist[i]);
}
}
if (ans == INF) ans = -1;
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
711 ms |
280144 KB |
Output is correct |
| 2 |
Correct |
666 ms |
280572 KB |
Output is correct |
| 3 |
Correct |
733 ms |
246324 KB |
Output is correct |
| 4 |
Incorrect |
680 ms |
246248 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
711 ms |
280144 KB |
Output is correct |
| 2 |
Correct |
666 ms |
280572 KB |
Output is correct |
| 3 |
Correct |
733 ms |
246324 KB |
Output is correct |
| 4 |
Incorrect |
680 ms |
246248 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
