Submission #216771

#TimeUsernameProblemLanguageResultExecution timeMemory
216771abacabaTreatment Project (JOI20_treatment)C++14
39 / 100
1949 ms524292 KiB
#include <iostream> #include <string> #include <unordered_map> #include <unordered_set> #include <cstring> #include <chrono> #include <vector> #include <map> #include <random> #include <set> #include <algorithm> #include <math.h> #include <cstdio> #include <stdio.h> #include <queue> #include <bitset> #include <cstdlib> #include <deque> #include <cassert> #include <stack> using namespace std; #define mp make_pair #define f first #define se second #define pb push_back #define ppb pop_back #define ll long long #define ull unsigned long long #define cntbit(x) __builtin_popcount(x) #define endl '\n' #define uset unordered_set #define umap unordered_map #define all(x) x.begin(), x.end() #define pii pair<int, int> #define ld long double #define pll pair<long long, long long> mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> inline T range(T l, T r) { return uniform_int_distribution <T>(l, r)(rng); } template <typename T> void Min(T &a, T b) { a = min(a, b); } template <typename T> void Max(T &a, T b) { a = max(a, b); } const int mod = 1e9 + 7; const ll inf = 2e18; const int N = 1e6 + 15; int n, m; ll ans = -1; vector <int> compress; int sz; ll d[N]; set <pair <ll, int>> q; inline int gt(int x) { return lower_bound(compress.begin(), compress.end(), x) - compress.begin() + 1; } struct pt { int t, l, r, c; } a[N]; struct segment_tree { set <pii> t[N << 2]; void get(int v, int tl, int tr, int l, int r, int val, vector <int> &res) { if(tl > r || tr < l) return; if(tl >= l && tr <= r) { while(!t[v].empty() && t[v].begin()->f <= val) { res.pb(t[v].begin()->se); t[v].erase(t[v].begin()); } return; } int mid = tl + tr >> 1; get(v << 1, tl, mid, l, r, val, res); get(v << 1 | 1, mid + 1, tr, l, r, val, res); } void update(int v, int tl, int tr, int pos, pii val, bool insert) { if(insert) t[v].insert(val); else if(t[v].find(val) != t[v].end()) t[v].erase(val); if(tl == tr) return; int mid = tl + tr >> 1; if(pos <= mid) update(v << 1, tl, mid, pos, val, insert); else update(v << 1 | 1, mid + 1, tr, pos, val, insert); } } t1, t2; main() { fill(d, d + N, inf); ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0); cin >> n >> m; for(int i = 1; i <= m; ++i) { cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c; compress.pb(a[i].t); } sort(compress.begin(), compress.end()); compress.erase(unique(compress.begin(), compress.end()), compress.end()); sz = compress.size(); for(int i = 1; i <= m; ++i) { --a[i].l; if(a[i].l == 0) { d[i] = a[i].c; q.insert({d[i], i}); } else { t1.update(1, 1, sz, gt(a[i].t), mp(a[i].l + a[i].t, i), true); t2.update(1, 1, sz, gt(a[i].t), mp(a[i].l - a[i].t, i), true); } } while(!q.empty()) { int i = q.begin()->se; q.erase(q.begin()); vector <int> res[2] = {{}, {}}; t1.get(1, 1, sz, gt(a[i].t), sz, a[i].r + a[i].t, res[0]); t2.get(1, 1, sz, 1, gt(a[i].t), a[i].r - a[i].t, res[1]); for(int t = 0; t < 2; ++t) { for(int j : res[t]) { d[j] = d[i] + a[j].c; q.insert(mp(d[j], j)); t1.update(1, 1, sz, gt(a[j].t), mp(a[j].l + a[j].t, j), false); t2.update(1, 1, sz, gt(a[j].t), mp(a[j].l - a[j].t, j), false); } } } for(int i = 1; i <= m; ++i) { if(a[i].r != n || d[i] == inf) continue; if(ans == -1 || d[i] < ans) ans = d[i]; } cout << ans << endl; return 0; }

Compilation message (stderr)

treatment.cpp: In member function 'void segment_tree::get(int, int, int, int, int, int, std::vector<int>&)':
treatment.cpp:86:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
treatment.cpp: In member function 'void segment_tree::update(int, int, int, int, std::pair<int, int>, bool)':
treatment.cpp:97:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = tl + tr >> 1;
             ~~~^~~~
treatment.cpp: At global scope:
treatment.cpp:105:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...