oj.uz

Submission #923086

# Submission time Handle Problem Language Result Execution time Memory
923086 2024-02-06T14:46:04 Z phoenix0423 Triple Jump (JOI19_jumps) C++17
100 / 100
 943 ms 153828 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define FOR(i, n) for(int i = 0; i < n; i++)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define int long long
const ll INF = 1e18;
const int maxn = 5e5 + 5;
int n;

struct info{
    int l, r, t, id;
    info(){}
    info(int _l, int _r, int _t, int _id) : l(_l), r(_r), t(_t), id(_id){}
    bool operator < (const info& other) const{
        if(l != other.l) return l < other.l;
        return t < other.t;
    }
    bool operator > (const info& other) const{
        if(l != other.l) return l > other.l;
        return t > other.t;
    }
};

struct node{
    int f, mx, ttl, tag;
};
node st[maxn * 4];
void cast(int v, int val){
    st[v].f = max(st[v].f, val);
    st[v].tag = max(st[v].tag, val);
    st[v].ttl = max(st[v].ttl, st[v].f + st[v].mx);
}
void push(int v){
    if(st[v].tag){
        cast(v * 2, st[v].tag);
        cast(v * 2 + 1, st[v].tag);
        st[v].tag = 0;
    }
}
void upd(int l, int r, pll val, int v = 1, int L = 0, int R = n - 1){
    if(l > R || r < L) return;
    if(l <= L && r >= R){
        st[v].f = max(st[v].f, val.f);
        st[v].mx = max(st[v].mx, val.s);
        st[v].tag = max(st[v].tag, val.f);
        st[v].ttl = max(st[v].ttl, st[v].f + st[v].mx);
        return;
    }
    push(v);
    int m = (L + R) / 2;
    upd(l, r, val, v * 2, L, m);
    upd(l, r, val, v * 2 + 1, m + 1, R);
    st[v].ttl = max(st[v * 2].ttl, st[v * 2 + 1].ttl);
    st[v].mx = max(st[v * 2].mx, st[v * 2 + 1].mx);
}

int qry(int l, int r, int v = 1, int L = 0, int R = n - 1){
    if(l > R || r < L) return 0;
    if(l <= L && r >= R) return st[v].ttl;
    push(v);
    int m = (L + R) / 2;
    return max(qry(l, r, v * 2, L, m), qry(l, r, v * 2 + 1, m + 1, R));
}
signed main(void){
    fastio;
    cin>>n;
    for(int i = 0; i < n * 4; i++) st[i].f = st[i].mx = st[i].ttl = -INF;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin>>a[i];
    int q;
    cin>>q;
    vector<pll> rng;
    stack<int> stk;
    stk.push(0);
    for(int i = 1; i < n; i++){
        while(!stk.empty() && a[stk.top()] <= a[i]){
            rng.eb(stk.top(), i);
            stk.pop();
        }
        if(!stk.empty()){
            rng.eb(stk.top(), i);
        }
        stk.push(i);
    }
    vector<info> event;
    for(auto [x, y] : rng){
        // cout<<"ok : "<<x<<" "<<y<<"\n";
        if(2 * y - x < n) event.pb(info(x, 2 * y - x, 1, a[x] + a[y]));
    }
    for(int i = 0; i < q; i++){
        int l, r;
        cin>>l>>r;
        l--, r--;
        event.pb(info(l, r, 0, i));
    }
    sort(event.begin(), event.end(), greater<info>());
    for(int i = 0; i < n; i++) upd(i, i, {-INF, a[i]});
    vector<int> ans(q);
    for(int i = 0; i < event.size(); i++){
        int t = event[i].l;
        while(i < event.size() && event[i].l == t){
            auto [l, r, t, id] = event[i];
            // cout<<"event : "<<l<<" "<<r<<" "<<t<<" "<<id<<"\n";
            i++;
            if(t) upd(r, n - 1, {id, -INF});
            else{
                ans[id] = qry(l, r);
                // cout<<"qry : "<<qry(l, r)<<"\n";
            }
        }
        i--;
    }
    for(auto x : ans) cout<<x<<"\n";
    cout<<"\n";
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:106:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i = 0; i < event.size(); i++){
      |                    ~~^~~~~~~~~~~~~~
jumps.cpp:108:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<info>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         while(i < event.size() && event[i].l == t){
      |               ~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 244 ms 29892 KB Output is correct
12 Correct 237 ms 29592 KB Output is correct
13 Correct 237 ms 29684 KB Output is correct
14 Correct 237 ms 29876 KB Output is correct
15 Correct 242 ms 29872 KB Output is correct
16 Correct 237 ms 29212 KB Output is correct
17 Correct 237 ms 29288 KB Output is correct
18 Correct 240 ms 29212 KB Output is correct
19 Correct 234 ms 29724 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 51272 KB Output is correct
2 Correct 130 ms 40008 KB Output is correct
3 Correct 129 ms 41612 KB Output is correct
4 Correct 179 ms 51268 KB Output is correct
5 Correct 179 ms 51272 KB Output is correct
6 Correct 177 ms 50760 KB Output is correct
7 Correct 177 ms 50896 KB Output is correct
8 Correct 176 ms 50760 KB Output is correct
9 Correct 188 ms 51272 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 464 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 244 ms 29892 KB Output is correct
12 Correct 237 ms 29592 KB Output is correct
13 Correct 237 ms 29684 KB Output is correct
14 Correct 237 ms 29876 KB Output is correct
15 Correct 242 ms 29872 KB Output is correct
16 Correct 237 ms 29212 KB Output is correct
17 Correct 237 ms 29288 KB Output is correct
18 Correct 240 ms 29212 KB Output is correct
19 Correct 234 ms 29724 KB Output is correct
20 Correct 180 ms 51272 KB Output is correct
21 Correct 130 ms 40008 KB Output is correct
22 Correct 129 ms 41612 KB Output is correct
23 Correct 179 ms 51268 KB Output is correct
24 Correct 179 ms 51272 KB Output is correct
25 Correct 177 ms 50760 KB Output is correct
26 Correct 177 ms 50896 KB Output is correct
27 Correct 176 ms 50760 KB Output is correct
28 Correct 188 ms 51272 KB Output is correct
29 Correct 935 ms 153572 KB Output is correct
30 Correct 744 ms 126088 KB Output is correct
31 Correct 739 ms 130068 KB Output is correct
32 Correct 930 ms 153572 KB Output is correct
33 Correct 937 ms 153572 KB Output is correct
34 Correct 920 ms 151860 KB Output is correct
35 Correct 921 ms 151528 KB Output is correct
36 Correct 915 ms 151536 KB Output is correct
37 Correct 943 ms 152372 KB Output is correct
38 Correct 757 ms 153320 KB Output is correct
39 Correct 741 ms 153828 KB Output is correct
40 Correct 733 ms 152280 KB Output is correct
41 Correct 734 ms 151712 KB Output is correct
42 Correct 734 ms 151536 KB Output is correct
43 Correct 741 ms 152480 KB Output is correct
44 Correct 779 ms 153512 KB Output is correct
45 Correct 785 ms 153752 KB Output is correct
46 Correct 761 ms 151756 KB Output is correct
47 Correct 762 ms 151480 KB Output is correct
48 Correct 784 ms 151548 KB Output is correct
49 Correct 752 ms 152308 KB Output is correct
50 Correct 828 ms 153448 KB Output is correct
51 Correct 812 ms 153400 KB Output is correct
52 Correct 801 ms 151768 KB Output is correct
53 Correct 816 ms 151508 KB Output is correct
54 Correct 817 ms 151524 KB Output is correct
55 Correct 806 ms 152496 KB Output is correct