oj.uz

Submission #941903

# Submission time Handle Problem Language Result Execution time Memory
941903 2024-03-09T16:33:10 Z Tuanlinh123 Treatment Project (JOI20_treatment) C++17
35 / 100
 472 ms 376364 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*40];
long long dis[maxn*40];
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);
    }
    // for (ll i=0; i<sz(p); i++)
    //     for (ll j=0; j<i; j++)
    //         if (p[j].type==0 && p[i].type==1 && p[i].x>=p[j].x && p[i].y>=p[j].y)
    //             A[p[i].id].pb(p[j].id);
    ll k=SegTree::crr;
    // for (ll i=1; i<=k; i++)
    //     for (ll j:A[i])
    //         if (j) cout << i << " " << j << "\n";
    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 451 ms 182204 KB Output is correct
2 Correct 331 ms 184876 KB Output is correct
3 Correct 422 ms 181700 KB Output is correct
4 Correct 436 ms 181608 KB Output is correct
5 Correct 249 ms 149180 KB Output is correct
6 Correct 306 ms 158228 KB Output is correct
7 Correct 366 ms 172192 KB Output is correct
8 Correct 145 ms 146624 KB Output is correct
9 Correct 195 ms 160160 KB Output is correct
10 Correct 206 ms 173280 KB Output is correct
11 Runtime error 472 ms 376364 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 23 ms 99928 KB Output is correct
2 Correct 23 ms 99932 KB Output is correct
3 Correct 22 ms 99932 KB Output is correct
4 Correct 22 ms 99880 KB Output is correct
5 Correct 23 ms 99916 KB Output is correct
6 Correct 24 ms 99932 KB Output is correct
7 Correct 22 ms 99928 KB Output is correct
8 Correct 22 ms 99860 KB Output is correct
9 Correct 22 ms 99680 KB Output is correct
10 Correct 22 ms 99932 KB Output is correct
11 Correct 26 ms 99932 KB Output is correct
12 Correct 22 ms 99932 KB Output is correct
13 Correct 24 ms 99932 KB Output is correct
14 Correct 25 ms 100188 KB Output is correct
15 Correct 25 ms 99944 KB Output is correct
16 Correct 22 ms 99928 KB Output is correct
17 Correct 22 ms 99928 KB Output is correct
18 Correct 23 ms 99940 KB Output is correct
19 Correct 23 ms 99928 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 99928 KB Output is correct
2 Correct 23 ms 99932 KB Output is correct
3 Correct 22 ms 99932 KB Output is correct
4 Correct 22 ms 99880 KB Output is correct
5 Correct 23 ms 99916 KB Output is correct
6 Correct 24 ms 99932 KB Output is correct
7 Correct 22 ms 99928 KB Output is correct
8 Correct 22 ms 99860 KB Output is correct
9 Correct 22 ms 99680 KB Output is correct
10 Correct 22 ms 99932 KB Output is correct
11 Correct 26 ms 99932 KB Output is correct
12 Correct 22 ms 99932 KB Output is correct
13 Correct 24 ms 99932 KB Output is correct
14 Correct 25 ms 100188 KB Output is correct
15 Correct 25 ms 99944 KB Output is correct
16 Correct 22 ms 99928 KB Output is correct
17 Correct 22 ms 99928 KB Output is correct
18 Correct 23 ms 99940 KB Output is correct
19 Correct 23 ms 99928 KB Output is correct
20 Correct 37 ms 102624 KB Output is correct
21 Correct 38 ms 102644 KB Output is correct
22 Correct 36 ms 103040 KB Output is correct
23 Correct 34 ms 102624 KB Output is correct
24 Correct 37 ms 102872 KB Output is correct
25 Correct 38 ms 102872 KB Output is correct
26 Correct 36 ms 102872 KB Output is correct
27 Correct 37 ms 102876 KB Output is correct
28 Correct 38 ms 102968 KB Output is correct
29 Correct 36 ms 102868 KB Output is correct
30 Correct 32 ms 102868 KB Output is correct
31 Correct 31 ms 102880 KB Output is correct
32 Correct 39 ms 103128 KB Output is correct
33 Correct 38 ms 103116 KB Output is correct
34 Correct 38 ms 102876 KB Output is correct
35 Correct 38 ms 103124 KB Output is correct
36 Correct 38 ms 102988 KB Output is correct
37 Correct 39 ms 102868 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 182204 KB Output is correct
2 Correct 331 ms 184876 KB Output is correct
3 Correct 422 ms 181700 KB Output is correct
4 Correct 436 ms 181608 KB Output is correct
5 Correct 249 ms 149180 KB Output is correct
6 Correct 306 ms 158228 KB Output is correct
7 Correct 366 ms 172192 KB Output is correct
8 Correct 145 ms 146624 KB Output is correct
9 Correct 195 ms 160160 KB Output is correct
10 Correct 206 ms 173280 KB Output is correct
11 Runtime error 472 ms 376364 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -