답안 #1002238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002238	2024-06-19T11:18:05 Z	vjudge1	Fuel Station (NOI20_fuelstation)	C++17	30 / 100	161 ms	26368 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     500005
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, 1, 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	161 ms	24824 KB	Output is correct
2	Correct	156 ms	25332 KB	Output is correct
3	Correct	154 ms	26100 KB	Output is correct
4	Correct	121 ms	24740 KB	Output is correct
5	Correct	128 ms	25080 KB	Output is correct
6	Correct	150 ms	25260 KB	Output is correct
7	Correct	154 ms	24332 KB	Output is correct
8	Correct	124 ms	25480 KB	Output is correct
9	Correct	159 ms	26100 KB	Output is correct
10	Correct	116 ms	24596 KB	Output is correct
11	Correct	159 ms	25080 KB	Output is correct
12	Correct	119 ms	25640 KB	Output is correct
13	Correct	152 ms	24904 KB	Output is correct
14	Correct	158 ms	25028 KB	Output is correct
15	Correct	125 ms	26368 KB	Output is correct
16	Correct	159 ms	25764 KB	Output is correct
17	Correct	152 ms	26100 KB	Output is correct
18	Correct	140 ms	25844 KB	Output is correct
19	Correct	107 ms	25048 KB	Output is correct
20	Correct	144 ms	26304 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	1116 KB	Output is correct
3	Correct	5 ms	1688 KB	Output is correct
4	Correct	6 ms	1688 KB	Output is correct
5	Correct	5 ms	1432 KB	Output is correct
6	Correct	5 ms	1688 KB	Output is correct
7	Correct	5 ms	1708 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	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	4 ms	1112 KB	Output is correct
15	Correct	4 ms	1116 KB	Output is correct
16	Correct	4 ms	1116 KB	Output is correct
17	Correct	5 ms	1176 KB	Output is correct
18	Correct	5 ms	1176 KB	Output is correct
19	Correct	3 ms	1116 KB	Output is correct
20	Correct	4 ms	1116 KB	Output is correct
21	Correct	4 ms	1116 KB	Output is correct
22	Correct	3 ms	1116 KB	Output is correct
23	Correct	3 ms	1116 KB	Output is correct
24	Correct	4 ms	1116 KB	Output is correct
25	Correct	4 ms	1116 KB	Output is correct

Subtask #4
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	3 ms	1116 KB	Output is correct
3	Correct	5 ms	1688 KB	Output is correct
4	Correct	6 ms	1688 KB	Output is correct
5	Correct	5 ms	1432 KB	Output is correct
6	Correct	5 ms	1688 KB	Output is correct
7	Correct	5 ms	1708 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	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	1 ms	348 KB	Output is correct
14	Correct	4 ms	1112 KB	Output is correct
15	Correct	4 ms	1116 KB	Output is correct
16	Correct	4 ms	1116 KB	Output is correct
17	Correct	5 ms	1176 KB	Output is correct
18	Correct	5 ms	1176 KB	Output is correct
19	Correct	3 ms	1116 KB	Output is correct
20	Correct	4 ms	1116 KB	Output is correct
21	Correct	4 ms	1116 KB	Output is correct
22	Correct	3 ms	1116 KB	Output is correct
23	Correct	3 ms	1116 KB	Output is correct
24	Correct	4 ms	1116 KB	Output is correct
25	Correct	4 ms	1116 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	111 ms	22100 KB	Output is correct
28	Correct	139 ms	22016 KB	Output is correct
29	Correct	139 ms	21108 KB	Output is correct
30	Correct	141 ms	22012 KB	Output is correct
31	Correct	161 ms	22536 KB	Output is correct
32	Correct	142 ms	21236 KB	Output is correct
33	Correct	1 ms	348 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	0 ms	348 KB	Output is correct
36	Correct	0 ms	348 KB	Output is correct
37	Incorrect	0 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	-

답안 #1002238

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