oj.uz

Submission #1002241

# Submission time Handle Problem Language Result Execution time Memory
1002241 2024-06-19T11:19:36 Z Whisper Fuel Station (NOI20_fuelstation) C++17
30 / 100
 198 ms 18680 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, n) for (int i = 0; i < (n); ++i)
#define REPD(i, n) for (int i = (n) - 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, K;
#define MAX     300005
struct Event{
    int X, A, B;
    Event(){}
    Event(int _X, int _A, int _B): X(_X), A(_A), B(_B){}

    bool operator < (const Event& oth) const{
        return B > oth.B;
    }
} A[MAX];

template <class T = vector<int>>
    T unique(T v){
        sort(v.begin(), v.end());
        v.resize(unique(v.begin(), v.end()) - v.begin());
        return v;
    }
template <class T = int>
    T find(T x, const vector<T>& v){
        return upper_bound(v.begin(), v.end(), x) - v.begin();
    }

template <class T = int> struct SegmentTree{
    int n;
    vector<T> st, lz;
    SegmentTree(int _n){
        this -> n = _n;
        st.resize((n << 2) + 5);
        lz.resize((n << 2) + 5);
    }

    void pushDown(int id){
        if (!lz[id]) return;
        st[id << 1] += lz[id];
        st[id << 1 | 1] += lz[id];
        lz[id << 1] += lz[id];
        lz[id << 1 | 1] += lz[id];
        lz[id] = 0;
    }
    void upd(int id, int l, int r, int u, int v, T val){
        if (u > r || v < l) return;
        if (u <= l && v >= r){
            st[id] += val; lz[id] += val;
            return;
        }
        int m = (l + r) >> 1;
        pushDown(id);
        upd(id << 1, l, m, u, v, val);
        upd(id << 1 | 1, m + 1, r, u, v, val);
        st[id] = min(st[id << 1], st[id << 1 | 1]);
    }
    void upd(int l, int r, T val){
        upd(1, 0, n, l, r, val);
    }
};

void process(void){
    cin >> N >> K;
    vector<Event> event;

    vector<int> pos;
    for (int i = 1; i <= N; ++i){
        int x, a, b; cin >> x >> a >> b;
        event.push_back(Event(x, a, b));
        pos.push_back(x);
    }
    pos.push_back(0); pos.push_back(K);
    pos = unique(pos);

    N = (int)pos.size() - 1;
    SegmentTree<int> st(N);

    for (int i = 0; i < N; ++i){
        st.upd(i, i, -pos[i]);
    }

    sort(event.begin(), event.end());
    int ans = K;
    for (auto&x : event){
        int p = find(x.X, pos);
        st.upd(p, N, x.A);
        if (abs(st.st[1]) <= x.B){
            minimize(ans, abs(st.st[1]));
        }
    }
    cout << ans;
}

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

    process();
}

Subtask #1
0 / 7.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 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 18468 KB Output is correct
2 Correct 160 ms 17996 KB Output is correct
3 Correct 157 ms 18676 KB Output is correct
4 Correct 125 ms 17416 KB Output is correct
5 Correct 119 ms 17660 KB Output is correct
6 Correct 149 ms 18416 KB Output is correct
7 Correct 149 ms 18384 KB Output is correct
8 Correct 116 ms 16888 KB Output is correct
9 Correct 162 ms 18164 KB Output is correct
10 Correct 114 ms 17148 KB Output is correct
11 Correct 149 ms 17912 KB Output is correct
12 Correct 116 ms 17344 KB Output is correct
13 Correct 155 ms 17912 KB Output is correct
14 Correct 146 ms 16892 KB Output is correct
15 Correct 116 ms 18680 KB Output is correct
16 Correct 198 ms 17144 KB Output is correct
17 Correct 115 ms 17556 KB Output is correct
18 Correct 156 ms 18680 KB Output is correct
19 Correct 129 ms 17816 KB Output is correct
20 Correct 174 ms 17316 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 3 ms 920 KB Output is correct
3 Correct 7 ms 1432 KB Output is correct
4 Correct 6 ms 1560 KB Output is correct
5 Correct 7 ms 1432 KB Output is correct
6 Correct 8 ms 1432 KB Output is correct
7 Correct 7 ms 1432 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 4 ms 920 KB Output is correct
15 Correct 6 ms 916 KB Output is correct
16 Correct 5 ms 920 KB Output is correct
17 Correct 5 ms 920 KB Output is correct
18 Correct 5 ms 920 KB Output is correct
19 Correct 3 ms 920 KB Output is correct
20 Correct 4 ms 920 KB Output is correct
21 Correct 5 ms 920 KB Output is correct
22 Correct 3 ms 920 KB Output is correct
23 Correct 3 ms 920 KB Output is correct
24 Correct 5 ms 920 KB Output is correct
25 Correct 4 ms 920 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 110 ms 16792 KB Output is correct
28 Correct 148 ms 17712 KB Output is correct
29 Correct 151 ms 18552 KB Output is correct
30 Correct 172 ms 18676 KB Output is correct
31 Correct 147 ms 18512 KB Output is correct
32 Correct 144 ms 18672 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Incorrect 1 ms 348 KB Output isn't correct
38 Halted 0 ms 0 KB -

Subtask #5
0 / 19.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 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
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 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 21.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 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -