oj.uz

Submission #674994

# Submission time Handle Problem Language Result Execution time Memory
674994 2022-12-26T18:31:19 Z urosk Treatment Project (JOI20_treatment) C++14
39 / 100
 1388 ms 524288 KB 
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
//using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
*/
#define maxn 100005
#define maxx 800005
ll n,m;
struct tupl{
    ll t,l,r,c;
} a[maxn];
ll tsz = 1,tsz2 = 1;
int ls[maxx],rs[maxx];
int ls2[maxx],rs2[maxx];
set<pair<int,int> > t[maxx],t2[maxn];
void upd(ll v,ll tl,ll tr,ll i,pll p,bool f){
    if(f) t[v].insert(p);
    else t[v].erase(p);
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    if(i<=mid){
        if(!ls[v]) ls[v] = ++tsz;
        upd(ls[v],tl,mid,i,p,f);
    }else{
        if(!rs[v]) rs[v] = ++tsz;
        upd(rs[v],mid+1,tr,i,p,f);
    }
}
void upd2(ll v,ll tl,ll tr,ll i,pll p,bool f){
    if(f) t2[v].insert(p);
    else t2[v].erase(p);
    if(tl==tr) return;
    ll mid = (tl+tr)/2;
    if(i<=mid){
        if(!ls2[v]) ls2[v] = ++tsz2;
        upd2(ls2[v],tl,mid,i,p,f);
    }else{
        if(!rs2[v]) rs2[v] = ++tsz2;
        upd2(rs2[v],mid+1,tr,i,p,f);
    }
}
set<ll> s;
void get(ll v,ll tl,ll tr,ll l,ll r,ll x){
    if(l>r) return;
    if(tl==l&&tr==r){
        auto it = t[v].begin();
        while(it!=t[v].end()&&(*it).fi<=x){
            s.insert((*it).sc);
            it++;
        }
        return;
    }
    ll mid = (tl+tr)/2;
    if(ls[v]) get(ls[v],tl,mid,l,min(mid,r),x);
    if(rs[v]) get(rs[v],mid+1,tr,max(mid+1,l),r,x);
}
void get2(ll v,ll tl,ll tr,ll l,ll r,ll x){
    if(l>r) return;
    if(tl==l&&tr==r){
        auto it = t2[v].begin();
        while(it!=t2[v].end()&&(*it).fi<=x){
            s.insert((*it).sc);
            it++;
        }
        return;
    }
    ll mid = (tl+tr)/2;
    if(ls2[v]) get2(ls2[v],tl,mid,l,min(mid,r),x);
    if(rs2[v]) get2(rs2[v],mid+1,tr,max(mid+1,l),r,x);
}
ll d[maxn];
void tc(){
    cin >> m >> n;
    for(ll i = 1;i<=n;i++) cin >> a[i].t >> a[i].l >> a[i].r >> a[i].c;
    for(ll i = 1;i<=n;i++) a[i].l--;
    ll mxt = 0;
    for(ll i = 1;i<=n;i++) mxt = max(mxt,a[i].t);
    for(ll i = 1;i<=n;i++){
        if(a[i].l==0) continue;
        upd(1,1,mxt,a[i].t,{a[i].l+a[i].t,i},1);
        upd2(1,1,mxt,a[i].t,{a[i].l-a[i].t,i},1);
    }
    for(ll i = 1;i<=n;i++) d[i] = llinf;
    priority_queue<pll> pq;
    for(ll i = 1;i<=n;i++){
        if(a[i].l==0){
            d[i] = a[i].c;
            pq.push({-d[i],i});
        }
    }
    while(sz(pq)){
        pll p = pq.top();
        ll i = p.sc;
        pq.pop();
        if(-p.fi!=d[i]) continue;
        s.clear();
        get(1,1,mxt,a[i].t,mxt,a[i].r+a[i].t);
        get2(1,1,mxt,1,a[i].t,a[i].r-a[i].t);
        for(ll j : s){
            if(j==i) continue;
            d[j] = d[i] + a[j].c;
            upd(1,1,mxt,a[j].t,{a[j].l+a[j].t,j},0);
            upd2(1,1,mxt,a[j].t,{a[j].l-a[j].t,j},0);
            pq.push({-d[j],j});
        }
    }
    ll ans = llinf;
    for(ll i = 1;i<=n;i++) if(a[i].r==m) ans = min(ans,d[i]);
    if(ans==llinf) ans = -1;
    cout<<ans<<endl;
}
int main(){
	daj_mi_malo_vremena
    int t; t = 1;
    while(t--){
        tc();
    }
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 55884 KB Output is correct
2 Correct 123 ms 55864 KB Output is correct
3 Correct 128 ms 54596 KB Output is correct
4 Correct 124 ms 54708 KB Output is correct
5 Correct 128 ms 57996 KB Output is correct
6 Correct 124 ms 56148 KB Output is correct
7 Correct 107 ms 55836 KB Output is correct
8 Correct 92 ms 55732 KB Output is correct
9 Correct 84 ms 55764 KB Output is correct
10 Correct 76 ms 55884 KB Output is correct
11 Correct 230 ms 61452 KB Output is correct
12 Correct 213 ms 59188 KB Output is correct
13 Correct 186 ms 58056 KB Output is correct
14 Correct 190 ms 58144 KB Output is correct
15 Correct 172 ms 55876 KB Output is correct
16 Correct 167 ms 55828 KB Output is correct
17 Correct 165 ms 55908 KB Output is correct
18 Correct 238 ms 60424 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42580 KB Output is correct
2 Correct 22 ms 42596 KB Output is correct
3 Correct 20 ms 42572 KB Output is correct
4 Correct 23 ms 42596 KB Output is correct
5 Correct 20 ms 42636 KB Output is correct
6 Correct 21 ms 42580 KB Output is correct
7 Correct 20 ms 42580 KB Output is correct
8 Correct 23 ms 42580 KB Output is correct
9 Correct 20 ms 42580 KB Output is correct
10 Correct 22 ms 42624 KB Output is correct
11 Correct 22 ms 42564 KB Output is correct
12 Correct 21 ms 42680 KB Output is correct
13 Correct 22 ms 42612 KB Output is correct
14 Correct 19 ms 42676 KB Output is correct
15 Correct 21 ms 42580 KB Output is correct
16 Correct 20 ms 42576 KB Output is correct
17 Correct 20 ms 42636 KB Output is correct
18 Correct 21 ms 42580 KB Output is correct
19 Correct 20 ms 42572 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 42580 KB Output is correct
2 Correct 22 ms 42596 KB Output is correct
3 Correct 20 ms 42572 KB Output is correct
4 Correct 23 ms 42596 KB Output is correct
5 Correct 20 ms 42636 KB Output is correct
6 Correct 21 ms 42580 KB Output is correct
7 Correct 20 ms 42580 KB Output is correct
8 Correct 23 ms 42580 KB Output is correct
9 Correct 20 ms 42580 KB Output is correct
10 Correct 22 ms 42624 KB Output is correct
11 Correct 22 ms 42564 KB Output is correct
12 Correct 21 ms 42680 KB Output is correct
13 Correct 22 ms 42612 KB Output is correct
14 Correct 19 ms 42676 KB Output is correct
15 Correct 21 ms 42580 KB Output is correct
16 Correct 20 ms 42576 KB Output is correct
17 Correct 20 ms 42636 KB Output is correct
18 Correct 21 ms 42580 KB Output is correct
19 Correct 20 ms 42572 KB Output is correct
20 Correct 44 ms 47304 KB Output is correct
21 Correct 47 ms 47180 KB Output is correct
22 Correct 80 ms 57400 KB Output is correct
23 Correct 76 ms 57420 KB Output is correct
24 Correct 77 ms 56272 KB Output is correct
25 Correct 83 ms 58176 KB Output is correct
26 Correct 80 ms 58120 KB Output is correct
27 Correct 79 ms 57856 KB Output is correct
28 Correct 83 ms 56156 KB Output is correct
29 Correct 77 ms 58200 KB Output is correct
30 Correct 59 ms 57984 KB Output is correct
31 Correct 65 ms 57616 KB Output is correct
32 Correct 101 ms 58960 KB Output is correct
33 Correct 81 ms 53452 KB Output is correct
34 Correct 58 ms 49216 KB Output is correct
35 Correct 97 ms 58940 KB Output is correct
36 Correct 83 ms 53564 KB Output is correct
37 Correct 57 ms 49204 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 55884 KB Output is correct
2 Correct 123 ms 55864 KB Output is correct
3 Correct 128 ms 54596 KB Output is correct
4 Correct 124 ms 54708 KB Output is correct
5 Correct 128 ms 57996 KB Output is correct
6 Correct 124 ms 56148 KB Output is correct
7 Correct 107 ms 55836 KB Output is correct
8 Correct 92 ms 55732 KB Output is correct
9 Correct 84 ms 55764 KB Output is correct
10 Correct 76 ms 55884 KB Output is correct
11 Correct 230 ms 61452 KB Output is correct
12 Correct 213 ms 59188 KB Output is correct
13 Correct 186 ms 58056 KB Output is correct
14 Correct 190 ms 58144 KB Output is correct
15 Correct 172 ms 55876 KB Output is correct
16 Correct 167 ms 55828 KB Output is correct
17 Correct 165 ms 55908 KB Output is correct
18 Correct 238 ms 60424 KB Output is correct
19 Correct 20 ms 42580 KB Output is correct
20 Correct 22 ms 42596 KB Output is correct
21 Correct 20 ms 42572 KB Output is correct
22 Correct 23 ms 42596 KB Output is correct
23 Correct 20 ms 42636 KB Output is correct
24 Correct 21 ms 42580 KB Output is correct
25 Correct 20 ms 42580 KB Output is correct
26 Correct 23 ms 42580 KB Output is correct
27 Correct 20 ms 42580 KB Output is correct
28 Correct 22 ms 42624 KB Output is correct
29 Correct 22 ms 42564 KB Output is correct
30 Correct 21 ms 42680 KB Output is correct
31 Correct 22 ms 42612 KB Output is correct
32 Correct 19 ms 42676 KB Output is correct
33 Correct 21 ms 42580 KB Output is correct
34 Correct 20 ms 42576 KB Output is correct
35 Correct 20 ms 42636 KB Output is correct
36 Correct 21 ms 42580 KB Output is correct
37 Correct 20 ms 42572 KB Output is correct
38 Correct 44 ms 47304 KB Output is correct
39 Correct 47 ms 47180 KB Output is correct
40 Correct 80 ms 57400 KB Output is correct
41 Correct 76 ms 57420 KB Output is correct
42 Correct 77 ms 56272 KB Output is correct
43 Correct 83 ms 58176 KB Output is correct
44 Correct 80 ms 58120 KB Output is correct
45 Correct 79 ms 57856 KB Output is correct
46 Correct 83 ms 56156 KB Output is correct
47 Correct 77 ms 58200 KB Output is correct
48 Correct 59 ms 57984 KB Output is correct
49 Correct 65 ms 57616 KB Output is correct
50 Correct 101 ms 58960 KB Output is correct
51 Correct 81 ms 53452 KB Output is correct
52 Correct 58 ms 49216 KB Output is correct
53 Correct 97 ms 58940 KB Output is correct
54 Correct 83 ms 53564 KB Output is correct
55 Correct 57 ms 49204 KB Output is correct
56 Correct 1290 ms 166816 KB Output is correct
57 Runtime error 1388 ms 524288 KB Execution killed with signal 11
58 Halted 0 ms 0 KB -