oj.uz

Submission #674980

# Submission time Handle Problem Language Result Execution time Memory
674980 2022-12-26T18:23:59 Z urosk Treatment Project (JOI20_treatment) C++14
39 / 100
 2300 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 3000005
ll n,m;
struct tupl{
    ll t,l,r,c;
} a[maxn];
ll tsz = 1,tsz2 = 1;
ll ls[maxx],rs[maxx];
ll ls2[maxx],rs2[maxx];
set<pll> 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++){
        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});
            upd(1,1,mxt,a[i].t,{a[i].l+a[i].t,i},0);
            upd2(1,1,mxt,a[i].t,{a[i].l-a[i].t,i},0);
        }
    }
    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 187 ms 165508 KB Output is correct
2 Correct 187 ms 165540 KB Output is correct
3 Correct 210 ms 165636 KB Output is correct
4 Correct 195 ms 165728 KB Output is correct
5 Correct 203 ms 167620 KB Output is correct
6 Correct 202 ms 165684 KB Output is correct
7 Correct 172 ms 165452 KB Output is correct
8 Correct 156 ms 165384 KB Output is correct
9 Correct 152 ms 165444 KB Output is correct
10 Correct 144 ms 165388 KB Output is correct
11 Correct 307 ms 171084 KB Output is correct
12 Correct 291 ms 168852 KB Output is correct
13 Correct 243 ms 167576 KB Output is correct
14 Correct 265 ms 167632 KB Output is correct
15 Correct 227 ms 165628 KB Output is correct
16 Correct 233 ms 165432 KB Output is correct
17 Correct 219 ms 164704 KB Output is correct
18 Correct 288 ms 169352 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 145948 KB Output is correct
2 Correct 65 ms 145940 KB Output is correct
3 Correct 66 ms 145912 KB Output is correct
4 Correct 66 ms 145932 KB Output is correct
5 Correct 70 ms 146012 KB Output is correct
6 Correct 74 ms 145940 KB Output is correct
7 Correct 66 ms 145988 KB Output is correct
8 Correct 68 ms 145964 KB Output is correct
9 Correct 66 ms 145936 KB Output is correct
10 Correct 78 ms 145916 KB Output is correct
11 Correct 67 ms 146004 KB Output is correct
12 Correct 66 ms 145996 KB Output is correct
13 Correct 67 ms 145988 KB Output is correct
14 Correct 69 ms 145996 KB Output is correct
15 Correct 86 ms 145880 KB Output is correct
16 Correct 70 ms 145912 KB Output is correct
17 Correct 66 ms 145868 KB Output is correct
18 Correct 66 ms 145868 KB Output is correct
19 Correct 67 ms 145876 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 145948 KB Output is correct
2 Correct 65 ms 145940 KB Output is correct
3 Correct 66 ms 145912 KB Output is correct
4 Correct 66 ms 145932 KB Output is correct
5 Correct 70 ms 146012 KB Output is correct
6 Correct 74 ms 145940 KB Output is correct
7 Correct 66 ms 145988 KB Output is correct
8 Correct 68 ms 145964 KB Output is correct
9 Correct 66 ms 145936 KB Output is correct
10 Correct 78 ms 145916 KB Output is correct
11 Correct 67 ms 146004 KB Output is correct
12 Correct 66 ms 145996 KB Output is correct
13 Correct 67 ms 145988 KB Output is correct
14 Correct 69 ms 145996 KB Output is correct
15 Correct 86 ms 145880 KB Output is correct
16 Correct 70 ms 145912 KB Output is correct
17 Correct 66 ms 145868 KB Output is correct
18 Correct 66 ms 145868 KB Output is correct
19 Correct 67 ms 145876 KB Output is correct
20 Correct 110 ms 154204 KB Output is correct
21 Correct 105 ms 154124 KB Output is correct
22 Correct 134 ms 165964 KB Output is correct
23 Correct 150 ms 166048 KB Output is correct
24 Correct 149 ms 168752 KB Output is correct
25 Correct 137 ms 168060 KB Output is correct
26 Correct 134 ms 167324 KB Output is correct
27 Correct 132 ms 166596 KB Output is correct
28 Correct 160 ms 168836 KB Output is correct
29 Correct 131 ms 168148 KB Output is correct
30 Correct 131 ms 167140 KB Output is correct
31 Correct 122 ms 166340 KB Output is correct
32 Correct 157 ms 168784 KB Output is correct
33 Correct 134 ms 160868 KB Output is correct
34 Correct 111 ms 154936 KB Output is correct
35 Correct 156 ms 168764 KB Output is correct
36 Correct 138 ms 160936 KB Output is correct
37 Correct 115 ms 154872 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 165508 KB Output is correct
2 Correct 187 ms 165540 KB Output is correct
3 Correct 210 ms 165636 KB Output is correct
4 Correct 195 ms 165728 KB Output is correct
5 Correct 203 ms 167620 KB Output is correct
6 Correct 202 ms 165684 KB Output is correct
7 Correct 172 ms 165452 KB Output is correct
8 Correct 156 ms 165384 KB Output is correct
9 Correct 152 ms 165444 KB Output is correct
10 Correct 144 ms 165388 KB Output is correct
11 Correct 307 ms 171084 KB Output is correct
12 Correct 291 ms 168852 KB Output is correct
13 Correct 243 ms 167576 KB Output is correct
14 Correct 265 ms 167632 KB Output is correct
15 Correct 227 ms 165628 KB Output is correct
16 Correct 233 ms 165432 KB Output is correct
17 Correct 219 ms 164704 KB Output is correct
18 Correct 288 ms 169352 KB Output is correct
19 Correct 66 ms 145948 KB Output is correct
20 Correct 65 ms 145940 KB Output is correct
21 Correct 66 ms 145912 KB Output is correct
22 Correct 66 ms 145932 KB Output is correct
23 Correct 70 ms 146012 KB Output is correct
24 Correct 74 ms 145940 KB Output is correct
25 Correct 66 ms 145988 KB Output is correct
26 Correct 68 ms 145964 KB Output is correct
27 Correct 66 ms 145936 KB Output is correct
28 Correct 78 ms 145916 KB Output is correct
29 Correct 67 ms 146004 KB Output is correct
30 Correct 66 ms 145996 KB Output is correct
31 Correct 67 ms 145988 KB Output is correct
32 Correct 69 ms 145996 KB Output is correct
33 Correct 86 ms 145880 KB Output is correct
34 Correct 70 ms 145912 KB Output is correct
35 Correct 66 ms 145868 KB Output is correct
36 Correct 66 ms 145868 KB Output is correct
37 Correct 67 ms 145876 KB Output is correct
38 Correct 110 ms 154204 KB Output is correct
39 Correct 105 ms 154124 KB Output is correct
40 Correct 134 ms 165964 KB Output is correct
41 Correct 150 ms 166048 KB Output is correct
42 Correct 149 ms 168752 KB Output is correct
43 Correct 137 ms 168060 KB Output is correct
44 Correct 134 ms 167324 KB Output is correct
45 Correct 132 ms 166596 KB Output is correct
46 Correct 160 ms 168836 KB Output is correct
47 Correct 131 ms 168148 KB Output is correct
48 Correct 131 ms 167140 KB Output is correct
49 Correct 122 ms 166340 KB Output is correct
50 Correct 157 ms 168784 KB Output is correct
51 Correct 134 ms 160868 KB Output is correct
52 Correct 111 ms 154936 KB Output is correct
53 Correct 156 ms 168764 KB Output is correct
54 Correct 138 ms 160936 KB Output is correct
55 Correct 115 ms 154872 KB Output is correct
56 Correct 2300 ms 365568 KB Output is correct
57 Runtime error 1978 ms 524288 KB Execution killed with signal 9
58 Halted 0 ms 0 KB -