oj.uz

Submission #998459

# Submission time Handle Problem Language Result Execution time Memory
998459 2024-06-14T02:28:27 Z cpptowin Fuel Station (NOI20_fuelstation) C++17
7 / 100
 244 ms 68680 KB 
#include <bits/stdc++.h>
#define fo(i, d, c) for (int i = d; i <= c; i++)
#define fod(i, c, d) for (int i = c; i >= d; i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout << "\n";
#define int long long
#define inf (int)1e18
#define pii pair<int, int>
#define vii vector<pii>
#define lb(x) x & -x
#define bit(i, j) ((i >> j) & 1)
#define offbit(i, j) (i ^ (1LL << j))
#define onbit(i, j) (i | (1LL << j))
#define vi vector<int>
#define all(x) x.begin(), x.end()
template <typename T1, typename T2>
bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2>
bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int nsqrt = 450;
const int mod = 1e9 + 7;
struct SegmentTree
{
    vector<int> st, lazy;
    int n;
    /// real n
    SegmentTree(int _n = 0) : n(_n)
    {
        st.resize(4 * n + 10);
        lazy.resize(4 * n + 10);
    }
    void resize(int _n)
    {
        n = _n;
        st.resize(4 * n + 10);
        lazy.resize(4 * n + 10);
    }

    void update(int id, int l, int r, int x, int val)
    {
        if (l > x or r < x)
            return;
        if (l == r)
        {
            st[id] += val;
            return;
        }
        int mid = l + r >> 1;
        update(id << 1, l, mid, x, val);
        update(id << 1 | 1, mid + 1, r, x, val);
        st[id] = st[id << 1] + st[id << 1 | 1];
    }

    int get(int id, int l, int r, int u, int v)
    {
        if (l > v || u > r)
            return 0;
        if (u <= l && r <= v)
            return st[id];
        int mid = (l + r) >> 1;
        return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
    }
    int get(int l, int r)
    {
        return get(1, 1, n, l, r);
    }
    void update(int x, int val)
    {
        update(1, 1, n, x, val);
    }
};
int n;
vii ke[maxn];
vi nen;
int x[maxn], a[maxn], b[maxn];
main()
{
#define name "TASK"
    if (fopen(name ".inp", "r"))
    {
        freopen(name ".inp", "r", stdin);
        freopen(name ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int d;
    cin >> n >> d;
    fo(i, 1, n)
    {
        cin >> x[i] >> a[i] >> b[i];
        nen.pb(b[i]);
    }
    SegmentTree st(n);
    sort(all(nen));
    nen.erase(unique(all(nen)),nen.end());
    fo(i,1,n)
    {
        b[i] = lower_bound(all(nen),b[i]) - nen.begin() + 1;
        ke[b[i]].pb(x[i],a[i]);
    }
    sort(all(nen),greater<int>());
    int ans = d;
    sort(x + 1,x + n + 1);
    fo(it,1,(int)nen.size())
    {
        for(auto [i,u] : ke[it])
        {
            int lb = lower_bound(x + 1,x + n + 1,i) - x;
            int val = st.get(1,lb);
            st.update(lb,min(max(0LL,d - i - val),u));
        }
        if(d - st.st[1] <= nen[it - 1]) minimize(ans,d - st.st[1]);
    }
    cout << ans;
}

Compilation message

FuelStation.cpp: In member function 'void SegmentTree::update(long long int, long long int, long long int, long long int, long long int)':
FuelStation.cpp:69:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |         int mid = l + r >> 1;
      |                   ~~^~~
FuelStation.cpp: At global scope:
FuelStation.cpp:97:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   97 | main()
      | ^~~~
FuelStation.cpp: In function 'int main()':
FuelStation.cpp:102:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |         freopen(name ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
FuelStation.cpp:103:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen(name ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 11 ms 24672 KB Output is correct
3 Correct 11 ms 24700 KB Output is correct
4 Correct 9 ms 24708 KB Output is correct
5 Correct 14 ms 24664 KB Output is correct
6 Correct 10 ms 24668 KB Output is correct
7 Correct 10 ms 24460 KB Output is correct
8 Correct 14 ms 24552 KB Output is correct
9 Correct 10 ms 24668 KB Output is correct
10 Correct 10 ms 24668 KB Output is correct
11 Correct 10 ms 24696 KB Output is correct
12 Correct 10 ms 24668 KB Output is correct
13 Correct 14 ms 24668 KB Output is correct
14 Correct 10 ms 24668 KB Output is correct
15 Correct 10 ms 23900 KB Output is correct

Subtask #2
0 / 13.0

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

Subtask #3
0 / 17.0

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

Subtask #4
0 / 12.0

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

Subtask #5
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 11 ms 24672 KB Output is correct
3 Correct 11 ms 24700 KB Output is correct
4 Correct 9 ms 24708 KB Output is correct
5 Correct 14 ms 24664 KB Output is correct
6 Correct 10 ms 24668 KB Output is correct
7 Correct 10 ms 24460 KB Output is correct
8 Correct 14 ms 24552 KB Output is correct
9 Correct 10 ms 24668 KB Output is correct
10 Correct 10 ms 24668 KB Output is correct
11 Correct 10 ms 24696 KB Output is correct
12 Correct 10 ms 24668 KB Output is correct
13 Correct 14 ms 24668 KB Output is correct
14 Correct 10 ms 24668 KB Output is correct
15 Correct 10 ms 23900 KB Output is correct
16 Correct 9 ms 23868 KB Output is correct
17 Incorrect 10 ms 23900 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 11 ms 24672 KB Output is correct
3 Correct 11 ms 24700 KB Output is correct
4 Correct 9 ms 24708 KB Output is correct
5 Correct 14 ms 24664 KB Output is correct
6 Correct 10 ms 24668 KB Output is correct
7 Correct 10 ms 24460 KB Output is correct
8 Correct 14 ms 24552 KB Output is correct
9 Correct 10 ms 24668 KB Output is correct
10 Correct 10 ms 24668 KB Output is correct
11 Correct 10 ms 24696 KB Output is correct
12 Correct 10 ms 24668 KB Output is correct
13 Correct 14 ms 24668 KB Output is correct
14 Correct 10 ms 24668 KB Output is correct
15 Correct 10 ms 23900 KB Output is correct
16 Correct 13 ms 23896 KB Output is correct
17 Incorrect 17 ms 25240 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #7
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24668 KB Output is correct
2 Correct 11 ms 24672 KB Output is correct
3 Correct 11 ms 24700 KB Output is correct
4 Correct 9 ms 24708 KB Output is correct
5 Correct 14 ms 24664 KB Output is correct
6 Correct 10 ms 24668 KB Output is correct
7 Correct 10 ms 24460 KB Output is correct
8 Correct 14 ms 24552 KB Output is correct
9 Correct 10 ms 24668 KB Output is correct
10 Correct 10 ms 24668 KB Output is correct
11 Correct 10 ms 24696 KB Output is correct
12 Correct 10 ms 24668 KB Output is correct
13 Correct 14 ms 24668 KB Output is correct
14 Correct 10 ms 24668 KB Output is correct
15 Correct 10 ms 23900 KB Output is correct
16 Incorrect 244 ms 68680 KB Output isn't correct
17 Halted 0 ms 0 KB -