oj.uz

Submission #260750

# Submission time Handle Problem Language Result Execution time Memory
260750 2020-08-10T20:24:20 Z limabeans Triple Jump (JOI19_jumps) C++17
0 / 100
 1031 ms 524288 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





const int inf = 1e9;

struct node {
    int ab,c,abc;
    node() {
	ab=c=abc=-inf;
    }
    node(int _ab, int _c, int _abc) : ab(_ab), c(_c), abc(_abc) {}
};

struct segtree {
    node merge(node x, node y) {
	return { max(x.ab,y.ab), max(x.c,y.c), max({x.abc,y.abc,x.ab+y.c}) };
	return x;
    }
    int n;
    vector<node> t;
    void init(int n) {
	n += 10;
	this->n = n;
	t.resize(n*4);
    }

    void upd(int v, int tl, int tr, int i, int val, int stat) {
	if (tl == tr) {
	    if (stat==0) {
		t[v].ab=val;
	    } else {
		t[v].c=val;
	    }
	    t[v].abc = max(t[v].abc, t[v].ab + t[v].c);
	} else {
	    int tm = (tl+tr)/2;
	    if (i<=tm) {
		upd(2*v,tl,tm,i,val,stat);
	    } else {
		upd(2*v+1,tm+1,tr,i,val,stat);
	    }
	    t[v] = merge(t[2*v], t[2*v+1]);
	}
    }

    node qry(int v, int tl, int tr, int l, int r) {
	if (l>tr || r<tl) {
	    return node();
	}
	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));
    }
};

const int maxn = 5e5+10;



int n;
int A[maxn];
vector<int> B[maxn];

int q;
int ans[maxn];
vector<pair<int,int>> Q[maxn]; //(r,i)
segtree tree;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n;
    tree.init(n+10);
    
    for (int i=1; i<=n; i++) {
	cin>>A[i];
	tree.upd(1,1,n,i,A[i],1);
    }
    

    cin>>q;
    for (int i=0; i<q; i++) {
	int l,r;
	cin>>l>>r;
	Q[l].push_back({r,i});
    }

    for (int i=1; i<=n; i++) {
	for (int j=i+1; j<=n; j++) {
	    B[i].push_back(j);
	}
    }

    for (int a=n; a>=1; a--) {
	for (int b: B[a]) {
	    int c = b+(b-a);
	    if (c <= n) {
		tree.upd(1,1,n,c,A[a]+A[b],0);
	    }
	}
	for (auto qq: Q[a]) {
	    int idx = qq.second;
	    int r = qq.first;

	    ans[idx] = tree.qry(1,1,n,a,r).abc;
	}
    }

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 1031 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

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