oj.uz

Submission #1094900

# Submission time Handle Problem Language Result Execution time Memory
1094900 2024-09-30T20:23:37 Z raphaelp Bouquet (EGOI24_bouquet) C++14
0 / 100
 38 ms 3532 KB 
#include <bits/stdc++.h>
using namespace std;
class SegTree
{
private:
    vector<int> st;
    int N;
    int l(int x) { return (x << 1); }
    int r(int x) { return (x << 1) + 1; }
    void update(int L, int R, int a, int val, int x)
    {
        if (L > a || R < a)
            return;
        if (L == a && R == a)
        {
            st[x] = val;
        }
        else
        {
            int m = (L + R) / 2;
            update(L, m, a, val, l(x));
            update(m + 1, R, a, val, r(x));
            st[x] = max(st[l(x)], st[r(x)]);
        }
    }
    int RMQ(int L, int R, int a, int b, int x)
    {
        if (L > b || R < a)
            return 0;
        if (L >= a && R <= b)
            return st[x];
        int m = (L + R) / 2;
        return max(RMQ(L, m, a, b, l(x)), RMQ(m + 1, R, a, b, r(x)));
    }

public:
    SegTree(int x)
    {
        N = pow(2, ceil(log2(N)));
        st.assign(2 * N, 0);
    }
    void update(int x, int val) { update(0, N - 1, x, val, 1); }
    int RMQ(int a, int b)
    {
        if (a > b)
            return 0;
        else
            return RMQ(0, N - 1, a, b, 1);
    }
};
int main()
{
    int N;
    cin >> N;
    vector<int> lef(N), rig(N);
    for (int i = 0; i < N; i++)
    {
        cin >> lef[i] >> rig[i];
    }
    SegTree ST(N);
    vector<int> dp(N);
    priority_queue<pair<int, int>> PQ;
    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        while (!PQ.empty() && -PQ.top().first < i)
        {
            ST.update(PQ.top().second, dp[PQ.top().second]);
            PQ.pop();
        }
        dp[i] = ST.RMQ(0, i - lef[i] - 1);
        dp[i]++;
        PQ.push({-(i + rig[i]), i});
        ans = max(ans, dp[i]);
    }
    cout << ans;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:39:16: warning: 'ST.SegTree::N' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |         N = pow(2, ceil(log2(N)));
      |             ~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0.0 / 8.0

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

Subtask #2
0.0 / 16.0

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

Subtask #3
0.0 / 28.0

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

Subtask #4
0.0 / 18.0

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

Subtask #5
0.0 / 30.0

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