oj.uz

Submission #1105815

# Submission time Handle Problem Language Result Execution time Memory
1105815 2024-10-28T02:20:17 Z whoknow Fuel Station (NOI20_fuelstation) C++17
13 / 100
 237 ms 37636 KB 
#include <bits/stdc++.h>
#define ll 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;
    }
    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:120:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  120 | main()
      | ^~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 183 ms 36168 KB Output is correct
2 Correct 197 ms 35828 KB Output is correct
3 Correct 192 ms 35912 KB Output is correct
4 Correct 194 ms 36168 KB Output is correct
5 Correct 188 ms 36680 KB Output is correct
6 Correct 183 ms 35768 KB Output is correct
7 Correct 194 ms 35808 KB Output is correct
8 Correct 191 ms 36400 KB Output is correct
9 Correct 181 ms 37636 KB Output is correct
10 Correct 173 ms 35664 KB Output is correct
11 Correct 179 ms 35400 KB Output is correct
12 Correct 178 ms 34052 KB Output is correct
13 Correct 177 ms 36424 KB Output is correct
14 Correct 203 ms 36408 KB Output is correct
15 Correct 184 ms 36936 KB Output is correct
16 Correct 237 ms 34660 KB Output is correct
17 Correct 197 ms 37568 KB Output is correct
18 Correct 189 ms 35716 KB Output is correct
19 Correct 175 ms 32836 KB Output is correct
20 Correct 192 ms 32724 KB Output is correct

Subtask #3
0 / 17.0

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