oj.uz

Submission #941904

# Submission time Handle Problem Language Result Execution time Memory
941904 2024-03-09T16:34:10 Z Tuanlinh123 Treatment Project (JOI20_treatment) C++17
35 / 100
 2832 ms 524288 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*80];
long long dis[maxn*80];
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 514 ms 277448 KB Output is correct
2 Correct 346 ms 275548 KB Output is correct
3 Correct 442 ms 273872 KB Output is correct
4 Correct 453 ms 273944 KB Output is correct
5 Correct 253 ms 239804 KB Output is correct
6 Correct 324 ms 249584 KB Output is correct
7 Correct 385 ms 263072 KB Output is correct
8 Correct 166 ms 238012 KB Output is correct
9 Correct 197 ms 251328 KB Output is correct
10 Correct 229 ms 264636 KB Output is correct
11 Runtime error 2832 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 194132 KB Output is correct
2 Correct 45 ms 194236 KB Output is correct
3 Correct 44 ms 194268 KB Output is correct
4 Correct 45 ms 194388 KB Output is correct
5 Correct 44 ms 194384 KB Output is correct
6 Correct 44 ms 194384 KB Output is correct
7 Correct 47 ms 194500 KB Output is correct
8 Correct 45 ms 194384 KB Output is correct
9 Correct 45 ms 194396 KB Output is correct
10 Correct 45 ms 194388 KB Output is correct
11 Correct 44 ms 194392 KB Output is correct
12 Correct 45 ms 194396 KB Output is correct
13 Correct 44 ms 194220 KB Output is correct
14 Correct 45 ms 194408 KB Output is correct
15 Correct 48 ms 194388 KB Output is correct
16 Correct 45 ms 194396 KB Output is correct
17 Correct 46 ms 194396 KB Output is correct
18 Correct 43 ms 194384 KB Output is correct
19 Correct 45 ms 194388 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 194132 KB Output is correct
2 Correct 45 ms 194236 KB Output is correct
3 Correct 44 ms 194268 KB Output is correct
4 Correct 45 ms 194388 KB Output is correct
5 Correct 44 ms 194384 KB Output is correct
6 Correct 44 ms 194384 KB Output is correct
7 Correct 47 ms 194500 KB Output is correct
8 Correct 45 ms 194384 KB Output is correct
9 Correct 45 ms 194396 KB Output is correct
10 Correct 45 ms 194388 KB Output is correct
11 Correct 44 ms 194392 KB Output is correct
12 Correct 45 ms 194396 KB Output is correct
13 Correct 44 ms 194220 KB Output is correct
14 Correct 45 ms 194408 KB Output is correct
15 Correct 48 ms 194388 KB Output is correct
16 Correct 45 ms 194396 KB Output is correct
17 Correct 46 ms 194396 KB Output is correct
18 Correct 43 ms 194384 KB Output is correct
19 Correct 45 ms 194388 KB Output is correct
20 Correct 59 ms 197188 KB Output is correct
21 Correct 58 ms 197136 KB Output is correct
22 Correct 57 ms 197336 KB Output is correct
23 Correct 56 ms 197064 KB Output is correct
24 Correct 59 ms 197168 KB Output is correct
25 Correct 61 ms 197196 KB Output is correct
26 Correct 58 ms 197064 KB Output is correct
27 Correct 55 ms 197076 KB Output is correct
28 Correct 61 ms 197300 KB Output is correct
29 Correct 58 ms 197200 KB Output is correct
30 Correct 54 ms 197192 KB Output is correct
31 Correct 54 ms 197116 KB Output is correct
32 Correct 66 ms 197336 KB Output is correct
33 Correct 59 ms 197336 KB Output is correct
34 Correct 67 ms 197332 KB Output is correct
35 Correct 60 ms 197332 KB Output is correct
36 Correct 61 ms 197496 KB Output is correct
37 Correct 60 ms 197336 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 277448 KB Output is correct
2 Correct 346 ms 275548 KB Output is correct
3 Correct 442 ms 273872 KB Output is correct
4 Correct 453 ms 273944 KB Output is correct
5 Correct 253 ms 239804 KB Output is correct
6 Correct 324 ms 249584 KB Output is correct
7 Correct 385 ms 263072 KB Output is correct
8 Correct 166 ms 238012 KB Output is correct
9 Correct 197 ms 251328 KB Output is correct
10 Correct 229 ms 264636 KB Output is correct
11 Runtime error 2832 ms 524288 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -