Submission #1283955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283955		vuquangsang	Triple Jump (JOI19_jumps)	C++20	0 / 100	13 ms	1164 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

#define     el "\n"
#define     FOR(i,a,b) for(int i = (a), _b = (b); i <= _b; i++)
#define     FORD(i,a,b) for(int i = (a), _b = (b); i >= _b; i--)
#define     pb push_back
#define     fi first
#define     se second
#define     all(x) x.begin(),x.end()
#define     lg(x) __lg(x)
#define     alla(a,n) a+1,a+n+1
#define     ll long long
#define     pii pair<int, int>


template <class T> bool maxi(T &x, T y) { if(x < y) { x = y ; return true ;} return false;}
template <class T> bool mini(T &x, T y) { if(x > y) { x = y ; return true ;} return false;}

const int N = 5e5 + 2;

int n, q, a[N];

struct Queries
{
    int l, r;
} queries[N];

namespace subtask_12
{

    int rmq[N][21];

    void build_rmq()
    {
        FOR(i, 1, n) rmq[i][0] = a[i];

        for(int j = 1; (1 << j) - 1 <= n; j++) {
            for(int i = 1; i + (1 << j) - 1 <= n; i++) {
                rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int get(int l, int r)
    {
        if(l > r) return 0;
        int j = __lg(r - l + 1);
        return max(rmq[l][j], rmq[r - (1 << j) + 1][j]);
    }
    void slv()
    {
        build_rmq();
        for(int idx = 1; idx <= q; idx++) {
            int l = queries[idx].l, r = queries[idx].r;

            long long ans = 0;
            for(int i = l; i <= r - 2; i++) {
                int mid = (i + r) / 2;
                long long cost = a[i] + get(i + 1, mid) + get(mid + 1, r);
                ans = max(ans, cost);
            }
            cout << ans << el;
        }
    }
}
main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    #define __Azul__ "JOI19_jumps"
    if(fopen(__Azul__".inp", "r")) {
        freopen(__Azul__".inp", "r", stdin);
        freopen(__Azul__".out", "w", stdout);
    }

    cin >> n;
    FOR(i, 1, n) cin >> a[i];
    cin >> q;
    FOR(i, 1, q) cin >> queries[i].l >> queries[i].r;

    if(n <= 5000) return subtask_12 :: slv(), 0;

    cerr << "\nTime" << 0.001 * clock() << "s "; return 0;


}

Compilation message (stderr)

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

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