Submission #1105819

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105819		whoknow	Fuel Station (NOI20_fuelstation)	C++17	100 / 100	262 ms	46664 KiB

FuelStation

#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 = -1;
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]!=0)
        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]!=0)
        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++)
    {
        a[i].id=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;
    }
    if(res == -1)
        return cout << D, void();
    cout << bina(res);
}
}
main()
{
    if(fopen("TEST.inp", "r"))
    {
        freopen("TEST.inp", "r", stdin);
        freopen("TEST.out", "w", stdout);
    }
    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;
    sub1::solve();
}

Compilation message (stderr)

FuelStation.cpp:126:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  126 | main()
      | ^~~~
FuelStation.cpp: In function 'int main()':
FuelStation.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |         freopen("TEST.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
FuelStation.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         freopen("TEST.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 12 / 12
• Subtask 5: 19 / 19
• Subtask 6: 11 / 11
• Subtask 7: 21 / 21