oj.uz

Submission #737454

# Submission time Handle Problem Language Result Execution time Memory
737454 2023-05-07T08:15:36 Z Ronin13 Fuel Station (NOI20_fuelstation) C++14
20 / 100
 911 ms 732740 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 10000001;
vector <ll> bit(nmax);

const ll mod = 1e9 + 7;

int lsb(int x){
    return x & -x;
}

void add(int pos, ll v, int n){
    while(pos <= n){
        bit[pos] += v;
        pos += lsb(pos);
    }
}

ll get(int pos){
    ll res = 0;
    while(pos){
        res += bit[pos];
        pos -= lsb(pos);
    }
    return res;
}

vector <ll> t(4 * nmax), lazy(4 * nmax);

void push(int v){
    t[2 * v] += lazy[v];
    lazy[2 * v] += lazy[v];
    t[2 * v + 1] += lazy[v];
    lazy[2 * v + 1] += lazy[v];
    lazy[v] = 0;
}



void upd(int v, int l, int r, int pos, ll val){
    if(l > pos || r < pos)
        return;
    if(l == r){
        t[v] = val;
        return;
    }
    int m = (l + r) / 2;
    push(v);
    upd(2 * v, l, m, pos, val);
    upd(2 * v + 1, m + 1,r, pos, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}

void upd_ran(int v, int l, int r, int st, int fin, ll val){
    if(l > fin || r < st)
        return;
    if(l >= st && r <= fin){
        t[v] += val;
        lazy[v] += val;
        return;
    }
    int m = (l + r) / 2;
    push(v);
    upd_ran(2 * v, l, m, st, fin, val);
    upd_ran(2 * v + 1, m + 1, r, st, fin, val);
    t[v] = max(t[2 * v], t[2 * v + 1]);
}


int main(){
    int n; cin >> n;
    int d; cin >> d;
    ll a[n + 1], b[n + 1];
    ll x[n + 1];
    ll pos[n + 2];
    for(int i = 1; i <= n; i++)
        cin >> x[i] >> a[i] >> b[i];
    map  <int,int> mp;
    vector <pll> cmp;
    for(int i= 1; i <= n; i++){
        cmp.pb({x[i], i});
    }
    cmp.pb({d, 0});
    sort(cmp.begin(), cmp.end());
    for(int i= 0; i < cmp.size(); i++)
        pos[cmp[i].s] = i + 1;
    vector <pll> B;
    for(int i = 1; i <=n; i++){
        B.pb({b[i], i});
    }
    sort(B.begin(), B.end());
    upd(1, 1, n + 1, n + 1, d);
    for(int i = 1; i<= n; i++)
        upd(1, 1, n + 1, i, x[i]);
    ll ans = d;

    for(int i = 0; i < B.size(); i++){
        int p = B[i].s;
        ll xx = get(pos[p] - 1);
        upd(1, 1, n + 1, pos[p], x[p] - xx);
        upd_ran(1, 1, n + 1, pos[p] + 1, n + 1, -a[p]);
        add(pos[p], a[p], n + 1);
        if(B[i].f >= t[1]){
            ans = min(t[1], ans);
            continue;
        }
    }
    cout << max(ans, 0LL);
    return 0;
}

Compilation message

FuelStation.cpp: In function 'int main()':
FuelStation.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i= 0; i < cmp.size(); i++)
      |                   ~~^~~~~~~~~~~~
FuelStation.cpp:105:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 0; i < B.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 704688 KB Output is correct
2 Correct 276 ms 704788 KB Output is correct
3 Correct 252 ms 704796 KB Output is correct
4 Correct 246 ms 704792 KB Output is correct
5 Correct 260 ms 704716 KB Output is correct
6 Correct 248 ms 704760 KB Output is correct
7 Correct 250 ms 704788 KB Output is correct
8 Correct 246 ms 704772 KB Output is correct
9 Correct 246 ms 704816 KB Output is correct
10 Correct 248 ms 704752 KB Output is correct
11 Correct 256 ms 704812 KB Output is correct
12 Correct 248 ms 704760 KB Output is correct
13 Correct 249 ms 705020 KB Output is correct
14 Correct 254 ms 704796 KB Output is correct
15 Correct 244 ms 704692 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 898 ms 732740 KB Output is correct
2 Correct 884 ms 732716 KB Output is correct
3 Correct 888 ms 732620 KB Output is correct
4 Correct 862 ms 732136 KB Output is correct
5 Correct 858 ms 732216 KB Output is correct
6 Correct 887 ms 732328 KB Output is correct
7 Correct 881 ms 732228 KB Output is correct
8 Correct 879 ms 732056 KB Output is correct
9 Correct 903 ms 731896 KB Output is correct
10 Correct 845 ms 731936 KB Output is correct
11 Correct 911 ms 731952 KB Output is correct
12 Correct 889 ms 731920 KB Output is correct
13 Correct 906 ms 731872 KB Output is correct
14 Correct 906 ms 731732 KB Output is correct
15 Correct 852 ms 731696 KB Output is correct
16 Correct 903 ms 731728 KB Output is correct
17 Correct 860 ms 731704 KB Output is correct
18 Correct 885 ms 731704 KB Output is correct
19 Correct 850 ms 731808 KB Output is correct
20 Correct 888 ms 731768 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 704716 KB Output is correct
2 Correct 266 ms 705716 KB Output is correct
3 Correct 299 ms 705780 KB Output is correct
4 Correct 259 ms 705736 KB Output is correct
5 Correct 273 ms 705696 KB Output is correct
6 Correct 268 ms 705736 KB Output is correct
7 Correct 269 ms 705848 KB Output is correct
8 Incorrect 246 ms 704776 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 704716 KB Output is correct
2 Correct 266 ms 705716 KB Output is correct
3 Correct 299 ms 705780 KB Output is correct
4 Correct 259 ms 705736 KB Output is correct
5 Correct 273 ms 705696 KB Output is correct
6 Correct 268 ms 705736 KB Output is correct
7 Correct 269 ms 705848 KB Output is correct
8 Incorrect 246 ms 704776 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 704688 KB Output is correct
2 Correct 276 ms 704788 KB Output is correct
3 Correct 252 ms 704796 KB Output is correct
4 Correct 246 ms 704792 KB Output is correct
5 Correct 260 ms 704716 KB Output is correct
6 Correct 248 ms 704760 KB Output is correct
7 Correct 250 ms 704788 KB Output is correct
8 Correct 246 ms 704772 KB Output is correct
9 Correct 246 ms 704816 KB Output is correct
10 Correct 248 ms 704752 KB Output is correct
11 Correct 256 ms 704812 KB Output is correct
12 Correct 248 ms 704760 KB Output is correct
13 Correct 249 ms 705020 KB Output is correct
14 Correct 254 ms 704796 KB Output is correct
15 Correct 244 ms 704692 KB Output is correct
16 Correct 259 ms 704732 KB Output is correct
17 Correct 251 ms 704740 KB Output is correct
18 Correct 246 ms 704736 KB Output is correct
19 Correct 246 ms 704736 KB Output is correct
20 Correct 256 ms 704772 KB Output is correct
21 Correct 246 ms 704804 KB Output is correct
22 Incorrect 247 ms 704740 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 704688 KB Output is correct
2 Correct 276 ms 704788 KB Output is correct
3 Correct 252 ms 704796 KB Output is correct
4 Correct 246 ms 704792 KB Output is correct
5 Correct 260 ms 704716 KB Output is correct
6 Correct 248 ms 704760 KB Output is correct
7 Correct 250 ms 704788 KB Output is correct
8 Correct 246 ms 704772 KB Output is correct
9 Correct 246 ms 704816 KB Output is correct
10 Correct 248 ms 704752 KB Output is correct
11 Correct 256 ms 704812 KB Output is correct
12 Correct 248 ms 704760 KB Output is correct
13 Correct 249 ms 705020 KB Output is correct
14 Correct 254 ms 704796 KB Output is correct
15 Correct 244 ms 704692 KB Output is correct
16 Correct 250 ms 704716 KB Output is correct
17 Correct 266 ms 705716 KB Output is correct
18 Correct 299 ms 705780 KB Output is correct
19 Correct 259 ms 705736 KB Output is correct
20 Correct 273 ms 705696 KB Output is correct
21 Correct 268 ms 705736 KB Output is correct
22 Correct 269 ms 705848 KB Output is correct
23 Incorrect 246 ms 704776 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 704688 KB Output is correct
2 Correct 276 ms 704788 KB Output is correct
3 Correct 252 ms 704796 KB Output is correct
4 Correct 246 ms 704792 KB Output is correct
5 Correct 260 ms 704716 KB Output is correct
6 Correct 248 ms 704760 KB Output is correct
7 Correct 250 ms 704788 KB Output is correct
8 Correct 246 ms 704772 KB Output is correct
9 Correct 246 ms 704816 KB Output is correct
10 Correct 248 ms 704752 KB Output is correct
11 Correct 256 ms 704812 KB Output is correct
12 Correct 248 ms 704760 KB Output is correct
13 Correct 249 ms 705020 KB Output is correct
14 Correct 254 ms 704796 KB Output is correct
15 Correct 244 ms 704692 KB Output is correct
16 Correct 898 ms 732740 KB Output is correct
17 Correct 884 ms 732716 KB Output is correct
18 Correct 888 ms 732620 KB Output is correct
19 Correct 862 ms 732136 KB Output is correct
20 Correct 858 ms 732216 KB Output is correct
21 Correct 887 ms 732328 KB Output is correct
22 Correct 881 ms 732228 KB Output is correct
23 Correct 879 ms 732056 KB Output is correct
24 Correct 903 ms 731896 KB Output is correct
25 Correct 845 ms 731936 KB Output is correct
26 Correct 911 ms 731952 KB Output is correct
27 Correct 889 ms 731920 KB Output is correct
28 Correct 906 ms 731872 KB Output is correct
29 Correct 906 ms 731732 KB Output is correct
30 Correct 852 ms 731696 KB Output is correct
31 Correct 903 ms 731728 KB Output is correct
32 Correct 860 ms 731704 KB Output is correct
33 Correct 885 ms 731704 KB Output is correct
34 Correct 850 ms 731808 KB Output is correct
35 Correct 888 ms 731768 KB Output is correct
36 Correct 250 ms 704716 KB Output is correct
37 Correct 266 ms 705716 KB Output is correct
38 Correct 299 ms 705780 KB Output is correct
39 Correct 259 ms 705736 KB Output is correct
40 Correct 273 ms 705696 KB Output is correct
41 Correct 268 ms 705736 KB Output is correct
42 Correct 269 ms 705848 KB Output is correct
43 Incorrect 246 ms 704776 KB Output isn't correct
44 Halted 0 ms 0 KB -