oj.uz

Submission #590032

# Submission time Handle Problem Language Result Execution time Memory
590032 2022-07-05T13:31:28 Z messiuuuuu Triple Jump (JOI19_jumps) C++14
46 / 100
 713 ms 54396 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 (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:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 1 ms 340 KB Output is correct
6 Correct 1 ms 328 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 324 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 1 ms 340 KB Output is correct
6 Correct 1 ms 328 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 324 KB Output is correct
11 Correct 335 ms 18268 KB Output is correct
12 Correct 310 ms 18308 KB Output is correct
13 Correct 280 ms 18180 KB Output is correct
14 Correct 347 ms 18296 KB Output is correct
15 Correct 286 ms 18292 KB Output is correct
16 Correct 331 ms 17644 KB Output is correct
17 Correct 254 ms 17556 KB Output is correct
18 Correct 276 ms 17568 KB Output is correct
19 Correct 279 ms 18176 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 18252 KB Output is correct
2 Correct 72 ms 17600 KB Output is correct
3 Correct 69 ms 16744 KB Output is correct
4 Correct 136 ms 18252 KB Output is correct
5 Correct 134 ms 18296 KB Output is correct
6 Correct 124 ms 17552 KB Output is correct
7 Correct 123 ms 17504 KB Output is correct
8 Correct 128 ms 17548 KB Output is correct
9 Correct 123 ms 17808 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 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 1 ms 340 KB Output is correct
6 Correct 1 ms 328 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 324 KB Output is correct
11 Correct 335 ms 18268 KB Output is correct
12 Correct 310 ms 18308 KB Output is correct
13 Correct 280 ms 18180 KB Output is correct
14 Correct 347 ms 18296 KB Output is correct
15 Correct 286 ms 18292 KB Output is correct
16 Correct 331 ms 17644 KB Output is correct
17 Correct 254 ms 17556 KB Output is correct
18 Correct 276 ms 17568 KB Output is correct
19 Correct 279 ms 18176 KB Output is correct
20 Correct 127 ms 18252 KB Output is correct
21 Correct 72 ms 17600 KB Output is correct
22 Correct 69 ms 16744 KB Output is correct
23 Correct 136 ms 18252 KB Output is correct
24 Correct 134 ms 18296 KB Output is correct
25 Correct 124 ms 17552 KB Output is correct
26 Correct 123 ms 17504 KB Output is correct
27 Correct 128 ms 17548 KB Output is correct
28 Correct 123 ms 17808 KB Output is correct
29 Incorrect 713 ms 54396 KB Output isn't correct
30 Halted 0 ms 0 KB -