oj.uz

Submission #859349

# Submission time Handle Problem Language Result Execution time Memory
859349 2023-10-10T04:32:36 Z Boycl07 Triple Jump (JOI19_jumps) C++17
100 / 100
 470 ms 48624 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define task "MEETING"
#define endl "\n"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }


const int N =  5e5 + 10;
const int N1 = 2e3 + 10;
const int K = 1e2 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 1;
const int block_size = 230;
const int LOG = 13;
const int offset = N;
const int LIM = 2e5;
const int AL = 26;
const int M = 11;
const int lim = (1 << 10) - 1;


int n;
int a[N];
int q;

struct node
{
    int x, y, v;
    node () {
        x = 0, y = 0, v = 0;
    }
    node (int x_, int y_, int v_) : x(x_), y(y_), v(v_) {}
    friend node operator + (const node &u, const node &v) {
        return node(max(u.x, v.x), max(u.y, v.y), max(max(u.v, v.v), u.x + v.y));
    }
};


node st[N << 1];

void build()
{
    for(int i = 1; i <= n; ++i)
        st[i + n].y = st[i + n].v = a[i], st[i + n].x = 0;
    for(int i = n; i >= 1; --i)
        st[i] = st[i << 1] + st[i << 1 | 1];
}

void update(int idx, int val)
{
    idx += n;
    maximize(st[idx].x, val);
    st[idx].v = st[idx].x + st[idx].y;
    for(; idx >>= 1;)
    {
        st[idx] = st[idx << 1] + st[idx << 1 | 1];
    }
}

ll get(int l, int r)
{
    node resl(0, 0, 0);
    node resr(0, 0, 0);
    for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
    {
        
        if(l & 1) resl = resl + st[l++];
        if( r & 1) resr = st[--r] + resr;
        //cout << l << " " << r << endl;
        //cout << endl;
    }
    return (resl + resr).v;
}


vector<pii> query[N];
int res[N];

void solve()
{
    cin >> n;
    rep(i, n) cin >> a[i];
    build();
    cin >> q;
    rep(i, q)
    {
        int l, r;
        cin >> l >> r;
        query[l].pb({r, i});
    }   

    stack<int> s;
    ford(i, n, 1)
    {
        while(sz(s) && a[s.top()] < a[i])
        {
            if(2 * s.top() - i <= n)
                update(2 * s.top() - i, a[i] + a[s.top()]);// cout << 2 * s.top() - i << " " << a[i] + a[s.top()] << endl;
           
            s.pop();
        }
        if(sz(s))
        {
            if(2 * s.top() - i <= n)
                update(2 * s.top() - i, a[i] + a[s.top()]);// cout << 2 * s.top() - i << " " << a[i] + a[s.top()] << endl;
        }
        s.push(i);
        for(auto &[j, idx] : query[i])
            res[idx] = get(i, j);
    }
    rep(i, q) cout << res[i] << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if(fopen("trie.inp", "r"))
    {
        freopen("trie.inp", "r", stdin);
        freopen("trie.out", "w", stdout);
    }

    int TC = 1;

    while(TC--)
    {
        solve();
        cout << endl;
    }

    return 0;
}
//ha

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen("trie.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen("trie.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26972 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 27132 KB Output is correct
6 Correct 5 ms 26972 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 5 ms 26972 KB Output is correct
9 Correct 5 ms 26972 KB Output is correct
10 Correct 5 ms 26972 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26972 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 27132 KB Output is correct
6 Correct 5 ms 26972 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 5 ms 26972 KB Output is correct
9 Correct 5 ms 26972 KB Output is correct
10 Correct 5 ms 26972 KB Output is correct
11 Correct 146 ms 39248 KB Output is correct
12 Correct 132 ms 38952 KB Output is correct
13 Correct 130 ms 38992 KB Output is correct
14 Correct 141 ms 39248 KB Output is correct
15 Correct 143 ms 39248 KB Output is correct
16 Correct 163 ms 38588 KB Output is correct
17 Correct 144 ms 38468 KB Output is correct
18 Correct 161 ms 38320 KB Output is correct
19 Correct 147 ms 39056 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 26972 KB Output is correct
2 Correct 34 ms 27732 KB Output is correct
3 Correct 44 ms 26972 KB Output is correct
4 Correct 65 ms 27216 KB Output is correct
5 Correct 64 ms 26968 KB Output is correct
6 Correct 61 ms 26972 KB Output is correct
7 Correct 60 ms 26972 KB Output is correct
8 Correct 61 ms 26972 KB Output is correct
9 Correct 61 ms 26968 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 26972 KB Output is correct
2 Correct 5 ms 26972 KB Output is correct
3 Correct 4 ms 26972 KB Output is correct
4 Correct 5 ms 26972 KB Output is correct
5 Correct 5 ms 27132 KB Output is correct
6 Correct 5 ms 26972 KB Output is correct
7 Correct 4 ms 26972 KB Output is correct
8 Correct 5 ms 26972 KB Output is correct
9 Correct 5 ms 26972 KB Output is correct
10 Correct 5 ms 26972 KB Output is correct
11 Correct 146 ms 39248 KB Output is correct
12 Correct 132 ms 38952 KB Output is correct
13 Correct 130 ms 38992 KB Output is correct
14 Correct 141 ms 39248 KB Output is correct
15 Correct 143 ms 39248 KB Output is correct
16 Correct 163 ms 38588 KB Output is correct
17 Correct 144 ms 38468 KB Output is correct
18 Correct 161 ms 38320 KB Output is correct
19 Correct 147 ms 39056 KB Output is correct
20 Correct 64 ms 26972 KB Output is correct
21 Correct 34 ms 27732 KB Output is correct
22 Correct 44 ms 26972 KB Output is correct
23 Correct 65 ms 27216 KB Output is correct
24 Correct 64 ms 26968 KB Output is correct
25 Correct 61 ms 26972 KB Output is correct
26 Correct 60 ms 26972 KB Output is correct
27 Correct 61 ms 26972 KB Output is correct
28 Correct 61 ms 26968 KB Output is correct
29 Correct 442 ms 42612 KB Output is correct
30 Correct 332 ms 44596 KB Output is correct
31 Correct 350 ms 42580 KB Output is correct
32 Correct 424 ms 42748 KB Output is correct
33 Correct 451 ms 42636 KB Output is correct
34 Correct 431 ms 42032 KB Output is correct
35 Correct 470 ms 42068 KB Output is correct
36 Correct 425 ms 41916 KB Output is correct
37 Correct 424 ms 42620 KB Output is correct
38 Correct 299 ms 48624 KB Output is correct
39 Correct 302 ms 48356 KB Output is correct
40 Correct 294 ms 46908 KB Output is correct
41 Correct 291 ms 46404 KB Output is correct
42 Correct 287 ms 46416 KB Output is correct
43 Correct 296 ms 47348 KB Output is correct
44 Correct 318 ms 47608 KB Output is correct
45 Correct 320 ms 47700 KB Output is correct
46 Correct 304 ms 46136 KB Output is correct
47 Correct 310 ms 45948 KB Output is correct
48 Correct 305 ms 45964 KB Output is correct
49 Correct 307 ms 47288 KB Output is correct
50 Correct 360 ms 45744 KB Output is correct
51 Correct 388 ms 45648 KB Output is correct
52 Correct 354 ms 45228 KB Output is correct
53 Correct 336 ms 44888 KB Output is correct
54 Correct 340 ms 44780 KB Output is correct
55 Correct 348 ms 45812 KB Output is correct