oj.uz

Submission #287673

# Submission time Handle Problem Language Result Execution time Memory
287673 2020-08-31T22:09:58 Z the_art_of_war Triple Jump (JOI19_jumps) C++17
100 / 100
 1266 ms 86372 KB 
//
// 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 16 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 16 ms 23808 KB Output is correct
5 Correct 16 ms 23816 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 16 ms 23808 KB Output is correct
9 Correct 19 ms 23808 KB Output is correct
10 Correct 16 ms 23808 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 16 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 16 ms 23808 KB Output is correct
5 Correct 16 ms 23816 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 16 ms 23808 KB Output is correct
9 Correct 19 ms 23808 KB Output is correct
10 Correct 16 ms 23808 KB Output is correct
11 Correct 441 ms 41912 KB Output is correct
12 Correct 438 ms 41816 KB Output is correct
13 Correct 455 ms 41944 KB Output is correct
14 Correct 440 ms 41944 KB Output is correct
15 Correct 437 ms 41944 KB Output is correct
16 Correct 443 ms 41304 KB Output is correct
17 Correct 452 ms 41176 KB Output is correct
18 Correct 440 ms 41176 KB Output is correct
19 Correct 442 ms 41816 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 40424 KB Output is correct
2 Correct 123 ms 40428 KB Output is correct
3 Correct 122 ms 41136 KB Output is correct
4 Correct 206 ms 42088 KB Output is correct
5 Correct 206 ms 42212 KB Output is correct
6 Correct 200 ms 41440 KB Output is correct
7 Correct 203 ms 41440 KB Output is correct
8 Correct 203 ms 41440 KB Output is correct
9 Correct 204 ms 41700 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 16 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 16 ms 23808 KB Output is correct
5 Correct 16 ms 23816 KB Output is correct
6 Correct 17 ms 23808 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 16 ms 23808 KB Output is correct
9 Correct 19 ms 23808 KB Output is correct
10 Correct 16 ms 23808 KB Output is correct
11 Correct 441 ms 41912 KB Output is correct
12 Correct 438 ms 41816 KB Output is correct
13 Correct 455 ms 41944 KB Output is correct
14 Correct 440 ms 41944 KB Output is correct
15 Correct 437 ms 41944 KB Output is correct
16 Correct 443 ms 41304 KB Output is correct
17 Correct 452 ms 41176 KB Output is correct
18 Correct 440 ms 41176 KB Output is correct
19 Correct 442 ms 41816 KB Output is correct
20 Correct 206 ms 40424 KB Output is correct
21 Correct 123 ms 40428 KB Output is correct
22 Correct 122 ms 41136 KB Output is correct
23 Correct 206 ms 42088 KB Output is correct
24 Correct 206 ms 42212 KB Output is correct
25 Correct 200 ms 41440 KB Output is correct
26 Correct 203 ms 41440 KB Output is correct
27 Correct 203 ms 41440 KB Output is correct
28 Correct 204 ms 41700 KB Output is correct
29 Correct 1249 ms 86216 KB Output is correct
30 Correct 1032 ms 81428 KB Output is correct
31 Correct 1031 ms 83524 KB Output is correct
32 Correct 1258 ms 86000 KB Output is correct
33 Correct 1266 ms 86132 KB Output is correct
34 Correct 1255 ms 83732 KB Output is correct
35 Correct 1253 ms 83528 KB Output is correct
36 Correct 1237 ms 83400 KB Output is correct
37 Correct 1247 ms 84936 KB Output is correct
38 Correct 1018 ms 85960 KB Output is correct
39 Correct 1033 ms 86068 KB Output is correct
40 Correct 1002 ms 82724 KB Output is correct
41 Correct 986 ms 82292 KB Output is correct
42 Correct 991 ms 82264 KB Output is correct
43 Correct 1012 ms 83912 KB Output is correct
44 Correct 1058 ms 85960 KB Output is correct
45 Correct 1068 ms 86028 KB Output is correct
46 Correct 1048 ms 83024 KB Output is correct
47 Correct 1057 ms 82632 KB Output is correct
48 Correct 1048 ms 82632 KB Output is correct
49 Correct 1042 ms 84556 KB Output is correct
50 Correct 1109 ms 86372 KB Output is correct
51 Correct 1107 ms 86088 KB Output is correct
52 Correct 1089 ms 83536 KB Output is correct
53 Correct 1090 ms 83272 KB Output is correct
54 Correct 1103 ms 83400 KB Output is correct
55 Correct 1110 ms 85316 KB Output is correct