oj.uz

Submission #463730

# Submission time Handle Problem Language Result Execution time Memory
463730 2021-08-11T16:06:33 Z Nima_Naderi Pinball (JOI14_pinball) C++14
51 / 100
 185 ms 26032 KB 
///In the name of GOD
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef tuple<ll, ll, ll, ll> tpl;
const ll MXN = 2e5 + 10;
const ll MXS = MXN * 2;
const ll INF = 1e18;
ll n, m, k, ans;
ll A[MXN], B[MXN], C[MXN], D[MXN];
vector<ll> Num;
inline int GetId(ll x){
    return lower_bound(Num.begin(), Num.end(), x) - Num.begin() + 1;
}
struct Segtree {
    ll seg[MXS], lim;//lim as size
    void init(){
        lim = k + 1;
        for(int i = lim << 1; -- i; ) seg[i] = INF;
    }
    void Upd(ll p, ll x){
        p += lim;
        while(p) seg[p] = min(seg[p], x), p >>= 1;
    }
    ll Get(ll l, ll r){
        ll res = INF; l += lim, r += lim;
        while(l <= r){
            if((l & 1) == 1) res = min(res, seg[l]), l ++;
            if((r & 1) == 0) res = min(res, seg[r]), r --;
            l >>= 1, r >>= 1;
        }
        return res;
    }
} SL, SR;
int main(){
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    cin >> n >> m, ans = INF;
    for(int i = 1; i <= n; i ++){
        cin >> A[i] >> B[i] >> C[i] >> D[i];
        Num.push_back(A[i]), Num.push_back(B[i]), Num.push_back(C[i]);
    }
    Num.push_back(1), Num.push_back(m);
    sort(Num.begin(), Num.end());
    Num.resize(k = unique(Num.begin(), Num.end()) - Num.begin());
    SL.init(), SR.init();
    SL.Upd(1, 0), SR.Upd(k, 0);
    for(int i = 1; i <= n; i ++){
        A[i] = GetId(A[i]), B[i] = GetId(B[i]), C[i] = GetId(C[i]);
        ll cl = SL.Get(A[i], B[i]), cr = SR.Get(A[i], B[i]);
        ans = min(ans, cl + cr + D[i]);
        cl += D[i], cr += D[i];
        SL.Upd(C[i], cl), SR.Upd(C[i], cr);
    }
    cout << (ans == INF ? -1 : ans) << '\n';
    return 0;
}
/*!
    HE'S AN INSTIGATOR,
    ENEMY ELIMINATOR,
    AND WHEN HE KNOCKS YOU BETTER
    YOU BETTER LET HIM IN.
*/
//! N.N

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 2 ms 460 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 2 ms 460 KB Output is correct
20 Correct 2 ms 460 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 2 ms 460 KB Output is correct
23 Correct 1 ms 460 KB Output is correct
24 Correct 1 ms 460 KB Output is correct
25 Correct 14 ms 1508 KB Output is correct
26 Correct 40 ms 3528 KB Output is correct
27 Correct 116 ms 7488 KB Output is correct
28 Correct 113 ms 7236 KB Output is correct
29 Correct 82 ms 6056 KB Output is correct
30 Correct 138 ms 7236 KB Output is correct
31 Correct 185 ms 11196 KB Output is correct
32 Correct 175 ms 9720 KB Output is correct
33 Correct 22 ms 3404 KB Output is correct
34 Correct 80 ms 7820 KB Output is correct
35 Runtime error 84 ms 26032 KB Execution killed with signal 11
36 Halted 0 ms 0 KB -