oj.uz

Submission #684862

# Submission time Handle Problem Language Result Execution time Memory
684862 2023-01-22T17:33:21 Z ziduo Triple Jump (JOI19_jumps) C++14
27 / 100
 150 ms 41996 KB 
/******************************************************************************

Welcome to GDB Online.
GDB online is an online compiler and debugger tool for C, C++, Python, PHP, Ruby, 
C#, OCaml, VB, Perl, Swift, Prolog, Javascript, Pascal, HTML, CSS, JS
Code, Compile, Run and Debug online from anywhere in world.

*******************************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define maxn 500000

int seg[4*maxn], lz[4*maxn], ma[4*maxn], arr[maxn];
void pushup(int x){
         int s1 = 2*x, s2 = 2*x+1;
        seg[x] = max(seg[x], lz[x]+ma[x]);
        lz[s1]=max(lz[s1], lz[x]);
        lz[s2]=max(lz[s2], lz[x]);
        lz[x] = 0;
        seg[x] = max(max(seg[x],seg[s1]), seg[s2]);
        
}
void update(int x, int l, int r, int a, int b, int v){
    if(a<=l&&b>=r){
        lz[x] = max(lz[x],v);
        pushup(x);
    }
    else{
        int s1 = 2*x, s2 = 2*x+1;
        int m = (l+r)/2;
        if(a<=m)update(s1, l, m, a, min(b, m), v);
        if(b>m)update(s2, m+1, r, max(m+1, a), b, v);
        pushup(x);
        
    }
}
int query(int x, int l, int r, int a, int b){
    if(a<=l&&b>=r){
        pushup(x);
        return seg[x];
    }
    else{
        int s1 = 2*x, s2 = 2*x+1;
        int m = (l+r)/2;
        int ret = 0;
        if(a<=m)ret = max(query(s1, l, m, a, min(b, m)),ret);
        if(b>m)ret = max(query(s2, m+1, r, max(m+1, a), b),ret);
        pushup(x);
        return ret;
    }    
}
void setUp(int x, int l, int r) {
    if(l==r){ma[x] = arr[l];
    return;
    }
    setUp(2*x, l, (l+r)/2);
    setUp(2*x+1, ((l+r)/2)+1, r);
    ma[x] = max(ma[2*x], ma[2*x+1]);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin>>n;
    vector<vector<int>> pairs;
    for(int i=0; i<n; i++)cin>>arr[i];
    deque<int> vals;
    deque<int> pos;
    for(int i=0; i<n; i++){
        vector<int> t; pairs.push_back(t);
        while(vals.size()&&vals.back()<arr[i]){
            vals.pop_back();
            pos.pop_back();
        }
        if(vals.size())
            pairs[pos.back()].push_back(i);
        vals.push_back(arr[i]);
        pos.push_back(i);
    }
    vals.clear(); pos.clear();
    for(int i=n-1; i>-1; i--){
        while(vals.size()&&vals.back()<arr[i]){
            vals.pop_back();
            pos.pop_back();
        }
        if(vals.size())
            pairs[i].push_back(pos.back());
            
        vals.push_back(arr[i]);
        pos.push_back(i);
    }    
    int q; cin>>q;
    vector<vector<int>> queries;
    for(int i=0; i<n; i++){
        vector<int>v;
        queries.push_back(v);
    }
    int answers[q];
    for(int i=0; i<q; i++){
        int l, r; cin>>l>>r;l--;r--;
        queries[l].push_back(r);
        queries[l].push_back(i);
    }
    for(int i=0; i<4*maxn; i++){
        lz[i] = 0;
        seg[i] = 0;
        ma[i]=0;
    }
    setUp(1, 0, n-1);
    for(int i=n-1; i>-1; i--){
        for(int p: pairs[i]){
            if(p+p-i<n){
                update(1, 0, n-1, p+p-i, n-1, arr[i]+arr[p]);
                //for(int i=1; i<=30; i++)cout<<seg[i]<<" ";
                //cout<<'\n';
            }
        }
        for(int j=0; j<queries[i].size(); j+=2){
            answers[queries[i][j+1]] = query(1, 0, n-1, i, queries[i][j]);
        }
        
    }
    for(int value: answers)cout<<value<<'\n';
    return 0;
}

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |         for(int j=0; j<queries[i].size(); j+=2){
      |                      ~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23764 KB Output is correct
2 Incorrect 9 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23764 KB Output is correct
2 Incorrect 9 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 40600 KB Output is correct
2 Correct 89 ms 41996 KB Output is correct
3 Correct 95 ms 41980 KB Output is correct
4 Correct 150 ms 40568 KB Output is correct
5 Correct 146 ms 40596 KB Output is correct
6 Correct 136 ms 41656 KB Output is correct
7 Correct 135 ms 41532 KB Output is correct
8 Correct 137 ms 41684 KB Output is correct
9 Correct 137 ms 41920 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 23764 KB Output is correct
2 Incorrect 9 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -