oj.uz

Submission #590038

# Submission time Handle Problem Language Result Execution time Memory
590038 2022-07-05T13:33:28 Z messiuuuuu Triple Jump (JOI19_jumps) C++14
46 / 100
 684 ms 43536 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 = 5e5 + 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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 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 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 275 ms 13584 KB Output is correct
12 Correct 253 ms 13496 KB Output is correct
13 Correct 253 ms 13592 KB Output is correct
14 Correct 260 ms 13552 KB Output is correct
15 Correct 255 ms 13636 KB Output is correct
16 Correct 269 ms 12988 KB Output is correct
17 Correct 253 ms 13016 KB Output is correct
18 Correct 250 ms 12956 KB Output is correct
19 Correct 261 ms 13580 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 16460 KB Output is correct
2 Correct 76 ms 15716 KB Output is correct
3 Correct 88 ms 14956 KB Output is correct
4 Correct 133 ms 16640 KB Output is correct
5 Correct 133 ms 16548 KB Output is correct
6 Correct 127 ms 16568 KB Output is correct
7 Correct 146 ms 16488 KB Output is correct
8 Correct 134 ms 16536 KB Output is correct
9 Correct 135 ms 16564 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 275 ms 13584 KB Output is correct
12 Correct 253 ms 13496 KB Output is correct
13 Correct 253 ms 13592 KB Output is correct
14 Correct 260 ms 13552 KB Output is correct
15 Correct 255 ms 13636 KB Output is correct
16 Correct 269 ms 12988 KB Output is correct
17 Correct 253 ms 13016 KB Output is correct
18 Correct 250 ms 12956 KB Output is correct
19 Correct 261 ms 13580 KB Output is correct
20 Correct 133 ms 16460 KB Output is correct
21 Correct 76 ms 15716 KB Output is correct
22 Correct 88 ms 14956 KB Output is correct
23 Correct 133 ms 16640 KB Output is correct
24 Correct 133 ms 16548 KB Output is correct
25 Correct 127 ms 16568 KB Output is correct
26 Correct 146 ms 16488 KB Output is correct
27 Correct 134 ms 16536 KB Output is correct
28 Correct 135 ms 16564 KB Output is correct
29 Incorrect 684 ms 43536 KB Output isn't correct
30 Halted 0 ms 0 KB -