Submission #287673

#	Time	Username	Problem	Language	Result	Execution time	Memory
287673		the_art_of_war	Triple Jump (JOI19_jumps)	C++17	100 / 100	1266 ms	86372 KiB

jumps

//
// Created by Ильдар Ялалов on 14.01.2020.
//
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 8e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
typedef unsigned int uint;
#define pb push_back
#define eb emplace_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define mp make_pair
#define all(a) a.begin(),a.end()


#ifdef zxc

#include "debug.h"

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#define debug_arr(...) 42
#endif

bool debug = 0;
const int MAXN = (1e6) + 100;
const int LOG = 21;
const int mod = 1e9 + 7;
const int MX = (3e6 + 10);

int arr[MAXN];
int res[MAXN];

vector<int> add[MAXN];

#define left v<<1,tl,tm
#define right v<<1|1,tm+1,tr

int c[4 * MAXN];
int ab[4 * MAXN];
int val[4 * MAXN];

void calc(int v) {
    c[v] = max(c[v << 1], c[v << 1 | 1]);
    val[v] = max(val[v], max(val[v << 1], val[v << 1 | 1]));
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        c[v] = arr[tl];
        val[v] = -inf_int;
        ab[v] = -inf_int;
    } else {
        int tm = (tl + tr) >> 1;
        ab[v] = val[v] = -inf_int;
        build(left);
        build(right);
        calc(v);
    }
}

void push(int v) {
    int v1 = (v << 1);
    int v2 = (v << 1 | 1);
    ab[v1] = max(ab[v1], ab[v]);
    ab[v2] = max(ab[v2], ab[v]);
    val[v1] = max(val[v1], ab[v1] + c[v1]);
    val[v2] = max(val[v2], ab[v2] + c[v2]);
}

void update(int v, int tl, int tr, int l, int r, int x) {
    if (l > tr || r < tl)
        return;
    if (l <= tl && tr <= r) {
        ab[v] = max(ab[v], x);
        val[v] = max(val[v], c[v] + ab[v]);
    } else {
        int tm = (tl + tr) >> 1;
        push(v);
        update(left, l, r, x);
        update(right, l, r, x);
        calc(v);
    }
}

int get(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl)
        return -inf_int;
    if (l <= tl && tr <= r) {
        return val[v];
    } else {
        int tm = (tl + tr) >> 1;
        push(v);
        int res1 = get(left, l, r);
        int res2 = get(right, l, r);
        calc(v);
        return max(res1, res2);
    }
}

void solve() {
    int n, q;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }
    cin >> q;
    vector<pair<pii, int> > cc;
    for (int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        cc.pb({{l, r}, i});
    }
    sort(all(cc));

    vector<pii> pairs;

    stack<int> st;
    for (int i = 1; i <= n; ++i) {
        while (!st.empty() && arr[i] >= arr[st.top()]) {
            pairs.pb({st.top(), i});
            st.pop();
        }
        if (!st.empty()) {
            pairs.pb({st.top(), i});
        }
        st.push(i);
    }
    debug(pairs);


    for (auto x :  pairs) {
        add[x.fi].pb(x.se);
    }


    debug(cc);

    int top = sz(cc) - 1;

    build(1, 0, n);
    for (int a = n; a >= 1; --a) {
        debug(a);
        for (int b : add[a]) {
            int st = 2 * b - a;
            debug(a, b, st);
            update(1, 0, n, st, n, arr[a] + arr[b]);
        }

        while (top >= 0 && cc[top].fi.fi >= a) {
            int r = cc[top].fi.se;
            int id = cc[top].se;
            debug("ask", a, r);
            res[id] = get(1, 0, n, a, r);
            top--;
        }
    }

    for (int i = 1; i <= q; ++i) {
        cout << res[i] << "\n";
    }

}


// CHECK LIMITS (n <= 10^5)
// CHECK CORNER CASES ( n==1)
signed main() {

#ifdef zxc
    freopen("../output.txt", "r", stdin);
    // freopen("../output1.txt", "w", stdout);
#else
#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(15);


    int t = 1;
    while (t--)
        solve();

    debug(1.0 * clock() / CLOCKS_PER_SEC);
}

Compilation message (stderr)

jumps.cpp: In function 'void solve()':
jumps.cpp:36:20: warning: statement has no effect [-Wunused-value]
   36 | #define debug(...) 42
      |                    ^~
jumps.cpp:144:5: note: in expansion of macro 'debug'
  144 |     debug(pairs);
      |     ^~~~~
jumps.cpp:36:20: warning: statement has no effect [-Wunused-value]
   36 | #define debug(...) 42
      |                    ^~
jumps.cpp:152:5: note: in expansion of macro 'debug'
  152 |     debug(cc);
      |     ^~~~~
jumps.cpp:36:20: warning: statement has no effect [-Wunused-value]
   36 | #define debug(...) 42
      |                    ^~
jumps.cpp:158:9: note: in expansion of macro 'debug'
  158 |         debug(a);
      |         ^~~~~
jumps.cpp:36:20: warning: statement has no effect [-Wunused-value]
   36 | #define debug(...) 42
      |                    ^~
jumps.cpp:161:13: note: in expansion of macro 'debug'
  161 |             debug(a, b, st);
      |             ^~~~~
jumps.cpp:36:20: warning: statement has no effect [-Wunused-value]
   36 | #define debug(...) 42
      |                    ^~
jumps.cpp:168:13: note: in expansion of macro 'debug'
  168 |             debug("ask", a, r);
      |             ^~~~~
jumps.cpp: In function 'int main()':
jumps.cpp:36:20: warning: statement has no effect [-Wunused-value]
   36 | #define debug(...) 42
      |                    ^~
jumps.cpp:201:5: note: in expansion of macro 'debug'
  201 |     debug(1.0 * clock() / CLOCKS_PER_SEC);
      |     ^~~~~

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