답안 #1002241

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002241	2024-06-19T11:19:36 Z	Whisper	Fuel Station (NOI20_fuelstation)	C++17	30 / 100	198 ms	18680 KB

FuelStation

#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

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
13.0 / 13.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #6
0 / 11.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #7
0 / 21.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	348 KB	Output isn't correct
4	Halted	0 KB	-

답안 #1002241

Compilation message

Subtask #1 0 / 7.0

Subtask #2 13.0 / 13.0

Subtask #3 17.0 / 17.0

Subtask #4 0 / 12.0

Subtask #5 0 / 19.0

Subtask #6 0 / 11.0

Subtask #7 0 / 21.0

Subtask #1
0 / 7.0

Subtask #2
13.0 / 13.0

Subtask #3
17.0 / 17.0

Subtask #4
0 / 12.0

Subtask #5
0 / 19.0

Subtask #6
0 / 11.0

Subtask #7
0 / 21.0