oj.uz

Submission #737475

# Submission time Handle Problem Language Result Execution time Memory
737475 2023-05-07T08:24:26 Z Ronin13 Fuel Station (NOI20_fuelstation) C++14
100 / 100
 1123 ms 740048 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());
    reverse(B.begin(), B.end());
    upd(1, 1, n + 1, n + 1, d);
    for(int i = 1; i<= n; i++)
        upd(1, 1, n + 1, pos[i], x[i]);
    ll ans = d;

    for(int i = 0; i < B.size(); i++){
        int p = B[i].s;
        upd_ran(1, 1, n + 1, pos[p] + 1, n + 1, -a[p]);
        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:106: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]
  106 |     for(int i = 0; i < B.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 704700 KB Output is correct
2 Correct 251 ms 704824 KB Output is correct
3 Correct 257 ms 704768 KB Output is correct
4 Correct 246 ms 704788 KB Output is correct
5 Correct 259 ms 704736 KB Output is correct
6 Correct 262 ms 704860 KB Output is correct
7 Correct 243 ms 704756 KB Output is correct
8 Correct 273 ms 704768 KB Output is correct
9 Correct 255 ms 704732 KB Output is correct
10 Correct 261 ms 704748 KB Output is correct
11 Correct 245 ms 704716 KB Output is correct
12 Correct 262 ms 704748 KB Output is correct
13 Correct 253 ms 704776 KB Output is correct
14 Correct 252 ms 704752 KB Output is correct
15 Correct 247 ms 704700 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 731372 KB Output is correct
2 Correct 899 ms 731188 KB Output is correct
3 Correct 902 ms 731216 KB Output is correct
4 Correct 933 ms 731172 KB Output is correct
5 Correct 872 ms 731104 KB Output is correct
6 Correct 935 ms 731180 KB Output is correct
7 Correct 922 ms 731164 KB Output is correct
8 Correct 885 ms 731176 KB Output is correct
9 Correct 927 ms 731168 KB Output is correct
10 Correct 1004 ms 731152 KB Output is correct
11 Correct 872 ms 731172 KB Output is correct
12 Correct 819 ms 731180 KB Output is correct
13 Correct 1102 ms 731176 KB Output is correct
14 Correct 919 ms 731180 KB Output is correct
15 Correct 1039 ms 731180 KB Output is correct
16 Correct 1033 ms 731688 KB Output is correct
17 Correct 969 ms 732680 KB Output is correct
18 Correct 956 ms 732648 KB Output is correct
19 Correct 935 ms 732724 KB Output is correct
20 Correct 1057 ms 732716 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 704784 KB Output is correct
2 Correct 299 ms 705752 KB Output is correct
3 Correct 290 ms 705700 KB Output is correct
4 Correct 308 ms 705728 KB Output is correct
5 Correct 284 ms 705680 KB Output is correct
6 Correct 318 ms 705724 KB Output is correct
7 Correct 359 ms 705784 KB Output is correct
8 Correct 318 ms 704808 KB Output is correct
9 Correct 303 ms 704744 KB Output is correct
10 Correct 270 ms 704832 KB Output is correct
11 Correct 333 ms 704768 KB Output is correct
12 Correct 275 ms 704872 KB Output is correct
13 Correct 321 ms 704784 KB Output is correct
14 Correct 296 ms 705780 KB Output is correct
15 Correct 330 ms 705780 KB Output is correct
16 Correct 324 ms 705792 KB Output is correct
17 Correct 340 ms 705720 KB Output is correct
18 Correct 311 ms 705756 KB Output is correct
19 Correct 282 ms 705720 KB Output is correct
20 Correct 298 ms 705780 KB Output is correct
21 Correct 301 ms 705832 KB Output is correct
22 Correct 319 ms 705688 KB Output is correct
23 Correct 305 ms 705724 KB Output is correct
24 Correct 293 ms 705748 KB Output is correct
25 Correct 311 ms 705756 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 704784 KB Output is correct
2 Correct 299 ms 705752 KB Output is correct
3 Correct 290 ms 705700 KB Output is correct
4 Correct 308 ms 705728 KB Output is correct
5 Correct 284 ms 705680 KB Output is correct
6 Correct 318 ms 705724 KB Output is correct
7 Correct 359 ms 705784 KB Output is correct
8 Correct 318 ms 704808 KB Output is correct
9 Correct 303 ms 704744 KB Output is correct
10 Correct 270 ms 704832 KB Output is correct
11 Correct 333 ms 704768 KB Output is correct
12 Correct 275 ms 704872 KB Output is correct
13 Correct 321 ms 704784 KB Output is correct
14 Correct 296 ms 705780 KB Output is correct
15 Correct 330 ms 705780 KB Output is correct
16 Correct 324 ms 705792 KB Output is correct
17 Correct 340 ms 705720 KB Output is correct
18 Correct 311 ms 705756 KB Output is correct
19 Correct 282 ms 705720 KB Output is correct
20 Correct 298 ms 705780 KB Output is correct
21 Correct 301 ms 705832 KB Output is correct
22 Correct 319 ms 705688 KB Output is correct
23 Correct 305 ms 705724 KB Output is correct
24 Correct 293 ms 705748 KB Output is correct
25 Correct 311 ms 705756 KB Output is correct
26 Correct 328 ms 704724 KB Output is correct
27 Correct 815 ms 735496 KB Output is correct
28 Correct 862 ms 735260 KB Output is correct
29 Correct 952 ms 734880 KB Output is correct
30 Correct 964 ms 734884 KB Output is correct
31 Correct 1048 ms 735584 KB Output is correct
32 Correct 793 ms 735264 KB Output is correct
33 Correct 288 ms 704744 KB Output is correct
34 Correct 277 ms 704760 KB Output is correct
35 Correct 266 ms 704716 KB Output is correct
36 Correct 290 ms 704784 KB Output is correct
37 Correct 325 ms 704716 KB Output is correct
38 Correct 281 ms 704960 KB Output is correct
39 Correct 834 ms 735624 KB Output is correct
40 Correct 808 ms 735544 KB Output is correct
41 Correct 803 ms 735524 KB Output is correct
42 Correct 795 ms 735520 KB Output is correct
43 Correct 858 ms 735528 KB Output is correct
44 Correct 782 ms 734960 KB Output is correct
45 Correct 835 ms 734548 KB Output is correct
46 Correct 790 ms 735548 KB Output is correct
47 Correct 819 ms 736956 KB Output is correct
48 Correct 854 ms 737064 KB Output is correct
49 Correct 802 ms 734800 KB Output is correct
50 Correct 769 ms 735260 KB Output is correct
51 Correct 759 ms 735256 KB Output is correct
52 Correct 782 ms 734948 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 704700 KB Output is correct
2 Correct 251 ms 704824 KB Output is correct
3 Correct 257 ms 704768 KB Output is correct
4 Correct 246 ms 704788 KB Output is correct
5 Correct 259 ms 704736 KB Output is correct
6 Correct 262 ms 704860 KB Output is correct
7 Correct 243 ms 704756 KB Output is correct
8 Correct 273 ms 704768 KB Output is correct
9 Correct 255 ms 704732 KB Output is correct
10 Correct 261 ms 704748 KB Output is correct
11 Correct 245 ms 704716 KB Output is correct
12 Correct 262 ms 704748 KB Output is correct
13 Correct 253 ms 704776 KB Output is correct
14 Correct 252 ms 704752 KB Output is correct
15 Correct 247 ms 704700 KB Output is correct
16 Correct 254 ms 704760 KB Output is correct
17 Correct 288 ms 704696 KB Output is correct
18 Correct 280 ms 704716 KB Output is correct
19 Correct 276 ms 704796 KB Output is correct
20 Correct 267 ms 704688 KB Output is correct
21 Correct 270 ms 704852 KB Output is correct
22 Correct 286 ms 704736 KB Output is correct
23 Correct 257 ms 704788 KB Output is correct
24 Correct 270 ms 704716 KB Output is correct
25 Correct 262 ms 704716 KB Output is correct
26 Correct 272 ms 704772 KB Output is correct
27 Correct 259 ms 704744 KB Output is correct
28 Correct 265 ms 704804 KB Output is correct
29 Correct 257 ms 704708 KB Output is correct
30 Correct 266 ms 704792 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 704700 KB Output is correct
2 Correct 251 ms 704824 KB Output is correct
3 Correct 257 ms 704768 KB Output is correct
4 Correct 246 ms 704788 KB Output is correct
5 Correct 259 ms 704736 KB Output is correct
6 Correct 262 ms 704860 KB Output is correct
7 Correct 243 ms 704756 KB Output is correct
8 Correct 273 ms 704768 KB Output is correct
9 Correct 255 ms 704732 KB Output is correct
10 Correct 261 ms 704748 KB Output is correct
11 Correct 245 ms 704716 KB Output is correct
12 Correct 262 ms 704748 KB Output is correct
13 Correct 253 ms 704776 KB Output is correct
14 Correct 252 ms 704752 KB Output is correct
15 Correct 247 ms 704700 KB Output is correct
16 Correct 254 ms 704784 KB Output is correct
17 Correct 299 ms 705752 KB Output is correct
18 Correct 290 ms 705700 KB Output is correct
19 Correct 308 ms 705728 KB Output is correct
20 Correct 284 ms 705680 KB Output is correct
21 Correct 318 ms 705724 KB Output is correct
22 Correct 359 ms 705784 KB Output is correct
23 Correct 318 ms 704808 KB Output is correct
24 Correct 303 ms 704744 KB Output is correct
25 Correct 270 ms 704832 KB Output is correct
26 Correct 333 ms 704768 KB Output is correct
27 Correct 275 ms 704872 KB Output is correct
28 Correct 321 ms 704784 KB Output is correct
29 Correct 296 ms 705780 KB Output is correct
30 Correct 330 ms 705780 KB Output is correct
31 Correct 324 ms 705792 KB Output is correct
32 Correct 340 ms 705720 KB Output is correct
33 Correct 311 ms 705756 KB Output is correct
34 Correct 282 ms 705720 KB Output is correct
35 Correct 298 ms 705780 KB Output is correct
36 Correct 301 ms 705832 KB Output is correct
37 Correct 319 ms 705688 KB Output is correct
38 Correct 305 ms 705724 KB Output is correct
39 Correct 293 ms 705748 KB Output is correct
40 Correct 311 ms 705756 KB Output is correct
41 Correct 271 ms 704716 KB Output is correct
42 Correct 281 ms 705912 KB Output is correct
43 Correct 341 ms 705832 KB Output is correct
44 Correct 295 ms 705860 KB Output is correct
45 Correct 357 ms 705916 KB Output is correct
46 Correct 290 ms 705840 KB Output is correct
47 Correct 327 ms 705892 KB Output is correct
48 Correct 292 ms 704752 KB Output is correct
49 Correct 303 ms 704712 KB Output is correct
50 Correct 295 ms 704808 KB Output is correct
51 Correct 291 ms 704800 KB Output is correct
52 Correct 300 ms 704716 KB Output is correct
53 Correct 294 ms 704796 KB Output is correct
54 Correct 332 ms 705912 KB Output is correct
55 Correct 312 ms 705824 KB Output is correct
56 Correct 301 ms 705932 KB Output is correct
57 Correct 318 ms 705856 KB Output is correct
58 Correct 345 ms 705940 KB Output is correct
59 Correct 296 ms 705912 KB Output is correct
60 Correct 330 ms 706060 KB Output is correct
61 Correct 293 ms 705836 KB Output is correct
62 Correct 308 ms 705840 KB Output is correct
63 Correct 479 ms 705816 KB Output is correct
64 Correct 320 ms 705864 KB Output is correct
65 Correct 322 ms 705864 KB Output is correct

Subtask #7
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 704700 KB Output is correct
2 Correct 251 ms 704824 KB Output is correct
3 Correct 257 ms 704768 KB Output is correct
4 Correct 246 ms 704788 KB Output is correct
5 Correct 259 ms 704736 KB Output is correct
6 Correct 262 ms 704860 KB Output is correct
7 Correct 243 ms 704756 KB Output is correct
8 Correct 273 ms 704768 KB Output is correct
9 Correct 255 ms 704732 KB Output is correct
10 Correct 261 ms 704748 KB Output is correct
11 Correct 245 ms 704716 KB Output is correct
12 Correct 262 ms 704748 KB Output is correct
13 Correct 253 ms 704776 KB Output is correct
14 Correct 252 ms 704752 KB Output is correct
15 Correct 247 ms 704700 KB Output is correct
16 Correct 864 ms 731372 KB Output is correct
17 Correct 899 ms 731188 KB Output is correct
18 Correct 902 ms 731216 KB Output is correct
19 Correct 933 ms 731172 KB Output is correct
20 Correct 872 ms 731104 KB Output is correct
21 Correct 935 ms 731180 KB Output is correct
22 Correct 922 ms 731164 KB Output is correct
23 Correct 885 ms 731176 KB Output is correct
24 Correct 927 ms 731168 KB Output is correct
25 Correct 1004 ms 731152 KB Output is correct
26 Correct 872 ms 731172 KB Output is correct
27 Correct 819 ms 731180 KB Output is correct
28 Correct 1102 ms 731176 KB Output is correct
29 Correct 919 ms 731180 KB Output is correct
30 Correct 1039 ms 731180 KB Output is correct
31 Correct 1033 ms 731688 KB Output is correct
32 Correct 969 ms 732680 KB Output is correct
33 Correct 956 ms 732648 KB Output is correct
34 Correct 935 ms 732724 KB Output is correct
35 Correct 1057 ms 732716 KB Output is correct
36 Correct 254 ms 704784 KB Output is correct
37 Correct 299 ms 705752 KB Output is correct
38 Correct 290 ms 705700 KB Output is correct
39 Correct 308 ms 705728 KB Output is correct
40 Correct 284 ms 705680 KB Output is correct
41 Correct 318 ms 705724 KB Output is correct
42 Correct 359 ms 705784 KB Output is correct
43 Correct 318 ms 704808 KB Output is correct
44 Correct 303 ms 704744 KB Output is correct
45 Correct 270 ms 704832 KB Output is correct
46 Correct 333 ms 704768 KB Output is correct
47 Correct 275 ms 704872 KB Output is correct
48 Correct 321 ms 704784 KB Output is correct
49 Correct 296 ms 705780 KB Output is correct
50 Correct 330 ms 705780 KB Output is correct
51 Correct 324 ms 705792 KB Output is correct
52 Correct 340 ms 705720 KB Output is correct
53 Correct 311 ms 705756 KB Output is correct
54 Correct 282 ms 705720 KB Output is correct
55 Correct 298 ms 705780 KB Output is correct
56 Correct 301 ms 705832 KB Output is correct
57 Correct 319 ms 705688 KB Output is correct
58 Correct 305 ms 705724 KB Output is correct
59 Correct 293 ms 705748 KB Output is correct
60 Correct 311 ms 705756 KB Output is correct
61 Correct 328 ms 704724 KB Output is correct
62 Correct 815 ms 735496 KB Output is correct
63 Correct 862 ms 735260 KB Output is correct
64 Correct 952 ms 734880 KB Output is correct
65 Correct 964 ms 734884 KB Output is correct
66 Correct 1048 ms 735584 KB Output is correct
67 Correct 793 ms 735264 KB Output is correct
68 Correct 288 ms 704744 KB Output is correct
69 Correct 277 ms 704760 KB Output is correct
70 Correct 266 ms 704716 KB Output is correct
71 Correct 290 ms 704784 KB Output is correct
72 Correct 325 ms 704716 KB Output is correct
73 Correct 281 ms 704960 KB Output is correct
74 Correct 834 ms 735624 KB Output is correct
75 Correct 808 ms 735544 KB Output is correct
76 Correct 803 ms 735524 KB Output is correct
77 Correct 795 ms 735520 KB Output is correct
78 Correct 858 ms 735528 KB Output is correct
79 Correct 782 ms 734960 KB Output is correct
80 Correct 835 ms 734548 KB Output is correct
81 Correct 790 ms 735548 KB Output is correct
82 Correct 819 ms 736956 KB Output is correct
83 Correct 854 ms 737064 KB Output is correct
84 Correct 802 ms 734800 KB Output is correct
85 Correct 769 ms 735260 KB Output is correct
86 Correct 759 ms 735256 KB Output is correct
87 Correct 782 ms 734948 KB Output is correct
88 Correct 254 ms 704760 KB Output is correct
89 Correct 288 ms 704696 KB Output is correct
90 Correct 280 ms 704716 KB Output is correct
91 Correct 276 ms 704796 KB Output is correct
92 Correct 267 ms 704688 KB Output is correct
93 Correct 270 ms 704852 KB Output is correct
94 Correct 286 ms 704736 KB Output is correct
95 Correct 257 ms 704788 KB Output is correct
96 Correct 270 ms 704716 KB Output is correct
97 Correct 262 ms 704716 KB Output is correct
98 Correct 272 ms 704772 KB Output is correct
99 Correct 259 ms 704744 KB Output is correct
100 Correct 265 ms 704804 KB Output is correct
101 Correct 257 ms 704708 KB Output is correct
102 Correct 266 ms 704792 KB Output is correct
103 Correct 271 ms 704716 KB Output is correct
104 Correct 281 ms 705912 KB Output is correct
105 Correct 341 ms 705832 KB Output is correct
106 Correct 295 ms 705860 KB Output is correct
107 Correct 357 ms 705916 KB Output is correct
108 Correct 290 ms 705840 KB Output is correct
109 Correct 327 ms 705892 KB Output is correct
110 Correct 292 ms 704752 KB Output is correct
111 Correct 303 ms 704712 KB Output is correct
112 Correct 295 ms 704808 KB Output is correct
113 Correct 291 ms 704800 KB Output is correct
114 Correct 300 ms 704716 KB Output is correct
115 Correct 294 ms 704796 KB Output is correct
116 Correct 332 ms 705912 KB Output is correct
117 Correct 312 ms 705824 KB Output is correct
118 Correct 301 ms 705932 KB Output is correct
119 Correct 318 ms 705856 KB Output is correct
120 Correct 345 ms 705940 KB Output is correct
121 Correct 296 ms 705912 KB Output is correct
122 Correct 330 ms 706060 KB Output is correct
123 Correct 293 ms 705836 KB Output is correct
124 Correct 308 ms 705840 KB Output is correct
125 Correct 479 ms 705816 KB Output is correct
126 Correct 320 ms 705864 KB Output is correct
127 Correct 322 ms 705864 KB Output is correct
128 Correct 297 ms 704724 KB Output is correct
129 Correct 1016 ms 738604 KB Output is correct
130 Correct 967 ms 739280 KB Output is correct
131 Correct 1095 ms 739932 KB Output is correct
132 Correct 1075 ms 739244 KB Output is correct
133 Correct 1042 ms 739228 KB Output is correct
134 Correct 1016 ms 739828 KB Output is correct
135 Correct 303 ms 704716 KB Output is correct
136 Correct 265 ms 704748 KB Output is correct
137 Correct 307 ms 704748 KB Output is correct
138 Correct 298 ms 704736 KB Output is correct
139 Correct 256 ms 704804 KB Output is correct
140 Correct 255 ms 704716 KB Output is correct
141 Correct 1106 ms 739992 KB Output is correct
142 Correct 879 ms 739624 KB Output is correct
143 Correct 1063 ms 739920 KB Output is correct
144 Correct 1000 ms 739896 KB Output is correct
145 Correct 943 ms 740048 KB Output is correct
146 Correct 879 ms 738204 KB Output is correct
147 Correct 869 ms 739112 KB Output is correct
148 Correct 828 ms 738416 KB Output is correct
149 Correct 988 ms 739260 KB Output is correct
150 Correct 857 ms 739580 KB Output is correct
151 Correct 855 ms 739568 KB Output is correct
152 Correct 941 ms 739240 KB Output is correct
153 Correct 920 ms 739236 KB Output is correct
154 Correct 1123 ms 739248 KB Output is correct
155 Correct 1020 ms 739240 KB Output is correct