oj.uz

Submission #923084

# Submission time Handle Problem Language Result Execution time Memory
923084 2024-02-06T14:45:00 Z phoenix0423 Triple Jump (JOI19_jumps) C++17
46 / 100
 245 ms 51588 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 = 2e5 + 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 344 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Correct 0 ms 344 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 344 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Correct 0 ms 344 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 30744 KB Output is correct
12 Correct 241 ms 30584 KB Output is correct
13 Correct 238 ms 30512 KB Output is correct
14 Correct 241 ms 30828 KB Output is correct
15 Correct 233 ms 30748 KB Output is correct
16 Correct 245 ms 30452 KB Output is correct
17 Correct 236 ms 29980 KB Output is correct
18 Correct 238 ms 29972 KB Output is correct
19 Correct 235 ms 30600 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 51588 KB Output is correct
2 Correct 129 ms 40268 KB Output is correct
3 Correct 128 ms 41880 KB Output is correct
4 Correct 185 ms 51524 KB Output is correct
5 Correct 178 ms 51528 KB Output is correct
6 Correct 182 ms 50756 KB Output is correct
7 Correct 182 ms 51012 KB Output is correct
8 Correct 176 ms 50760 KB Output is correct
9 Correct 180 ms 51016 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Correct 0 ms 344 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 30744 KB Output is correct
12 Correct 241 ms 30584 KB Output is correct
13 Correct 238 ms 30512 KB Output is correct
14 Correct 241 ms 30828 KB Output is correct
15 Correct 233 ms 30748 KB Output is correct
16 Correct 245 ms 30452 KB Output is correct
17 Correct 236 ms 29980 KB Output is correct
18 Correct 238 ms 29972 KB Output is correct
19 Correct 235 ms 30600 KB Output is correct
20 Correct 181 ms 51588 KB Output is correct
21 Correct 129 ms 40268 KB Output is correct
22 Correct 128 ms 41880 KB Output is correct
23 Correct 185 ms 51524 KB Output is correct
24 Correct 178 ms 51528 KB Output is correct
25 Correct 182 ms 50756 KB Output is correct
26 Correct 182 ms 51012 KB Output is correct
27 Correct 176 ms 50760 KB Output is correct
28 Correct 180 ms 51016 KB Output is correct
29 Runtime error 29 ms 51356 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -