oj.uz

Submission #260668

# Submission time Handle Problem Language Result Execution time Memory
260668 2020-08-10T17:06:18 Z limabeans Triple Jump (JOI19_jumps) C++17
19 / 100
 4000 ms 46416 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Correct 20 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 20 ms 23808 KB Output is correct
5 Correct 17 ms 23808 KB Output is correct
6 Correct 20 ms 23808 KB Output is correct
7 Correct 17 ms 23808 KB Output is correct
8 Correct 20 ms 23808 KB Output is correct
9 Correct 17 ms 23808 KB Output is correct
10 Correct 17 ms 23936 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Correct 20 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 20 ms 23808 KB Output is correct
5 Correct 17 ms 23808 KB Output is correct
6 Correct 20 ms 23808 KB Output is correct
7 Correct 17 ms 23808 KB Output is correct
8 Correct 20 ms 23808 KB Output is correct
9 Correct 17 ms 23808 KB Output is correct
10 Correct 17 ms 23936 KB Output is correct
11 Correct 1384 ms 39084 KB Output is correct
12 Correct 1362 ms 43136 KB Output is correct
13 Correct 1348 ms 43256 KB Output is correct
14 Correct 1357 ms 43388 KB Output is correct
15 Correct 1378 ms 43384 KB Output is correct
16 Correct 1389 ms 42744 KB Output is correct
17 Correct 1361 ms 42632 KB Output is correct
18 Correct 1369 ms 42616 KB Output is correct
19 Correct 1362 ms 43164 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4097 ms 46416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23808 KB Output is correct
2 Correct 20 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 20 ms 23808 KB Output is correct
5 Correct 17 ms 23808 KB Output is correct
6 Correct 20 ms 23808 KB Output is correct
7 Correct 17 ms 23808 KB Output is correct
8 Correct 20 ms 23808 KB Output is correct
9 Correct 17 ms 23808 KB Output is correct
10 Correct 17 ms 23936 KB Output is correct
11 Correct 1384 ms 39084 KB Output is correct
12 Correct 1362 ms 43136 KB Output is correct
13 Correct 1348 ms 43256 KB Output is correct
14 Correct 1357 ms 43388 KB Output is correct
15 Correct 1378 ms 43384 KB Output is correct
16 Correct 1389 ms 42744 KB Output is correct
17 Correct 1361 ms 42632 KB Output is correct
18 Correct 1369 ms 42616 KB Output is correct
19 Correct 1362 ms 43164 KB Output is correct
20 Execution timed out 4097 ms 46416 KB Time limit exceeded
21 Halted 0 ms 0 KB -