Submission #885593

#	Time	Username	Problem	Language	Result	Execution time	Memory
885593		rukashii	Triple Jump (JOI19_jumps)	C++17	100 / 100	816 ms	193424 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
 
#define file  if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
// #define int long long
#define f first
#define s second
 
void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
    if (s.size()) setIn(s+".inp"), setOut(s+".out");
}
 
const int maxn = 5e5 + 2;
 
int a[maxn], n, q;
 
namespace Sub1
{
    void solve()
    {
        while (q--)
        {
            int l, r, ans = 0;
            cin >> l >> r;
 
            for (int i = l; i <= r; i++)
            {
                for (int j = i + 1; j <= r; j++)
                {
                    for (int k = j + 1; k <= r; k++)
                    {
                        if (k - j >= j - i)
                        {
                            ans = max(ans, a[i] + a[j] + a[k]);
                        }
                    }
                }
            }
 
            cout << ans << '\n';
        }
    }
} // namespace Sub1
 
namespace Sub2
{
    const int s2maxn = 5002;
 
    int dp[s2maxn][s2maxn], mx[s2maxn][s2maxn];
    void solve()
    {
        for (int i = 1; i <= n; i++)
        {
            mx[i][i] = a[i];
        }
 
        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                mx[i][j] = max(mx[i][j - 1], a[j]);
            }
        }
 
        for (int sz = 3; sz <= n; sz++)
        {
            for (int i = 1; i + sz - 1 <= n; i++)
            {
                int l = i, r = i + sz - 1;
                // if (sz == 3 && i == 1)
                    // cout << l << ' ' << r << ' ' << (l + r) / 2 << ' ' << mx[l][(l + r) / 2] << '\n';
                dp[l][r] = max({dp[l + 1][r], dp[l][r - 1], a[l] + a[r] + mx[l + 1][(l + r) / 2]});
            }
        }
 
        while (q--)
        {
            int l, r;
            cin >> l >> r;
 
            cout << dp[l][r] << '\n';
        }
    }
} // namespace Sub2
 
namespace Sub3
{
int prf[maxn];

void solve()
{
    stack <int> st;
    for (int i = 1; i <= n; i++)
    {
        while (st.size() && a[st.top()] < a[i])
        {
            if (i + (i - st.top() + 1) - 1 <= n)
                prf[i + i - st.top()] = max(prf[i + i - st.top()], a[i] + a[st.top()]);
            
            st.pop();
        }

        if (st.size())
            if (i + (i - st.top() + 1) - 1 <= n)
                prf[i + i - st.top()] = max(prf[i + i - st.top()], a[i] + a[st.top()]);
        st.push(i);
    }

    for (int i = 1; i <= n; i++)
    {
        prf[i] = max(prf[i - 1], prf[i]);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, prf[i] + a[i]);
    }

    cout << ans << '\n';
}
} // namespace Sub3

namespace Sub4
{
    struct node
    {
        int cur, mx, v;
    };

    node tree[maxn * 4];
    
    void build(int id, int l, int r)
    {
        if (l == r)
        {
            tree[id].cur = a[l];
            tree[id].v = a[l];
            return;
        }

        int mid = (l + r) / 2;

        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r);

        tree[id].v = max({tree[id * 2].v, tree[id * 2 + 1].v, tree[id * 2].mx + tree[id * 2 + 1].cur});
        tree[id].cur = max(tree[id * 2].cur, tree[id * 2 + 1].cur);
    }

    // void push(int id)
    // {
    //     int tmp = tree[id].mx ;

    //     tree[id * 2].mx = max(tmp, tree[id * 2].mx);
    //     tree[id * 2 + 1].mx = max(tmp, tree[id * 2 + 1].mx);
    //     tree[id * 2].v = max(tmp + tree[id * 2].cur, tree[id * 2].v);
    //     tree[id * 2 + 1].v = max(tmp + tree[id * 2 + 1].cur, tree[id * 2 + 1].v);
    // }

    node merge(node l, node r)
    {
        return {max(l.cur, r.cur), max(l.mx, r.mx), max({l.v, l.mx + r.cur, r.v})};
    }

    void update(int id, int l, int r, int u, int v, int vl)
    {
        if (r < u || v < l)
            return;
        if (l >= u && r <= v)
        {
            
            tree[id].mx = max(tree[id].mx, vl);
            tree[id].v = max(tree[id].cur + tree[id].mx, tree[id].v);
            return;
        }

        // push(id);
        int mid = (l + r) / 2;

        update(id * 2, l, mid, u, v, vl);
        update(id * 2 + 1, mid + 1, r, u, v, vl);

        tree[id] = merge(tree[id * 2], tree[id * 2 + 1]);
    }

    node get(int id, int l, int r, int u, int v)
    {
        if(r < u || v < l)
            return {0, 0, 0};
        if (l >= u && r <= v)
        {
            // cout << l << ' ' << r << ' ' << tree[id].v << '\n';
            return tree[id];
        }

        // push(id);
        int mid = (l + r) / 2;

        return merge(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
    }

    vector <pair <int, int>> Q[maxn];
    int ans[maxn];

    void solve()
    {
        for (int i = 1; i <= q; i++)
        {
            int l, r;
            cin >> l >> r;
            Q[l].push_back({r, i});
        }        

        build(1, 1, n);

        stack <int> st;
        for (int i = n; i >= 1; i--)
        {
            while (st.size() && a[st.top()] < a[i])
            {
                if (-i + 2 * st.top() <= n)
                    update(1, 1, n, -i + 2 * st.top(), -i + 2 * st.top(), a[i] + a[st.top()]);
                st.pop();
            }

            if (st.size())
                if (-i + 2 * st.top() <= n)
                    update(1, 1, n, -i + 2 * st.top(), -i + 2 * st.top(), a[i] + a[st.top()]);

            st.push(i);
            for (auto [r, id] : Q[i])
            {
                ans[id] = get(1, 1, n, i, r).v;
                // cout << " -> " <<  id << ' ' << ans[id] << '\n';
            }
        }

        // cout << tree[1].v << '\n';
        for (int i = 1; i <= q; i++)
            cout << ans[i] << "\n";
    }
} // namespace Sub4

 
signed main()
{
    // setIO();
    file;
    ios::sync_with_stdio(0); cin.tie(0);
 
    cin >> n;
    for (int i = 1; i <= n; i++)    
        cin >> a[i];
 
    cin >> q;
    if (n <= 100)
    {
        return Sub1::solve(), 0;
    }
    if (n <= 5000)
    {
        return Sub2::solve(), 0;
    }
    if (q == 1)
    {
        return Sub3::solve(), 0;
    }
    return Sub4::solve(), 0;
}

Compilation message (stderr)

jumps.cpp: In function 'void setIn(std::string)':
jumps.cpp:9:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 | void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'void setOut(std::string)':
jumps.cpp:10:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 | void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp: In function 'int main()':
jumps.cpp:4:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file  if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:250:5: note: in expansion of macro 'file'
  250 |     file;
      |     ^~~~
jumps.cpp:4:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file  if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
      |                                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:250:5: note: in expansion of macro 'file'
  250 |     file;
      |     ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54