Submission #952420

#	Time	Username	Problem	Language	Result	Execution time	Memory
952420		Mohamed_Kachef06	Fuel Station (NOI20_fuelstation)	C++17	13 / 100	476 ms	52144 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;
    vector<array<int , 3>> u;
    st.init(N+1); 
    for (int i = 0 ; i < N ; i++){
        int x , a , b;
        cin >> x >> a >> b;
        v.push_back({x , a , b});
       
    }
    v.push_back({D , 0 , 0});
    sort(v.begin() , v.end()); 
    for (int i = 0 ; i <= N ; i++) {
         u.push_back({v[i][2] , v[i][1] , i+1});
        st.update(i+1 , i+1 , -v[i][0]); 
    }
     u.push_back({(int)1e10 , 0 , N});
         sort(u.begin() , u.end()); 

    int ans = 1e18;
    int id = 0 ;
   // for (int j = 1 ; j <= N+1 ; j++) cout << st.get(j , j) << ' ';
    cout << '\n';
    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++;
        }
      //  for (int j = 1 ; j <= N+1 ; j++) cout << st.get(j , j) << ' ';
        //cout << '\n';
        int x = st.get(1 , N+1); 
        if (-x <= u[i][0]) ans = min(ans , -x); 
    }     
    cout << ans;  
}


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

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