oj.uz

Submission #952420

# Submission time Handle Problem Language Result Execution time Memory
952420 2024-03-23T20:23:02 Z Mohamed_Kachef06 Fuel Station (NOI20_fuelstation) C++17
13 / 100
 476 ms 52144 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 51148 KB Output is correct
2 Correct 469 ms 51360 KB Output is correct
3 Correct 445 ms 51116 KB Output is correct
4 Correct 473 ms 50540 KB Output is correct
5 Correct 439 ms 52144 KB Output is correct
6 Correct 473 ms 50096 KB Output is correct
7 Correct 472 ms 50300 KB Output is correct
8 Correct 436 ms 51820 KB Output is correct
9 Correct 444 ms 51372 KB Output is correct
10 Correct 458 ms 50536 KB Output is correct
11 Correct 457 ms 50296 KB Output is correct
12 Correct 436 ms 50864 KB Output is correct
13 Correct 467 ms 51604 KB Output is correct
14 Correct 476 ms 51436 KB Output is correct
15 Correct 437 ms 52104 KB Output is correct
16 Correct 470 ms 51628 KB Output is correct
17 Correct 448 ms 51888 KB Output is correct
18 Correct 454 ms 51672 KB Output is correct
19 Correct 437 ms 51632 KB Output is correct
20 Correct 453 ms 51984 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 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 Incorrect 0 ms 348 KB Output isn't correct
3 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 Incorrect 0 ms 348 KB Output isn't correct
3 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 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -