oj.uz

Submission #260752

# Submission time Handle Problem Language Result Execution time Memory
260752 2020-08-10T20:28:11 Z limabeans Triple Jump (JOI19_jumps) C++17
19 / 100
 1174 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=max(t[v].ab, val);
	    } else {
		t[v].c=max(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
5.0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 17 ms 23808 KB Output is correct
5 Correct 16 ms 23900 KB Output is correct
6 Correct 16 ms 23808 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 17 ms 23908 KB Output is correct
9 Correct 16 ms 23936 KB Output is correct
10 Correct 17 ms 23808 KB Output is correct
11 Correct 1120 ms 103564 KB Output is correct
12 Correct 1120 ms 103544 KB Output is correct
13 Correct 1119 ms 103468 KB Output is correct
14 Correct 1131 ms 103544 KB Output is correct
15 Correct 1174 ms 103544 KB Output is correct
16 Correct 1137 ms 102776 KB Output is correct
17 Correct 1134 ms 102776 KB Output is correct
18 Correct 1123 ms 102808 KB Output is correct
19 Correct 1116 ms 103544 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 967 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 16 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 17 ms 23808 KB Output is correct
4 Correct 17 ms 23808 KB Output is correct
5 Correct 16 ms 23900 KB Output is correct
6 Correct 16 ms 23808 KB Output is correct
7 Correct 16 ms 23808 KB Output is correct
8 Correct 17 ms 23908 KB Output is correct
9 Correct 16 ms 23936 KB Output is correct
10 Correct 17 ms 23808 KB Output is correct
11 Correct 1120 ms 103564 KB Output is correct
12 Correct 1120 ms 103544 KB Output is correct
13 Correct 1119 ms 103468 KB Output is correct
14 Correct 1131 ms 103544 KB Output is correct
15 Correct 1174 ms 103544 KB Output is correct
16 Correct 1137 ms 102776 KB Output is correct
17 Correct 1134 ms 102776 KB Output is correct
18 Correct 1123 ms 102808 KB Output is correct
19 Correct 1116 ms 103544 KB Output is correct
20 Runtime error 967 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Halted 0 ms 0 KB -