Submission #260668

#	Time	Username	Problem	Language	Result	Execution time	Memory
260668		limabeans	Triple Jump (JOI19_jumps)	C++17	19 / 100	4097 ms	46416 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


template<typename T> struct segtree {
    
    T merge(T x, T y) {
	return max(x, y);
    }
    int n;
    vector<ll> t;
    void init(int n) {
	n += 10;
	this->n = n;
	t.resize(n*4);
    }

    void upd(int v, int tl, int tr, int i, T dx) {
	if (tl == tr) {
	    t[v] = merge(t[v], dx);
	} else {
	    int tm = (tl+tr)/2;
	    if (i<=tm) {
		upd(2*v,tl,tm,i,dx);
	    } else {
		upd(2*v+1,tm+1,tr,i,dx);
	    }
	    t[v] = merge(t[2*v], t[2*v+1]);
	}
    }

    T qry(int v, int tl, int tr, int l, int r) {
	if (l>tr || r<tl) {
	    return 0;
	}
	if (l <= tl && tr <= r) {
	    return t[v];
	}
	int tm = (tl+tr)/2;
	return merge(qry(2*v,tl,tm,l,r), qry(2*v+1,tm+1,tr,l,r));
    }
};

struct sparse_table {
    //0-indexed, init with vector.

    //todo: call init()
    const static int LOG = 18; //todo
    int n;
    vector<int> a[LOG+1];
    vector<int> lg_floor;

    //todo
    int eval(int x, int y) {
	return max(x, y);
    }

    //todo: ll vs int
    void init(vector<int> v) {
	n = v.size();
	lg_floor.resize(n+10);
	lg_floor[1] = 0;
	for (int i=2; i<n+10; i++) lg_floor[i] = 1 + lg_floor[i/2];
	for (int j=0; j<LOG; j++) a[j].resize(n);
	for (int i=0; i<n; i++) a[0][i] = v[i];
	

	for (int j=1; j<LOG; j++) {
	    for (int i=0; i<n; i++) {
		a[j][i] = a[j-1][i];
		if (i + (1<<(j-1)) < n) {
		    a[j][i] = eval(a[j][i], a[j-1][i + (1<<(j-1))]);
		}
	    }
	}
    }

    int get(int l, int r) {
	assert(l<=r);
	int lg = lg_floor[r - l + 1];

	return eval(a[lg][l], a[lg][r-(1<<lg)+1]);
	
    }
};


const ll mod = 1e9+7;
const int maxn = 1e6 + 5;


int n, q;
int A[maxn];
vector<pair<int,int>> Q;
int ans[maxn];
vector<int> ev[maxn];

sparse_table st;
segtree<int> sg;

void init_st() {
    vector<int> a;
    for (int i=1; i<=n; i++) {
	a.push_back(A[i]);
    }
    st.init(a);
}

int qryMax(int l, int r) {
    assert(l<=r);
    return st.get(l-1,r-1);
}

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

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

    init_st();
    sg.init(n+10);
    
    cin>>q;
    Q.resize(q);
    for (int i=0; i<q; i++) {
	cin>>Q[i].first>>Q[i].second;
	ev[Q[i].second].push_back(i);
    }



    

    for (int r=3; r<=n; r++) {
	for (int l=1; l<=r-2; l++) {
	    int mid = (l+r)/2;
	    int mx = qryMax(l+1,mid);
	    sg.upd(1,1,n,l,mx+A[l]+A[r]);
	}
	for (int idx: ev[r]) {
	    int L = Q[idx].first; int R = Q[idx].second;
	    ans[idx] = max(ans[idx], sg.qry(1,1,n,L,R));
	}
    }


    for (int i=0; i<q; i++) {
	cout<<ans[i]<<"\n";
    }
    
    
    return 0;
}

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