oj.uz

Submission #1105817

# Submission time Handle Problem Language Result Execution time Memory
1105817 2024-10-28T02:24:15 Z whoknow Fuel Station (NOI20_fuelstation) C++17
13 / 100
 222 ms 44360 KB 
#include <bits/stdc++.h>
#define ll long long
#define int long long
#define F first
#define S second
#define MAXN 300005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
const ll INF = 1e18;
int n, D;
struct arr
{
    int x, A, B, id;
};
arr a[MAXN], b[MAXN];
namespace sub1
{
int res;
ll st[4 * MAXN], lazy[4 * MAXN];
void seg(int id, int l, int r)
{
    if(l == r)
        return st[id] = a[l].x, void();
    int mid = (l + r) / 2;
    seg(id * 2, l, mid);
    seg(id * 2 + 1, mid + 1, r);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}
void down(int id)
{
    ll t = lazy[id];
    st[id * 2] -= t;
    st[id * 2 + 1] -= t;
    lazy[id * 2] += t;
    lazy[id * 2 + 1] += t;
    lazy[id] = 0;
}
void update(int id, int l, int r, int u, int v, int k)
{
    if(l > v || r < u)
        return ;
    if(l >= u && r <= v)
    {
        st[id] -= k;
        lazy[id] += k;
        return ;
    }
    if(lazy[id])
        down(id);
    int mid = (l + r) / 2;
    update(id * 2, l, mid, u, v, k);
    update(id * 2 + 1, mid + 1, r, u, v, k);
    st[id] = max(st[id * 2], st[id * 2 + 1]);
}
ll get(int id, int l, int r, int u, int v)
{
    if(l > v || r < u)
        return -INF;
    if(l >= u && r <= v)
        return st[id];
    if(lazy[id])
        down(id);
    int mid = (l + r) / 2;
    return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
bool cmp1(arr x, arr y)
{
    return x.x < y.x;
}
bool cmp2(arr x, arr y)
{
    return x.B < y.B;
}
bool check(int x)
{
    ll t = x;
    for(int i = 1; i <= n; i++)
    {
        if(t < a[i].x)
            return 0;
        if(x <= a[i].B)
            t += a[i].A;
    }
    return 1;
}
int bina(int pos)
{
    int l = b[pos - 1].B + 1, r = b[pos].B;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    return r;
}
void solve()
{
    n++;
    a[n] = {D, 0, 0, n};
    sort(a + 1, a + 1 + n, cmp1);
    seg(1, 1, n);
    for(int i = 1; i <= n; i++)
        b[i] = a[i];
    sort(b + 1, b + 1 + n, cmp2);
    for(int i = n; i >= 1; i--)
    {
        update(1, 1, n, 1, n, -(b[i + 1].B - b[i].B));
        update(1, 1, n, b[i].id + 1, n, b[i].A);
        if(get(1, 1, n, 1, n) <= 0)
            res = i;
    }
    for(int i = b[res - 1].B; i <= b[res].B; i++)
        if(check(i))
            return cout << i, void();
//    cout << bina(res);
}
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> D;
    for(int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].A >> a[i].B, a[i].id = i;
    sub1::solve();
}

Compilation message

FuelStation.cpp:124:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  124 | main()
      | ^~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6480 KB Output is correct
2 Incorrect 1 ms 6480 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 207 ms 42052 KB Output is correct
2 Correct 211 ms 44100 KB Output is correct
3 Correct 209 ms 38772 KB Output is correct
4 Correct 207 ms 41960 KB Output is correct
5 Correct 201 ms 42232 KB Output is correct
6 Correct 222 ms 44360 KB Output is correct
7 Correct 219 ms 41800 KB Output is correct
8 Correct 208 ms 38404 KB Output is correct
9 Correct 217 ms 37852 KB Output is correct
10 Correct 194 ms 41716 KB Output is correct
11 Correct 202 ms 38560 KB Output is correct
12 Correct 192 ms 38024 KB Output is correct
13 Correct 208 ms 37828 KB Output is correct
14 Correct 202 ms 38164 KB Output is correct
15 Correct 200 ms 42164 KB Output is correct
16 Correct 211 ms 41288 KB Output is correct
17 Correct 203 ms 37960 KB Output is correct
18 Correct 212 ms 41872 KB Output is correct
19 Correct 206 ms 37840 KB Output is correct
20 Correct 186 ms 37848 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 19.0

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

Subtask #6
0 / 11.0

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

Subtask #7
0 / 21.0

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