oj.uz

Submission #1047853

# Submission time Handle Problem Language Result Execution time Memory
1047853 2024-08-07T16:42:19 Z KiaRez Treatment Project (JOI20_treatment) C++17
35 / 100
 357 ms 524288 KB 
/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int M = 1e5+5, N = 3e5+23, lg = 17;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int m, n, par[N], L[N], R[N], t[N], p[N], seg[N];
ll c[N], d[N * 3 * lg], id=1;
bool mark[N * 3 * lg];
vector<int> adj[N * 3 * lg];
vector<int> comp[2];
bool cmp(int i, int j) {
    return (t[i] < t[j]);
}

void query(int v, int l, int r, int ind=1, int lc=1, int rc=(1<<lg)+1) {
    if(lc >= r) return;
    if(rc <= r) {
        adj[v].pb(seg[ind]); return;
    }
    int mid = (lc+rc)/2;
    query(v, l, r, 2*ind, lc, mid);
    query(v, l, r, 2*ind+1, mid, rc);
}

void update(int ind, int v) {
    adj[id].pb(seg[ind]);
    adj[id].pb(v);
    seg[ind] = id; 
    ind/=2; id++;
    while(ind > 0) {
        seg[ind] = id++;
        adj[seg[ind]].pb(seg[2*ind]);
        adj[seg[ind]].pb(seg[2*ind+1]);
        ind /= 2;
    }
}

int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n>>m; id = m + 1;
    for(int i=1; i<=m; i++) {
        cin>>t[i]>>L[i]>>R[i]>>c[i];
        p[i] = i;
        comp[0].pb(L[i]-t[i]);
        comp[1].pb(L[i]+t[i]);
    }
    sort(p+1, p+m+1, cmp);

    for(int i=(1<<(lg + 1)); i>=1; i--) {
        seg[i] = id ++;
        if(i < (1<<lg)) {
            adj[seg[i]].pb(seg[2*i]);
            adj[seg[i]].pb(seg[2*i+1]);
        }
    }

    comp[0].pb(2e9); comp[1].pb(2e9);
sort(all(comp[0])); comp[0].resize(unique(all(comp[0]))-comp[0].begin());
sort(all(comp[1])); comp[1].resize(unique(all(comp[1]))-comp[1].begin());
    
    for(int i=1; i<=m; i++) {
        int ptr = lower_bound(all(comp[0]), R[p[i]]-t[p[i]]+2)-comp[0].begin();
        if(ptr != 0) {
            query(p[i], 1, ptr + 1);
        }
        ptr = lower_bound(all(comp[0]), L[p[i]]-t[p[i]])-comp[0].begin()+1;
        update((1<<lg)+ptr-1, p[i]);
    }

    for(int i=(1<<(lg + 1)); i>=1; i--) {
        seg[i] = id ++;
        if(i < (1<<lg)) {
            adj[seg[i]].pb(seg[2*i]);
            adj[seg[i]].pb(seg[2*i+1]);
        }
    }
    
    for(int i=m; i>=1; i--) {
        int ptr = lower_bound(all(comp[1]), R[p[i]]+t[p[i]]+2)-comp[1].begin();
        if(ptr != 0) {
            query(p[i], 1, ptr + 1);
        }
        ptr = lower_bound(all(comp[1]), L[p[i]]+t[p[i]])-comp[1].begin()+1;
        update((1<<lg)+ptr-1, p[i]);
    }

    priority_queue<pll, vector<pll>, greater<pll>> pq;
    for(int i=1; i<=m; i++) {
        if(L[i] == 1) {
            pq.push({c[i], i});
        }
    }

    while(size(pq) > 0) {
        pll v = pq.top(); pq.pop(); 
        if(mark[v.S] == 1) continue;
        // fuck(v.S);

        d[v.S] = v.F, mark[v.S] = 1;
        for(auto u : adj[v.S]) {
            if(mark[u] == 1) continue;
            pq.push({v.F+(u <= m ? c[u] : 0ll), u});
        }
    }

    ll ans = 2e18;
    for(int i=1 ; i<=m; i++) {
        if(d[i] == 0) continue;
        if(R[i] == n) {
            ans = min(ans, d[i]);
        }
    }

    cout<<(ans==2e18 ? -1 : ans)<<endl;

	return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 357 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 368828 KB Output is correct
2 Correct 99 ms 368984 KB Output is correct
3 Correct 100 ms 368976 KB Output is correct
4 Correct 100 ms 368976 KB Output is correct
5 Correct 105 ms 369088 KB Output is correct
6 Correct 99 ms 369012 KB Output is correct
7 Correct 99 ms 368976 KB Output is correct
8 Correct 100 ms 368980 KB Output is correct
9 Correct 104 ms 368980 KB Output is correct
10 Correct 99 ms 369064 KB Output is correct
11 Correct 104 ms 368856 KB Output is correct
12 Correct 99 ms 368976 KB Output is correct
13 Correct 115 ms 368980 KB Output is correct
14 Correct 99 ms 368976 KB Output is correct
15 Correct 104 ms 369180 KB Output is correct
16 Correct 100 ms 368980 KB Output is correct
17 Correct 100 ms 368984 KB Output is correct
18 Correct 100 ms 368976 KB Output is correct
19 Correct 102 ms 368940 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 368828 KB Output is correct
2 Correct 99 ms 368984 KB Output is correct
3 Correct 100 ms 368976 KB Output is correct
4 Correct 100 ms 368976 KB Output is correct
5 Correct 105 ms 369088 KB Output is correct
6 Correct 99 ms 369012 KB Output is correct
7 Correct 99 ms 368976 KB Output is correct
8 Correct 100 ms 368980 KB Output is correct
9 Correct 104 ms 368980 KB Output is correct
10 Correct 99 ms 369064 KB Output is correct
11 Correct 104 ms 368856 KB Output is correct
12 Correct 99 ms 368976 KB Output is correct
13 Correct 115 ms 368980 KB Output is correct
14 Correct 99 ms 368976 KB Output is correct
15 Correct 104 ms 369180 KB Output is correct
16 Correct 100 ms 368980 KB Output is correct
17 Correct 100 ms 368984 KB Output is correct
18 Correct 100 ms 368976 KB Output is correct
19 Correct 102 ms 368940 KB Output is correct
20 Correct 131 ms 377316 KB Output is correct
21 Correct 119 ms 377424 KB Output is correct
22 Correct 115 ms 377176 KB Output is correct
23 Correct 122 ms 377168 KB Output is correct
24 Correct 133 ms 377428 KB Output is correct
25 Correct 120 ms 377156 KB Output is correct
26 Correct 133 ms 377224 KB Output is correct
27 Correct 119 ms 377172 KB Output is correct
28 Correct 120 ms 377352 KB Output is correct
29 Correct 117 ms 377172 KB Output is correct
30 Correct 111 ms 375376 KB Output is correct
31 Correct 116 ms 375376 KB Output is correct
32 Correct 125 ms 377544 KB Output is correct
33 Correct 136 ms 377552 KB Output is correct
34 Correct 125 ms 377124 KB Output is correct
35 Correct 125 ms 377516 KB Output is correct
36 Correct 128 ms 377408 KB Output is correct
37 Correct 123 ms 377100 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 357 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -