oj.uz

Submission #941905

# Submission time Handle Problem Language Result Execution time Memory
941905 2024-03-09T16:34:54 Z Tuanlinh123 Treatment Project (JOI20_treatment) C++17
35 / 100
 477 ms 419964 KB 
#include<bits/stdc++.h>
#define ll int
#define pll pair<long long, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;

const ll maxn=100005;
const long long inf=1e18;

struct seg
{
    ll id, type, x, y;
    seg(){}
    seg(ll id, ll type, ll x, ll y): id(id), type(type), x(x), y(y){}

    bool operator < (const seg &o) const
    {
        if (x!=o.x) return x<o.x;
        if (type!=o.type) return type<o.type;
        return y<o.y;
    }
};

vector <seg> p;
vector <ll> A[maxn*50];
long long dis[maxn*50];
ll x[maxn], l[maxn], r[maxn], w[maxn];

namespace SegTree
{
    ll n, crr, St[maxn*4]={};
    void init(ll sz, ll m) {n=sz, crr=m;}

    void update(ll i, ll Start, ll End, ll idx, ll val)
    {
        if (Start>idx || End<idx) return;
        if (Start==End) {A[++crr].pb(St[i]), St[i]=crr, A[St[i]].pb(val); return;}
        ll mid=(Start+End)/2;
        A[++crr].pb(St[i]), St[i]=crr;
        if (idx<=mid) update(i*2, Start, mid, idx, val), A[St[i]].pb(St[i*2]);
        else update(i*2+1, mid+1, End, idx, val), A[St[i]].pb(St[i*2+1]);
    }
    void update(ll idx, ll val){update(1, 1, n, idx, val);}

    void query(ll i, ll Start, ll End, ll l, ll r, ll val)
    {
        if (Start>r || End<l) return;
        if (Start>=l && End<=r) {A[val].pb(St[i]); return;}
        ll mid=(Start+End)/2;
        if (mid>=l) query(i*2, Start, mid, l, r, val);
        if (mid+1<=r) query(i*2+1, mid+1, End, l, r, val);
    }
    void query(ll l, ll r, ll val){query(1, 1, n, l, r, val);}
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, m; cin >> n >> m;
    for (ll i=1; i<=m; i++)
    {
        cin >> x[i] >> l[i] >> r[i] >> w[i];
        p.emplace_back(i, 0, x[i]+l[i], l[i]-x[i]);
        p.emplace_back(i, 1, x[i]+r[i]+1, r[i]+1-x[i]);
    }
    vector <ll> cx, cy;
    for (seg &s:p) cx.pb(s.x), cy.pb(s.y);
    sort(cx.begin(), cx.end());
    cx.resize(unique(cx.begin(), cx.end())-cx.begin());
    sort(cy.begin(), cy.end());
    cy.resize(unique(cy.begin(), cy.end())-cy.begin());
    for (seg &s: p)
    {
        s.x=lower_bound(cx.begin(), cx.end(), s.x)-cx.begin()+1;
        s.y=lower_bound(cy.begin(), cy.end(), s.y)-cy.begin()+1;
    }
    sort(p.begin(), p.end());
    SegTree::init(sz(cy), m);
    for (seg &s: p)
    {
        ll id=s.id, t=s.type, p=s.y;
        if (!t) SegTree::update(p, id);
        else SegTree::query(1, p, id);
    }
    ll k=SegTree::crr;
    priority_queue <pll, vector <pll>, greater<pll>> q;
    for (ll i=1; i<=k; i++)
    {
        if (i<=m && l[i]==1) dis[i]=w[i], q.push({dis[i], i});
        else dis[i]=inf;   
    }
    while (!q.empty())
    {
        long long u=q.top().se, disu=q.top().fi; q.pop();
        if (dis[u]!=disu) continue;
        for (ll v:A[u])
            if (dis[v]>disu+(v<=m?w[v]:0))
                dis[v]=disu+(v<=m?w[v]:0), q.push({dis[v], v});
    }
    long long ans=inf;
    for (ll i=1; i<=m; i++)
        if (r[i]==n) ans=min(ans, dis[i]);
    if (ans==inf) cout << "-1";
    else cout << ans;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 206276 KB Output is correct
2 Correct 323 ms 204236 KB Output is correct
3 Correct 473 ms 203712 KB Output is correct
4 Correct 453 ms 202624 KB Output is correct
5 Correct 246 ms 168024 KB Output is correct
6 Correct 317 ms 178884 KB Output is correct
7 Correct 378 ms 191932 KB Output is correct
8 Correct 145 ms 166632 KB Output is correct
9 Correct 182 ms 179676 KB Output is correct
10 Correct 227 ms 193524 KB Output is correct
11 Runtime error 477 ms 419964 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 122968 KB Output is correct
2 Correct 27 ms 122972 KB Output is correct
3 Correct 29 ms 122968 KB Output is correct
4 Correct 28 ms 122972 KB Output is correct
5 Correct 28 ms 122872 KB Output is correct
6 Correct 27 ms 122972 KB Output is correct
7 Correct 28 ms 122972 KB Output is correct
8 Correct 27 ms 122972 KB Output is correct
9 Correct 28 ms 122968 KB Output is correct
10 Correct 27 ms 123024 KB Output is correct
11 Correct 30 ms 123048 KB Output is correct
12 Correct 28 ms 122972 KB Output is correct
13 Correct 28 ms 122972 KB Output is correct
14 Correct 28 ms 122972 KB Output is correct
15 Correct 28 ms 122972 KB Output is correct
16 Correct 28 ms 122972 KB Output is correct
17 Correct 28 ms 122972 KB Output is correct
18 Correct 27 ms 122972 KB Output is correct
19 Correct 28 ms 122972 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 122968 KB Output is correct
2 Correct 27 ms 122972 KB Output is correct
3 Correct 29 ms 122968 KB Output is correct
4 Correct 28 ms 122972 KB Output is correct
5 Correct 28 ms 122872 KB Output is correct
6 Correct 27 ms 122972 KB Output is correct
7 Correct 28 ms 122972 KB Output is correct
8 Correct 27 ms 122972 KB Output is correct
9 Correct 28 ms 122968 KB Output is correct
10 Correct 27 ms 123024 KB Output is correct
11 Correct 30 ms 123048 KB Output is correct
12 Correct 28 ms 122972 KB Output is correct
13 Correct 28 ms 122972 KB Output is correct
14 Correct 28 ms 122972 KB Output is correct
15 Correct 28 ms 122972 KB Output is correct
16 Correct 28 ms 122972 KB Output is correct
17 Correct 28 ms 122972 KB Output is correct
18 Correct 27 ms 122972 KB Output is correct
19 Correct 28 ms 122972 KB Output is correct
20 Correct 44 ms 125608 KB Output is correct
21 Correct 45 ms 125664 KB Output is correct
22 Correct 44 ms 125788 KB Output is correct
23 Correct 39 ms 125664 KB Output is correct
24 Correct 44 ms 125912 KB Output is correct
25 Correct 43 ms 125652 KB Output is correct
26 Correct 41 ms 125664 KB Output is correct
27 Correct 39 ms 125660 KB Output is correct
28 Correct 43 ms 125892 KB Output is correct
29 Correct 45 ms 125700 KB Output is correct
30 Correct 38 ms 125916 KB Output is correct
31 Correct 37 ms 125720 KB Output is correct
32 Correct 44 ms 125908 KB Output is correct
33 Correct 50 ms 125992 KB Output is correct
34 Correct 44 ms 126164 KB Output is correct
35 Correct 44 ms 126048 KB Output is correct
36 Correct 44 ms 126028 KB Output is correct
37 Correct 44 ms 125964 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 206276 KB Output is correct
2 Correct 323 ms 204236 KB Output is correct
3 Correct 473 ms 203712 KB Output is correct
4 Correct 453 ms 202624 KB Output is correct
5 Correct 246 ms 168024 KB Output is correct
6 Correct 317 ms 178884 KB Output is correct
7 Correct 378 ms 191932 KB Output is correct
8 Correct 145 ms 166632 KB Output is correct
9 Correct 182 ms 179676 KB Output is correct
10 Correct 227 ms 193524 KB Output is correct
11 Runtime error 477 ms 419964 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -