Submission #197729

#	Time	Username	Problem	Language	Result	Execution time	Memory
197729		HellAngel	Triple Jump (JOI19_jumps)	C++14	100 / 100	1331 ms	99576 KiB

jumps

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 5e5 + 7;
stack<int> st;
int n, m, a[maxn], ans[maxn];

vector<pair<int, int>> q[maxn];

vector<int> p[maxn];

struct Node
{
    int l, r, ans;
    Node(){};
    Node(int l, int r, int ans): l(l), r(r), ans(ans) {};
    Node operator + (const Node &other) const {
        Node cc;
        cc.l = max(l, other.l);
        cc.r = max(r, other.r);
        cc.ans = max({ans, other.ans, l + other.r});
        return cc;
    }
} IT[4 * maxn];

void Build(int id, int l, int r)
{
    if(l == r)
    {
        IT[id].r = a[l];
        return;
    }
    int mid = l + r >> 1;
    Build(id * 2, l, mid);
    Build(id * 2 + 1, mid + 1, r);
    IT[id] = IT[id * 2] + IT[id * 2 + 1];
}

void Update(int id, int l, int r, int u, int val)
{
    if(l == r)
    {
        IT[id].l = max(IT[id].l, val);
        return;
    }
    int mid = l + r >> 1;
    if(u <= mid) Update(id * 2, l, mid, u, val);
    else Update(id * 2 + 1, mid + 1, r, u, val);
    IT[id] = IT[id * 2] + IT[id * 2 + 1];
}

Node Query(int id, int l, int r, int u, int v)
{
    if(l > v || r < u) return {0, 0, 0};
    if(u <= l && r <= v)
    {
        return IT[id];
    }
    int mid = l + r >> 1;
    return Query(id * 2, l, mid, u, v) + Query(id * 2 + 1, mid + 1, r, u, v);
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
    cin >> n;
    /// first we need to list all the potential pair for 2 elements (a, b)
    /// if it exists k such that a < k < b and a[k] > a[b], (a, b) will not the optimal pair we need because we can choose (a, k) for a better solution
    /// in the same way if it exists k such that a < k < b and a[a] < a[k] < a[b], (a, b) will not the optimal pair we need because we can choose (k, b) for a better solution
    /// => for every k such that a < k < b, there must be a[a] > a[k] and a[k] < a[b]
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        while(!st.empty() && a[st.top()] <= a[i])
        {
            p[st.top()].push_back(i);
            st.pop();
        }
        if(!st.empty()) p[st.top()].push_back(i);
        st.push(i);
    }
    Build(1, 1, n);
    cin >> m;
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        q[u].emplace_back(v, i);
    }
    for(int i = n; i >= 1; i--)
    {
        for(auto j: p[i])
        {
            int cc = 2 * j - i - 1;
            if(cc <= n)
            Update(1, 1, n, cc, a[i] + a[j]);
        }
        for(auto j: q[i])
        {
            ans[j.second] = Query(1, 1, n, i, j.first).ans;
        }
    }
    for(int i = 1; i <= m; i++) cout << ans[i] << '\n';
}

Compilation message (stderr)

jumps.cpp: In function 'void Build(long long int, long long int, long long int)':
jumps.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
jumps.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:47:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
jumps.cpp: In function 'Node Query(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:60:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
jumps.cpp: In function 'int32_t main()':
jumps.cpp:68:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:68:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54