Submission #952694

#	Time	Username	Problem	Language	Result	Execution time	Memory
952694		Mohamed_Kachef06	Fuel Station (NOI20_fuelstation)	C++17	100 / 100	501 ms	48340 KiB

FuelStation

#include <bits/stdc++.h>
using namespace std;
#define int long long 

#define lc 2*p
#define rc 2*p+1
struct SegmentTree{
    vector<int> seg , lazy;
    int m;
    void init(int n){
        m = 1<<(__lg(n-1)+1);
        seg.resize(2*m); lazy.resize(2*m);
    }
    void propagate(int s,  int e , int p){
        if (s == e) return ;
        lazy[2*p]+=lazy[p];
        lazy[2*p+1] += lazy[p];
        seg[2*p] += lazy[p];
        seg[rc] += lazy[p]; 
        lazy[p] = 0;
    }
    void update(int l , int r , int val , int s , int e , int p){
        propagate(s , e , p);
        if (l > e || r < s) return ;
        else if (l <= s && r >= e){
            seg[p]+=val;
            lazy[p] += val; 
            return; 
        }
        update(l , r , val , s , (s+e)/2, 2*p); update(l, r , val , (s+e)/2+1 , e , 2*p+1);
        seg[p] = min(seg[lc] , seg[rc]);
    }
    int get(int l , int r , int s , int e , int p){
        propagate(s , e , p);
        if (l > e || r < s) return 1e18;
        else if (l <= s && r >= e) return seg[p]; 
        return min(get(l , r , s , (s+e)/2 , lc) , get(l , r , (s+e)/2 + 1 , e , 2*p+1));  
    }
    void update(int l , int r , int val){
        update(l , r , val ,1 , m ,1);
    }
    int get(int l , int r){
        return get(l , r ,1 , m , 1);
    }
};



SegmentTree st;

void doWork(){
    int n , d;
    cin >> n >> d;
    vector<array<int , 3>> v(n+1); 
    vector<array<int , 3>> u(n); 
    int arr[n+1] = {};
    // arr[i] = cost to go from i to i+1
    st.init(n+10); 
    for (int i=  1 ; i <= n ; i++){
        for (int j = 0 ; j < 3 ; j++){
            cin >> v[i][j]; 
        }
    }
    v.push_back({d , 0 , 0});
    sort(v.begin() , v.end());

    for (int i = 1 ; i <= n ; i++){
        u[i-1] = {v[i][2] , v[i][1] , i}; 
    }
    u.push_back({(int)1e18 , 0 , 0});
    sort(u.begin() , u.end() , greater<>());

    for (int i = 1 ; i <= n+1 ; i++){
        st.update(i , i , -v[i][0]); 
    }
    //cout << st.get(1 , n+2)  << ' ' ;
    int ans = 1e18;
    int id = 0;
    for (int i = 0 ; i <= n ; i++){
        while (id <= n && u[id][0] >= u[i][0]) {  st.update(u[id][2] + 1  , n+1 , u[id][1]); id++;}
        int mx = -st.get(1 , n+1); 
        // cout << mx << ' ' << u[i][0] << '\n';
        // cout << '\n';
        //cout << mx << ' ' ;
        if (mx <= u[i][0]) ans = min(ans , mx);
    }
    cout << ans; 
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    doWork(); 
}

Compilation message (stderr)

FuelStation.cpp: In function 'void doWork()':
FuelStation.cpp:56:9: warning: unused variable 'arr' [-Wunused-variable]
   56 |     int arr[n+1] = {};
      |         ^~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 12 / 12
• Subtask 5: 19 / 19
• Subtask 6: 11 / 11
• Subtask 7: 21 / 21