Submission #1257852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257852		mactoddlover	Triple Jump (JOI19_jumps)	C++17	100 / 100	680 ms	94352 KiB

jumps

#include<bits/stdc++.h>

#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()
#define dbg(x) "[" #x " = " << (x) << "]"

using namespace std;

template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}

typedef long long ll;
typedef long double ld;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}

const int N = 5e5 + 15;

int n, q;
int a[N];
int L[N], R[N];

namespace subtask1{
    bool check(void){
        return n <= 100 && q <= 100;
    }

    void main(){
        for(int i = 1; i <= q; i++){
            int res = 0;
            for(int x = L[i]; x <= R[i]; x++){
                for(int y = x+1; y <= R[i]; y++){
                    for(int z = 2*y - x; z <= R[i]; z++){
                        int sum = a[x] + a[y] + a[z];
                        maximize(res, sum);
                    }
                }
            }
            cout << res << endl;
        }
    }
}

namespace subtask4{

    // j - i <= k - j
    // 2*j - i <= k

    vector<pii> candidates[N];
    void add(int i, int j){
        if(2*j - i <= n) candidates[i].emplace_back(2*j - i, a[i] + a[j]);
    }

    struct node{
        int best, one, two;
        node() : best(0), one(0), two(0) {}
        node(int best, int one, int two) : best(best), one(one), two(two) {}
        friend node operator + (const node& a, const node& b){
            node c;
            c.one = max(a.one, b.one);
            c.two = max(a.two, b.two);
            c.best = max({a.best, b.best, a.two + b.one});
            return c;
        }
    } st[N << 2];

    void update(int l, int r, int id, int pos, int v, int t){
        if(r < pos || l > pos) return;
        if(l == r){
            if(!t) maximize(st[id].one, v);
            else maximize(st[id].two, v);
            maximize(st[id].best, st[id].one + st[id].two);
            return;
        }
        else{
            int mid = (l+r) >> 1;
            if(pos <= mid) update(l, mid, id<<1, pos, v, t);
            else update(mid+1, r, id<<1|1, pos, v, t);
            st[id] = st[id<<1] + st[id<<1|1];
        }
    }

    node get(int l, int r, int id, int u, int v){
        if(r < u || l > v) return node();
        if(u <= l && r <= v) return st[id];
        int mid = (l+r) >> 1;
        return get(l, mid, id<<1, u, v) + get(mid+1, r, id<<1|1, u, v);
    }

    void upd(int pos, int v, int t){
        update(1, n, 1, pos, v, t);
    }

    int query(int l, int r){
        return get(1, n, 1, l, r).best;
    }

    vector<pii> qu[N];
    int ans[N];

    void main(){
        stack<int> stk;

        for(int i = 1; i <= n; i++){
            while(!stk.empty() && a[stk.top()] <= a[i]){
                add(stk.top(), i);
                stk.pop();
            }
            // nearest j which a[j] > a[i] match (a[j] + a[i])
            // since if a[l] > a[j] > a[i], opt for l will be j
            if(!stk.empty()) add(stk.top(), i);
            stk.push(i);
        }

        for(int i = 1; i <= q; i++){
            qu[L[i]].emplace_back(R[i], i);
        }

        for(int i = n; i >= 1; i--){
            for(auto e : candidates[i]){
                upd(e.fi, e.se, 1);
            }
            upd(i, a[i], 0);
            for(auto e : qu[i]){
                ans[e.se] = query(i, e.fi);
            }
        }

        for(int i = 1; i <= q; i++) cout << ans[i] << endl;
    }
}

void solve(){
    cin >> n;

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

    cin >> q;

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

    /*if(subtask1::check()) subtask1::main();
    else*/ subtask4::main();
}

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

    #define task "task"

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:166:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54