oj.uz

Submission #147253

# Submission time Handle Problem Language Result Execution time Memory
147253 2019-08-28T13:59:56 Z Alexa2001 Triple Jump (JOI19_jumps) C++17
19 / 100
 4000 ms 19560 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 5e5 + 5;
const int inf = 1e9;

vector<pair<int,int>> v;
int a[Nmax], st[Nmax];
int n, L[Nmax], R[Nmax];
int Ans[Nmax];

void fnd()
{
    int i, nr = 0;

    st[0] = 0;
    a[0] = inf;

    for(i=1; i<=n; ++i)
    {
        while(a[st[nr]] <= a[i])
        {
            v.push_back({st[nr], i});
            --nr;
        }

        v.push_back({st[nr], i});
        st[++nr] = i;
    }
}

int best(int x, int y)
{
    int i; int ans = 0;
    for(i=x; i<=y; ++i) ans = max(ans, a[i]);
    return ans;
}

void solv(int R, vector<int> &queries)
{
    int i; 
    vector<int> best(R+2);

    best[R+1] = -1e9;
    for(i=R; i; --i) best[i] = max(best[i+1], a[i]);
   
    vector<int> coef(v.size());

    for(i=0; i<v.size(); ++i)
        coef[i] = a[v[i].first] + a[v[i].second] + best[ min(R+1, 2 * v[i].second - v[i].first)  ];
    
    int j = v.size() - 1;
    int now = 0;

    vector<int> wow(R+2);

    for(i=R; i; --i)
    {
        while(j>=0 && v[j].first >= i) now = max(now, coef[j]), --j;
        wow[i] = now;
    }

    for(auto it : queries)
        Ans[it] = wow[L[it]];
}

int main()
{
  //  freopen("triple.in", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);
    
    cin >> n;

    int i, q;
    for(i=1; i<=n; ++i) cin >> a[i];

    cin >> q;
    for(i=1; i<=q; ++i) cin >> L[i] >> R[i];

    fnd();
    
    vector<vector<int>> endp(n+1);

    sort(v.begin(), v.end());

    for(i=1; i<=q; ++i)
        endp[R[i]].push_back(i);
    
    for(i=1; i<=n; ++i)
        solv(i, endp[i]);
    
    for(i=1; i<=q; ++i) cout << Ans[i] << '\n';
    return 0;
}

Compilation message

jumps.cpp: In function 'void solv(int, std::vector<int>&)':
jumps.cpp:50:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v.size(); ++i)
              ~^~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 469 ms 19560 KB Output is correct
12 Correct 363 ms 19420 KB Output is correct
13 Correct 320 ms 19384 KB Output is correct
14 Correct 471 ms 19448 KB Output is correct
15 Correct 468 ms 19448 KB Output is correct
16 Correct 485 ms 18940 KB Output is correct
17 Correct 472 ms 18904 KB Output is correct
18 Correct 470 ms 18808 KB Output is correct
19 Correct 473 ms 19488 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4069 ms 12480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 469 ms 19560 KB Output is correct
12 Correct 363 ms 19420 KB Output is correct
13 Correct 320 ms 19384 KB Output is correct
14 Correct 471 ms 19448 KB Output is correct
15 Correct 468 ms 19448 KB Output is correct
16 Correct 485 ms 18940 KB Output is correct
17 Correct 472 ms 18904 KB Output is correct
18 Correct 470 ms 18808 KB Output is correct
19 Correct 473 ms 19488 KB Output is correct
20 Execution timed out 4069 ms 12480 KB Time limit exceeded
21 Halted 0 ms 0 KB -