oj.uz

Submission #674993

# Submission time Handle Problem Language Result Execution time Memory
674993 2022-12-26T18:30:51 Z urosk Treatment Project (JOI20_treatment) C++14
39 / 100
 1387 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 1000005
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 137 ms 65240 KB Output is correct
2 Correct 131 ms 65344 KB Output is correct
3 Correct 129 ms 64040 KB Output is correct
4 Correct 127 ms 64028 KB Output is correct
5 Correct 136 ms 67424 KB Output is correct
6 Correct 124 ms 65464 KB Output is correct
7 Correct 107 ms 65280 KB Output is correct
8 Correct 96 ms 65184 KB Output is correct
9 Correct 92 ms 65172 KB Output is correct
10 Correct 81 ms 65236 KB Output is correct
11 Correct 239 ms 70964 KB Output is correct
12 Correct 226 ms 68624 KB Output is correct
13 Correct 187 ms 67420 KB Output is correct
14 Correct 196 ms 67444 KB Output is correct
15 Correct 169 ms 65324 KB Output is correct
16 Correct 169 ms 65308 KB Output is correct
17 Correct 169 ms 65356 KB Output is correct
18 Correct 222 ms 69908 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 52008 KB Output is correct
2 Correct 23 ms 51948 KB Output is correct
3 Correct 23 ms 52064 KB Output is correct
4 Correct 24 ms 51956 KB Output is correct
5 Correct 23 ms 51972 KB Output is correct
6 Correct 24 ms 52052 KB Output is correct
7 Correct 27 ms 52052 KB Output is correct
8 Correct 24 ms 52052 KB Output is correct
9 Correct 25 ms 51956 KB Output is correct
10 Correct 25 ms 51968 KB Output is correct
11 Correct 23 ms 51968 KB Output is correct
12 Correct 25 ms 52004 KB Output is correct
13 Correct 24 ms 52052 KB Output is correct
14 Correct 25 ms 51968 KB Output is correct
15 Correct 24 ms 51924 KB Output is correct
16 Correct 26 ms 52028 KB Output is correct
17 Correct 25 ms 51988 KB Output is correct
18 Correct 25 ms 52012 KB Output is correct
19 Correct 28 ms 51920 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 52008 KB Output is correct
2 Correct 23 ms 51948 KB Output is correct
3 Correct 23 ms 52064 KB Output is correct
4 Correct 24 ms 51956 KB Output is correct
5 Correct 23 ms 51972 KB Output is correct
6 Correct 24 ms 52052 KB Output is correct
7 Correct 27 ms 52052 KB Output is correct
8 Correct 24 ms 52052 KB Output is correct
9 Correct 25 ms 51956 KB Output is correct
10 Correct 25 ms 51968 KB Output is correct
11 Correct 23 ms 51968 KB Output is correct
12 Correct 25 ms 52004 KB Output is correct
13 Correct 24 ms 52052 KB Output is correct
14 Correct 25 ms 51968 KB Output is correct
15 Correct 24 ms 51924 KB Output is correct
16 Correct 26 ms 52028 KB Output is correct
17 Correct 25 ms 51988 KB Output is correct
18 Correct 25 ms 52012 KB Output is correct
19 Correct 28 ms 51920 KB Output is correct
20 Correct 53 ms 56700 KB Output is correct
21 Correct 50 ms 56572 KB Output is correct
22 Correct 85 ms 66812 KB Output is correct
23 Correct 87 ms 66780 KB Output is correct
24 Correct 87 ms 65664 KB Output is correct
25 Correct 90 ms 67584 KB Output is correct
26 Correct 85 ms 67500 KB Output is correct
27 Correct 86 ms 67020 KB Output is correct
28 Correct 85 ms 65604 KB Output is correct
29 Correct 86 ms 67604 KB Output is correct
30 Correct 67 ms 67356 KB Output is correct
31 Correct 79 ms 66952 KB Output is correct
32 Correct 103 ms 68228 KB Output is correct
33 Correct 86 ms 62796 KB Output is correct
34 Correct 62 ms 58600 KB Output is correct
35 Correct 105 ms 68392 KB Output is correct
36 Correct 86 ms 62908 KB Output is correct
37 Correct 66 ms 58504 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 65240 KB Output is correct
2 Correct 131 ms 65344 KB Output is correct
3 Correct 129 ms 64040 KB Output is correct
4 Correct 127 ms 64028 KB Output is correct
5 Correct 136 ms 67424 KB Output is correct
6 Correct 124 ms 65464 KB Output is correct
7 Correct 107 ms 65280 KB Output is correct
8 Correct 96 ms 65184 KB Output is correct
9 Correct 92 ms 65172 KB Output is correct
10 Correct 81 ms 65236 KB Output is correct
11 Correct 239 ms 70964 KB Output is correct
12 Correct 226 ms 68624 KB Output is correct
13 Correct 187 ms 67420 KB Output is correct
14 Correct 196 ms 67444 KB Output is correct
15 Correct 169 ms 65324 KB Output is correct
16 Correct 169 ms 65308 KB Output is correct
17 Correct 169 ms 65356 KB Output is correct
18 Correct 222 ms 69908 KB Output is correct
19 Correct 23 ms 52008 KB Output is correct
20 Correct 23 ms 51948 KB Output is correct
21 Correct 23 ms 52064 KB Output is correct
22 Correct 24 ms 51956 KB Output is correct
23 Correct 23 ms 51972 KB Output is correct
24 Correct 24 ms 52052 KB Output is correct
25 Correct 27 ms 52052 KB Output is correct
26 Correct 24 ms 52052 KB Output is correct
27 Correct 25 ms 51956 KB Output is correct
28 Correct 25 ms 51968 KB Output is correct
29 Correct 23 ms 51968 KB Output is correct
30 Correct 25 ms 52004 KB Output is correct
31 Correct 24 ms 52052 KB Output is correct
32 Correct 25 ms 51968 KB Output is correct
33 Correct 24 ms 51924 KB Output is correct
34 Correct 26 ms 52028 KB Output is correct
35 Correct 25 ms 51988 KB Output is correct
36 Correct 25 ms 52012 KB Output is correct
37 Correct 28 ms 51920 KB Output is correct
38 Correct 53 ms 56700 KB Output is correct
39 Correct 50 ms 56572 KB Output is correct
40 Correct 85 ms 66812 KB Output is correct
41 Correct 87 ms 66780 KB Output is correct
42 Correct 87 ms 65664 KB Output is correct
43 Correct 90 ms 67584 KB Output is correct
44 Correct 85 ms 67500 KB Output is correct
45 Correct 86 ms 67020 KB Output is correct
46 Correct 85 ms 65604 KB Output is correct
47 Correct 86 ms 67604 KB Output is correct
48 Correct 67 ms 67356 KB Output is correct
49 Correct 79 ms 66952 KB Output is correct
50 Correct 103 ms 68228 KB Output is correct
51 Correct 86 ms 62796 KB Output is correct
52 Correct 62 ms 58600 KB Output is correct
53 Correct 105 ms 68392 KB Output is correct
54 Correct 86 ms 62908 KB Output is correct
55 Correct 66 ms 58504 KB Output is correct
56 Correct 1279 ms 176204 KB Output is correct
57 Runtime error 1387 ms 524288 KB Execution killed with signal 11
58 Halted 0 ms 0 KB -