oj.uz

답안 #260752

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260752 2020-08-10T20:28:11 Z limabeans 3단 점프 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -