제출 #590038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
590038		messiuuuuu	3단 점프 (JOI19_jumps)	C++14	46 / 100	684 ms	43536 KiB

jumps

#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();
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 0 / 54