oj.uz

Submission #941906

# Submission time Handle Problem Language Result Execution time Memory
941906 2024-03-09T16:35:25 Z Tuanlinh123 Treatment Project (JOI20_treatment) C++17
35 / 100
 530 ms 466876 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*60];
long long dis[maxn*60];
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 530 ms 228788 KB Output is correct
2 Correct 333 ms 226972 KB Output is correct
3 Correct 433 ms 226236 KB Output is correct
4 Correct 436 ms 225748 KB Output is correct
5 Correct 260 ms 192572 KB Output is correct
6 Correct 304 ms 201452 KB Output is correct
7 Correct 391 ms 214856 KB Output is correct
8 Correct 150 ms 190396 KB Output is correct
9 Correct 204 ms 203712 KB Output is correct
10 Correct 226 ms 216592 KB Output is correct
11 Runtime error 513 ms 466876 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 33 ms 146004 KB Output is correct
2 Correct 35 ms 146148 KB Output is correct
3 Correct 33 ms 146008 KB Output is correct
4 Correct 33 ms 146004 KB Output is correct
5 Correct 33 ms 146004 KB Output is correct
6 Correct 32 ms 146104 KB Output is correct
7 Correct 33 ms 146008 KB Output is correct
8 Correct 33 ms 146088 KB Output is correct
9 Correct 32 ms 146000 KB Output is correct
10 Correct 33 ms 146000 KB Output is correct
11 Correct 35 ms 146012 KB Output is correct
12 Correct 32 ms 146012 KB Output is correct
13 Correct 32 ms 146012 KB Output is correct
14 Correct 33 ms 146012 KB Output is correct
15 Correct 33 ms 146012 KB Output is correct
16 Correct 32 ms 146132 KB Output is correct
17 Correct 32 ms 146132 KB Output is correct
18 Correct 33 ms 146004 KB Output is correct
19 Correct 33 ms 146012 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 146004 KB Output is correct
2 Correct 35 ms 146148 KB Output is correct
3 Correct 33 ms 146008 KB Output is correct
4 Correct 33 ms 146004 KB Output is correct
5 Correct 33 ms 146004 KB Output is correct
6 Correct 32 ms 146104 KB Output is correct
7 Correct 33 ms 146008 KB Output is correct
8 Correct 33 ms 146088 KB Output is correct
9 Correct 32 ms 146000 KB Output is correct
10 Correct 33 ms 146000 KB Output is correct
11 Correct 35 ms 146012 KB Output is correct
12 Correct 32 ms 146012 KB Output is correct
13 Correct 32 ms 146012 KB Output is correct
14 Correct 33 ms 146012 KB Output is correct
15 Correct 33 ms 146012 KB Output is correct
16 Correct 32 ms 146132 KB Output is correct
17 Correct 32 ms 146132 KB Output is correct
18 Correct 33 ms 146004 KB Output is correct
19 Correct 33 ms 146012 KB Output is correct
20 Correct 49 ms 148700 KB Output is correct
21 Correct 47 ms 148704 KB Output is correct
22 Correct 46 ms 149064 KB Output is correct
23 Correct 50 ms 148708 KB Output is correct
24 Correct 54 ms 148948 KB Output is correct
25 Correct 49 ms 148696 KB Output is correct
26 Correct 49 ms 148692 KB Output is correct
27 Correct 44 ms 148780 KB Output is correct
28 Correct 50 ms 149032 KB Output is correct
29 Correct 56 ms 149048 KB Output is correct
30 Correct 42 ms 148948 KB Output is correct
31 Correct 44 ms 148980 KB Output is correct
32 Correct 56 ms 149208 KB Output is correct
33 Correct 50 ms 149212 KB Output is correct
34 Correct 50 ms 149084 KB Output is correct
35 Correct 56 ms 149208 KB Output is correct
36 Correct 49 ms 149208 KB Output is correct
37 Correct 56 ms 148948 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 530 ms 228788 KB Output is correct
2 Correct 333 ms 226972 KB Output is correct
3 Correct 433 ms 226236 KB Output is correct
4 Correct 436 ms 225748 KB Output is correct
5 Correct 260 ms 192572 KB Output is correct
6 Correct 304 ms 201452 KB Output is correct
7 Correct 391 ms 214856 KB Output is correct
8 Correct 150 ms 190396 KB Output is correct
9 Correct 204 ms 203712 KB Output is correct
10 Correct 226 ms 216592 KB Output is correct
11 Runtime error 513 ms 466876 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -