oj.uz

Submission #197729

# Submission time Handle Problem Language Result Execution time Memory
197729 2020-01-22T15:19:03 Z HellAngel Triple Jump (JOI19_jumps) C++14
100 / 100
 1331 ms 99576 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 25 ms 23800 KB Output is correct
3 Correct 24 ms 23800 KB Output is correct
4 Correct 24 ms 23932 KB Output is correct
5 Correct 25 ms 23800 KB Output is correct
6 Correct 25 ms 23800 KB Output is correct
7 Correct 25 ms 23928 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Correct 24 ms 23800 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 25 ms 23800 KB Output is correct
3 Correct 24 ms 23800 KB Output is correct
4 Correct 24 ms 23932 KB Output is correct
5 Correct 25 ms 23800 KB Output is correct
6 Correct 25 ms 23800 KB Output is correct
7 Correct 25 ms 23928 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Correct 24 ms 23800 KB Output is correct
11 Correct 454 ms 50792 KB Output is correct
12 Correct 460 ms 50776 KB Output is correct
13 Correct 460 ms 50728 KB Output is correct
14 Correct 443 ms 50936 KB Output is correct
15 Correct 440 ms 50792 KB Output is correct
16 Correct 447 ms 50028 KB Output is correct
17 Correct 454 ms 50076 KB Output is correct
18 Correct 448 ms 50168 KB Output is correct
19 Correct 447 ms 50552 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 46940 KB Output is correct
2 Correct 114 ms 45688 KB Output is correct
3 Correct 116 ms 47416 KB Output is correct
4 Correct 195 ms 47068 KB Output is correct
5 Correct 209 ms 47096 KB Output is correct
6 Correct 188 ms 46300 KB Output is correct
7 Correct 187 ms 46200 KB Output is correct
8 Correct 185 ms 46328 KB Output is correct
9 Correct 189 ms 46584 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Correct 25 ms 23800 KB Output is correct
3 Correct 24 ms 23800 KB Output is correct
4 Correct 24 ms 23932 KB Output is correct
5 Correct 25 ms 23800 KB Output is correct
6 Correct 25 ms 23800 KB Output is correct
7 Correct 25 ms 23928 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 24 ms 23928 KB Output is correct
10 Correct 24 ms 23800 KB Output is correct
11 Correct 454 ms 50792 KB Output is correct
12 Correct 460 ms 50776 KB Output is correct
13 Correct 460 ms 50728 KB Output is correct
14 Correct 443 ms 50936 KB Output is correct
15 Correct 440 ms 50792 KB Output is correct
16 Correct 447 ms 50028 KB Output is correct
17 Correct 454 ms 50076 KB Output is correct
18 Correct 448 ms 50168 KB Output is correct
19 Correct 447 ms 50552 KB Output is correct
20 Correct 194 ms 46940 KB Output is correct
21 Correct 114 ms 45688 KB Output is correct
22 Correct 116 ms 47416 KB Output is correct
23 Correct 195 ms 47068 KB Output is correct
24 Correct 209 ms 47096 KB Output is correct
25 Correct 188 ms 46300 KB Output is correct
26 Correct 187 ms 46200 KB Output is correct
27 Correct 185 ms 46328 KB Output is correct
28 Correct 189 ms 46584 KB Output is correct
29 Correct 1323 ms 96884 KB Output is correct
30 Correct 1130 ms 93816 KB Output is correct
31 Correct 1078 ms 97936 KB Output is correct
32 Correct 1307 ms 96948 KB Output is correct
33 Correct 1300 ms 97368 KB Output is correct
34 Correct 1331 ms 96116 KB Output is correct
35 Correct 1278 ms 96212 KB Output is correct
36 Correct 1274 ms 96028 KB Output is correct
37 Correct 1277 ms 96504 KB Output is correct
38 Correct 946 ms 99164 KB Output is correct
39 Correct 897 ms 99124 KB Output is correct
40 Correct 867 ms 97200 KB Output is correct
41 Correct 862 ms 96880 KB Output is correct
42 Correct 868 ms 97020 KB Output is correct
43 Correct 890 ms 98040 KB Output is correct
44 Correct 973 ms 99340 KB Output is correct
45 Correct 961 ms 99448 KB Output is correct
46 Correct 945 ms 97680 KB Output is correct
47 Correct 956 ms 97192 KB Output is correct
48 Correct 960 ms 97280 KB Output is correct
49 Correct 957 ms 98424 KB Output is correct
50 Correct 1085 ms 99448 KB Output is correct
51 Correct 1085 ms 99576 KB Output is correct
52 Correct 1063 ms 98420 KB Output is correct
53 Correct 1065 ms 98088 KB Output is correct
54 Correct 1052 ms 98168 KB Output is correct
55 Correct 1062 ms 99152 KB Output is correct