oj.uz

Submission #1039197

# Submission time Handle Problem Language Result Execution time Memory
1039197 2024-07-30T14:26:39 Z Whisper Pinball (JOI14_pinball) C++17
29 / 100
 30 ms 66604 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (b); i >= (a); i --)
#define REP(i, a) for (int i = 0; i < (a); ++i)
#define REPD(i, a) for (int i = (a) - 1; i >= 0; --i)

#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)


constexpr ll LINF = (1ll << 60);
constexpr int INF = (1ll << 30);
constexpr int Mod = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

/*
    Phu Trong from Nguyen Tat Thanh High School for gifted student
*/

template <class X, class Y>
    bool minimize(X &x, const Y &y){
        X eps = 1e-9;
        if (x > y + eps) {x = y; return 1;}
        return 0;
    }

template <class X, class Y>
    bool maximize(X &x, const Y &y){
        X eps = 1e-9;
        if (x + eps < y) {x = y; return 1;}
        return 0;
    }
int N, M;
#define MAX         100005

struct Info{
    int l, r, m, c;
    Info(){}
    Info(int _l, int _r, int _m, int _c): l(_l), r(_r), m(_m), c(_c){}

    friend istream &operator >> (istream& cin, Info& x){
        cin >> x.l >> x.r >> x.m >> x.c;
        return cin;
    }
} A[MAX];
vector<int> comp;
int find(int x){
    return lower_bound(comp.begin(), comp.end(), x) - comp.begin() + 1;
}

int l[MAX], r[MAX];
namespace SUBTASK_3{
    bool check(void){
        return (M <= 2000);
    }

    void main(void){
        memset(l, 0x3f, (N + 1) * sizeof(int));
        memset(r, 0x3f, (N + 1) * sizeof(int));
        for (int i = 1; i <= N; ++i){
            if (A[i].l == 1) l[i] = A[i].c;
            if (A[i].r == M) r[i] = A[i].c;
            for (int j = 1; j < i; ++j){
                if (A[i].l <= A[j].m && A[j].m <= A[i].r){
                    minimize(l[i], l[j] + A[i].c);
                }
                if (A[i].l <= A[j].m && A[j].m <= A[i].r){
                    minimize(r[i], r[j] + A[i].c);
                }
            }
        }
        int ans = LINF;
        for (int i = 1; i <= N; ++i){
            minimize(ans, l[i] + r[i] - A[i].c);
        }
        cout << (ans >= 1e15 ? -1 : ans);
    }
}


namespace SUBTASK_5{
    struct SegmentTree{
        vector<int> st;
        int n;
        SegmentTree(int _n = 0){
            init(n);
        }
        void init(int _n){
            st.clear();
            this -> n = _n;
            st.resize((n << 1), LINF);
        }
        void upd(int p, int val){
            for (minimize(st[p += n], val); p > 0; p >>= 1){
                st[p >> 1] = min(st[p], st[p ^ 1]);
            }
        }
        int query(int l, int r){
            int res = LINF;
            for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1){
                if (l & 1) minimize(res, st[l++]);
                if (r & 1) minimize(res, st[--r]);
            }
            return res;
        }
    };
    void main(void){
        memset(l, 0x3f, (N + 1) * sizeof(int));
        memset(r, 0x3f, (N + 1) * sizeof(int));
        #define SZ(a) (int)a.size()
        SegmentTree myit(SZ(comp) + 1);

        for (int i = 1; i <= N; ++i){
            if (A[i].l == 1) l[i] = A[i].c;
            minimize(l[i], myit.query(A[i].l, A[i].r) + A[i].c);
            myit.upd(A[i].m, l[i]);
        }

        myit.init(SZ(comp));
        for (int i = 1; i <= N; ++i){
            if (A[i].r == M) r[i] = A[i].c;
            minimize(r[i], myit.query(A[i].l, A[i].r) + A[i].c);
            myit.upd(A[i].m, r[i]);
        }
        int ans = LINF;
        for (int i = 1; i <= N; ++i){
            minimize(ans, l[i] + r[i] - A[i].c);
        }
        cout << (ans >= 1e15 ? -1 : ans);
    }
}
void process(void){
    cin >> N >> M;
    for (int i = 1; i <= N; ++i){
        cin >> A[i];
        comp.push_back(A[i].l);
        comp.push_back(A[i].r);
        comp.push_back(A[i].m);
    }
    if(SUBTASK_3 :: check()) {
        SUBTASK_3 :: main(); return;
    }
//    comp.push_back(1);
    comp.push_back(M);
    sort(comp.begin(), comp.end());
    comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
    for (int i = 1; i <= N; ++i){
        A[i].l = find(A[i].l);
        A[i].r = find(A[i].r);
        A[i].m = find(A[i].m);
    }
    M = find(M);

    SUBTASK_5 :: main();
}
signed main(){
    #define name "Whisper"
    cin.tie(nullptr) -> sync_with_stdio(false);
    //freopen(name".inp", "r", stdin);
    //freopen(name".out", "w", stdout);
    process();
    return (0 ^ 0);
}

Compilation message

pinball.cpp: In function 'void SUBTASK_5::main()':
pinball.cpp:91:17: warning: 'myit.SUBTASK_5::SegmentTree::n' is used uninitialized in this function [-Wuninitialized]
   91 |             init(n);
      |             ~~~~^~~

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 424 KB Output is correct
5 Correct 0 ms 428 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 28 ms 66384 KB Output is correct
10 Correct 26 ms 66444 KB Output is correct
11 Correct 29 ms 66388 KB Output is correct
12 Correct 26 ms 66396 KB Output is correct
13 Correct 24 ms 66384 KB Output is correct
14 Correct 25 ms 66392 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 424 KB Output is correct
5 Correct 0 ms 428 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 28 ms 66384 KB Output is correct
10 Correct 26 ms 66444 KB Output is correct
11 Correct 29 ms 66388 KB Output is correct
12 Correct 26 ms 66396 KB Output is correct
13 Correct 24 ms 66384 KB Output is correct
14 Correct 25 ms 66392 KB Output is correct
15 Correct 25 ms 66392 KB Output is correct
16 Correct 25 ms 66392 KB Output is correct
17 Correct 27 ms 66604 KB Output is correct
18 Correct 30 ms 66552 KB Output is correct
19 Incorrect 26 ms 66404 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 424 KB Output is correct
5 Correct 0 ms 428 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 28 ms 66384 KB Output is correct
10 Correct 26 ms 66444 KB Output is correct
11 Correct 29 ms 66388 KB Output is correct
12 Correct 26 ms 66396 KB Output is correct
13 Correct 24 ms 66384 KB Output is correct
14 Correct 25 ms 66392 KB Output is correct
15 Correct 25 ms 66392 KB Output is correct
16 Correct 25 ms 66392 KB Output is correct
17 Correct 27 ms 66604 KB Output is correct
18 Correct 30 ms 66552 KB Output is correct
19 Incorrect 26 ms 66404 KB Output isn't correct
20 Halted 0 ms 0 KB -