oj.uz

Submission #590040

# Submission time Handle Problem Language Result Execution time Memory
590040 2022-07-05T13:34:19 Z messiuuuuu Triple Jump (JOI19_jumps) C++14
100 / 100
 908 ms 58660 KB 
#include<bits/stdc++.h>
#define task "C"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 1e6 + 5;
const ll INF = 1e18 + 5;

int n, q;
int a[MAXN];
struct TQuery
{
    int l, r, id;
};
TQuery qu[MAXN];

void Input()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> qu[i].l >> qu[i].r;
        qu[i].id = i;
    }
}

pair<ll, int> st[4 * MAXN];
ll lazy[4 * MAXN];

pair<ll, int> Comb(const pair<ll, int>& l, const pair<ll, int>& r)
{
    return make_pair(max(l.fi, r.fi), max(l.se, r.se));
}

void Build(int id, int l, int r)
{
    if (l == r)
    {
        st[id] = {a[l], a[l]};
        return;
    }
    int mid = (l + r) / 2;
    Build(2 * id, l, mid);
    Build(2 * id + 1, mid + 1, r);
    st[id] = Comb(st[2 * id], st[2 * id + 1]);
}

pair<int, int> seg[MAXN];
int nseg = 0;

void down(int id)
{
    ll& t = lazy[id];
    if (!t)
        return;
    st[2 * id].fi = max(st[2 * id].fi, st[2 * id].se + t);
    st[2 * id + 1].fi = max(st[2 * id + 1].fi, st[2 * id + 1].se + t);
    lazy[2 * id] = max(lazy[2 * id], t);
    lazy[2 * id + 1] = max(lazy[2 * id + 1], t);
    t = 0;
    return;
}

void Update(int id, int l, int r, int u, int v, ll val)
{
    if (u > v)
        return;
    if (r < u || v < l)
        return;
    if (u <= l && r <= v)
    {
        st[id].fi = max(st[id].fi, val + st[id].se);
        lazy[id] = max(lazy[id], val);
        return;
    }
    down(id);
    int mid = (l + r) / 2;
    Update(2 * id, l, mid, u, v, val);
    Update(2 * id + 1, mid + 1, r, u, v, val);
    st[id] = Comb(st[2 * id], st[2 * id + 1]);
}

ll Get(int id, int l, int r, int u, int v)
{
    if (r < u || v < l)
        return 0;
    if (u <= l && r <= v)
    {
        return st[id].fi;
    }
    down(id);
    int mid = (l + r) / 2;
    return max(Get(2 * id, l, mid, u, v), Get(2 * id + 1, mid + 1, r, u, v));
}

int ans[MAXN];

void Solve()
{
    Build(1, 1, n);
    stack<int> S;
    for (int i = n; i >= 1; i--)
    {
        while (!S.empty() && a[i] > a[S.top()])
        {
            seg[++nseg] = make_pair(i, S.top());
            S.pop();
        }
        if (!S.empty())
            seg[++nseg] = make_pair(i, S.top());
        S.push(i);
    }
    sort(qu + 1, qu + q + 1, [](const auto& i, const auto& j)
         {
             return i.l > j.l;
         });
    sort(seg + 1, seg + nseg + 1, [](const auto& i, const auto& j)
         {
             return i.fi > j.fi;
         });
    int j = 1;
    for (int i = 1; i <= q; i++)
    {
        while (j <= nseg && seg[j].fi >= qu[i].l)
        {
            Update(1, 1, n, 2 * seg[j].se - seg[j].fi, n, a[seg[j].se] + a[seg[j].fi]);
            j++;
        }
        ans[qu[i].id] = Get(1, 1, n, qu[i].l, qu[i].r);
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(task".INP","r"))
    {
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    Input();
    Solve();
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 272 ms 13608 KB Output is correct
12 Correct 246 ms 13608 KB Output is correct
13 Correct 267 ms 13588 KB Output is correct
14 Correct 257 ms 13572 KB Output is correct
15 Correct 251 ms 13600 KB Output is correct
16 Correct 275 ms 12976 KB Output is correct
17 Correct 247 ms 13004 KB Output is correct
18 Correct 256 ms 12992 KB Output is correct
19 Correct 248 ms 13528 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 16560 KB Output is correct
2 Correct 75 ms 15804 KB Output is correct
3 Correct 76 ms 14968 KB Output is correct
4 Correct 130 ms 16520 KB Output is correct
5 Correct 130 ms 16560 KB Output is correct
6 Correct 126 ms 16560 KB Output is correct
7 Correct 134 ms 16532 KB Output is correct
8 Correct 151 ms 16536 KB Output is correct
9 Correct 128 ms 16476 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 272 ms 13608 KB Output is correct
12 Correct 246 ms 13608 KB Output is correct
13 Correct 267 ms 13588 KB Output is correct
14 Correct 257 ms 13572 KB Output is correct
15 Correct 251 ms 13600 KB Output is correct
16 Correct 275 ms 12976 KB Output is correct
17 Correct 247 ms 13004 KB Output is correct
18 Correct 256 ms 12992 KB Output is correct
19 Correct 248 ms 13528 KB Output is correct
20 Correct 137 ms 16560 KB Output is correct
21 Correct 75 ms 15804 KB Output is correct
22 Correct 76 ms 14968 KB Output is correct
23 Correct 130 ms 16520 KB Output is correct
24 Correct 130 ms 16560 KB Output is correct
25 Correct 126 ms 16560 KB Output is correct
26 Correct 134 ms 16532 KB Output is correct
27 Correct 151 ms 16536 KB Output is correct
28 Correct 128 ms 16476 KB Output is correct
29 Correct 908 ms 47500 KB Output is correct
30 Correct 661 ms 56588 KB Output is correct
31 Correct 650 ms 54560 KB Output is correct
32 Correct 825 ms 58524 KB Output is correct
33 Correct 813 ms 58592 KB Output is correct
34 Correct 833 ms 56228 KB Output is correct
35 Correct 805 ms 55888 KB Output is correct
36 Correct 823 ms 56140 KB Output is correct
37 Correct 806 ms 57440 KB Output is correct
38 Correct 629 ms 58608 KB Output is correct
39 Correct 643 ms 58476 KB Output is correct
40 Correct 615 ms 55316 KB Output is correct
41 Correct 609 ms 54668 KB Output is correct
42 Correct 630 ms 54736 KB Output is correct
43 Correct 625 ms 56496 KB Output is correct
44 Correct 650 ms 58660 KB Output is correct
45 Correct 639 ms 58492 KB Output is correct
46 Correct 646 ms 55340 KB Output is correct
47 Correct 656 ms 55208 KB Output is correct
48 Correct 695 ms 54948 KB Output is correct
49 Correct 657 ms 57012 KB Output is correct
50 Correct 819 ms 58520 KB Output is correct
51 Correct 741 ms 58564 KB Output is correct
52 Correct 747 ms 56068 KB Output is correct
53 Correct 757 ms 55760 KB Output is correct
54 Correct 830 ms 55812 KB Output is correct
55 Correct 767 ms 57396 KB Output is correct