oj.uz

Submission #163609

# Submission time Handle Problem Language Result Execution time Memory
163609 2019-11-14T10:20:14 Z combi1k1 Triple Jump (JOI19_jumps) C++14
32 / 100
 342 ms 80936 KB 
#include<bits/stdc++.h>

using namespace std;

#define FOR(i,a,b)  for(int i = a ; i <= b ; ++i)

#define X   first
#define Y   second

#define pb  push_back
#define ll  long long

#define lch     i << 1
#define rch     i << 1 | 1

#define Unit    Node(-2e9,-2e9,-3e9)

const int   N   = 2e5 + 1;

typedef pair<int,int>   ii;

struct Node {
    ll  L, R, S;

    Node(ll l = 0,ll r = 0,ll s = 0) : L(l), R(r), S(s) {}
}   tr[N << 2];

Node Spare;

Node operator + (const Node &a,const Node &b)   {
    ll x = max(a.L,b.L);
    ll y = max(a.R,b.R);
    ll z = max(a.S,b.S);

    return  Node(x,y,max(z,a.L + b.R));
}

void upd(int i,int l,int r,int p,int v,int t)   {
    if (l > p)  return;
    if (r < p)  return;
    if (l == r) {
        if (t)  tr[i].R = max(tr[i].R,(ll)v);
        else    tr[i].L = max(tr[i].L,(ll)v);

        tr[i].S = tr[i].L + tr[i].R;

        return;
    }
    int m = (l + r) / 2;

    upd(lch,l,m,p,v,t); ++m;
    upd(rch,m,r,p,v,t);

    tr[i] = tr[lch] + tr[rch];
}
void get(int i,int l,int r,int L,int R) {
    if (l > R)  return;
    if (L > r)  return;
    if (L <= l && r <= R)   {
        Spare = Spare + tr[i];
        return;
    }

    int m = (l + r) / 2;

    get(lch,l,m,L,R);   ++m;
    get(rch,m,r,L,R);
}

vector<ii>  Que[N];
vector<ii>  Seg[N];

int a[N];
int t[N];
int tot = 0;

ll  ans[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;

    fill(tr + 1,tr + 4 * n,Unit);

    auto add = [&](int x,int y) {
        if (y + y <= n + x)
            Seg[x].pb(ii(y + y - x,a[x] + a[y]));
    };
    auto ask = [&](int l,int r) {
        Spare = Unit;
        get(1,1,n,l,r);

        return  Spare.S;
    };

    FOR(i,1,n)  {
        cin >> a[i];
        for(; tot && a[t[tot]] < a[i] ; --tot)
            add(t[tot],i);
        if (tot)
            add(t[tot],i);

        t[++tot] = i;
    }

    int q;  cin >> q;

    FOR(i,1,q)  {
        int l;  cin >> l;
        int r;  cin >> r;

        Que[l].push_back(ii(r,i));
    }

    for(int i = n ; i >= 1 ; --i)   {
        upd(1,1,n,i,a[i],1);

        for(ii  e : Seg[i])
            upd(1,1,n,e.X,e.Y,0);
        for(ii  e : Que[i])
            ans[e.Y] = ask(i,e.X);
    }

    FOR(i,1,q)  cout << ans[i] << "\n";
}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28452 KB Output is correct
2 Correct 26 ms 28536 KB Output is correct
3 Correct 28 ms 28536 KB Output is correct
4 Correct 29 ms 28536 KB Output is correct
5 Correct 29 ms 28536 KB Output is correct
6 Correct 28 ms 28536 KB Output is correct
7 Correct 28 ms 28664 KB Output is correct
8 Correct 26 ms 28536 KB Output is correct
9 Correct 28 ms 28536 KB Output is correct
10 Correct 30 ms 28508 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28452 KB Output is correct
2 Correct 26 ms 28536 KB Output is correct
3 Correct 28 ms 28536 KB Output is correct
4 Correct 29 ms 28536 KB Output is correct
5 Correct 29 ms 28536 KB Output is correct
6 Correct 28 ms 28536 KB Output is correct
7 Correct 28 ms 28664 KB Output is correct
8 Correct 26 ms 28536 KB Output is correct
9 Correct 28 ms 28536 KB Output is correct
10 Correct 30 ms 28508 KB Output is correct
11 Runtime error 219 ms 80936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 38616 KB Output is correct
2 Correct 240 ms 37368 KB Output is correct
3 Correct 234 ms 38264 KB Output is correct
4 Correct 342 ms 38648 KB Output is correct
5 Correct 338 ms 38548 KB Output is correct
6 Correct 335 ms 37880 KB Output is correct
7 Correct 332 ms 37752 KB Output is correct
8 Correct 329 ms 37752 KB Output is correct
9 Correct 332 ms 38264 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28452 KB Output is correct
2 Correct 26 ms 28536 KB Output is correct
3 Correct 28 ms 28536 KB Output is correct
4 Correct 29 ms 28536 KB Output is correct
5 Correct 29 ms 28536 KB Output is correct
6 Correct 28 ms 28536 KB Output is correct
7 Correct 28 ms 28664 KB Output is correct
8 Correct 26 ms 28536 KB Output is correct
9 Correct 28 ms 28536 KB Output is correct
10 Correct 30 ms 28508 KB Output is correct
11 Runtime error 219 ms 80936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Halted 0 ms 0 KB -