oj.uz

Submission #198185

# Submission time Handle Problem Language Result Execution time Memory
198185 2020-01-25T03:57:40 Z HungAnhGoldIBO2020 Triple Jump (JOI19_jumps) C++14
100 / 100
 1348 ms 87900 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+2;
const int inf=1e9+7;
int ar[N],ans[N];
struct node{
	int lef=-inf,rig=-inf,ans=-inf;
} it[4*N];
vector<pair<int,int> > lis,query[N];
vector<int> upd_lis[N];
void get(int idx,int l,int r){
	it[idx].lef=max(it[2*idx].lef,it[2*idx+1].lef);
	it[idx].rig=max(it[2*idx].rig,it[2*idx+1].rig);
	it[idx].ans=max(it[2*idx].ans,max(it[2*idx+1].ans,it[2*idx].lef+it[2*idx+1].rig));
}
node merge(node a,node b){
	node ans;
	ans.lef=max(a.lef,b.lef);
	ans.rig=max(a.rig,b.rig);
	ans.ans=max(a.ans,max(b.ans,a.lef+b.rig));
	return ans;
}
void init(int idx,int l,int r){
	if(l==r){
		it[idx].rig=ar[l];
		return;
	}
	init(2*idx,l,(l+r)/2);
	init(2*idx+1,(l+r)/2+1,r);
	get(idx,l,r);
}
void upd(int idx,int l,int r,int pos,int val){
	if(l>pos||r<pos){
		return;
	}
	if(l==r){
		it[idx].lef=max(it[idx].lef,val);
		it[idx].ans=max(it[idx].ans,it[idx].lef+it[idx].rig);
		return;
	}
	upd(2*idx,l,(l+r)/2,pos,val);
	upd(2*idx+1,(l+r)/2+1,r,pos,val);
	get(idx,l,r);
}
node getmax(int idx,int l,int r,int lef,int rig){
	if(l>rig||r<lef){
		return node();
	}
	if(l>=lef&&r<=rig){
		return it[idx];
	}
	return merge(getmax(2*idx,l,(l+r)/2,lef,rig),getmax(2*idx+1,(l+r)/2+1,r,lef,rig));
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l,q;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>ar[i];
		while(lis.size()){
			upd_lis[lis.back().second].push_back(i);
			if(lis.back().first>ar[i]){
				break;
			}
			else{
				lis.pop_back();
			}
		}
		lis.push_back({ar[i],i});
	}
	init(1,1,n);
	cin>>q;
	for(i=1;i<=q;i++){
		cin>>j>>k;
		query[j].push_back({k,i});
	}
	for(i=n;i>0;i--){
		for(j=0;j<upd_lis[i].size();j++){
			if(2*upd_lis[i][j]-i>n){
				continue;
			}
			upd(1,1,n,2*upd_lis[i][j]-i,ar[i]+ar[upd_lis[i][j]]);
		}
		for(j=0;j<query[i].size();j++){
			node wow=getmax(1,1,n,i,query[i][j].first);
			ans[query[i][j].second]=wow.ans;
		}
	}
	for(i=1;i<=q;i++){
		cout<<ans[i]<<'\n';
	}
}
/*
5
5 2 1 5 3
3
1 4
2 5
1 5
*/

Compilation message

jumps.cpp: In function 'int main()':
jumps.cpp:79:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<upd_lis[i].size();j++){
           ~^~~~~~~~~~~~~~~~~~
jumps.cpp:85:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<query[i].size();j++){
           ~^~~~~~~~~~~~~~~~
jumps.cpp:57:14: warning: unused variable 'l' [-Wunused-variable]
  int n,i,j,k,l,q;
              ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23804 KB Output is correct
2 Correct 24 ms 23804 KB Output is correct
3 Correct 24 ms 23800 KB Output is correct
4 Correct 24 ms 23800 KB Output is correct
5 Correct 25 ms 23800 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 25 ms 23800 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 25 ms 24056 KB Output is correct
10 Correct 25 ms 23928 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23804 KB Output is correct
2 Correct 24 ms 23804 KB Output is correct
3 Correct 24 ms 23800 KB Output is correct
4 Correct 24 ms 23800 KB Output is correct
5 Correct 25 ms 23800 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 25 ms 23800 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 25 ms 24056 KB Output is correct
10 Correct 25 ms 23928 KB Output is correct
11 Correct 481 ms 42232 KB Output is correct
12 Correct 484 ms 42232 KB Output is correct
13 Correct 469 ms 42428 KB Output is correct
14 Correct 466 ms 42268 KB Output is correct
15 Correct 472 ms 42352 KB Output is correct
16 Correct 473 ms 41672 KB Output is correct
17 Correct 469 ms 41592 KB Output is correct
18 Correct 476 ms 41544 KB Output is correct
19 Correct 460 ms 42232 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 39032 KB Output is correct
2 Correct 120 ms 38828 KB Output is correct
3 Correct 122 ms 40292 KB Output is correct
4 Correct 209 ms 39048 KB Output is correct
5 Correct 196 ms 39004 KB Output is correct
6 Correct 186 ms 38264 KB Output is correct
7 Correct 183 ms 38392 KB Output is correct
8 Correct 184 ms 38264 KB Output is correct
9 Correct 185 ms 38776 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23804 KB Output is correct
2 Correct 24 ms 23804 KB Output is correct
3 Correct 24 ms 23800 KB Output is correct
4 Correct 24 ms 23800 KB Output is correct
5 Correct 25 ms 23800 KB Output is correct
6 Correct 24 ms 23800 KB Output is correct
7 Correct 25 ms 23800 KB Output is correct
8 Correct 24 ms 23800 KB Output is correct
9 Correct 25 ms 24056 KB Output is correct
10 Correct 25 ms 23928 KB Output is correct
11 Correct 481 ms 42232 KB Output is correct
12 Correct 484 ms 42232 KB Output is correct
13 Correct 469 ms 42428 KB Output is correct
14 Correct 466 ms 42268 KB Output is correct
15 Correct 472 ms 42352 KB Output is correct
16 Correct 473 ms 41672 KB Output is correct
17 Correct 469 ms 41592 KB Output is correct
18 Correct 476 ms 41544 KB Output is correct
19 Correct 460 ms 42232 KB Output is correct
20 Correct 190 ms 39032 KB Output is correct
21 Correct 120 ms 38828 KB Output is correct
22 Correct 122 ms 40292 KB Output is correct
23 Correct 209 ms 39048 KB Output is correct
24 Correct 196 ms 39004 KB Output is correct
25 Correct 186 ms 38264 KB Output is correct
26 Correct 183 ms 38392 KB Output is correct
27 Correct 184 ms 38264 KB Output is correct
28 Correct 185 ms 38776 KB Output is correct
29 Correct 1343 ms 82216 KB Output is correct
30 Correct 1144 ms 81656 KB Output is correct
31 Correct 1141 ms 85516 KB Output is correct
32 Correct 1341 ms 82196 KB Output is correct
33 Correct 1348 ms 82164 KB Output is correct
34 Correct 1322 ms 79896 KB Output is correct
35 Correct 1317 ms 79748 KB Output is correct
36 Correct 1323 ms 79608 KB Output is correct
37 Correct 1317 ms 81124 KB Output is correct
38 Correct 958 ms 87900 KB Output is correct
39 Correct 949 ms 87800 KB Output is correct
40 Correct 930 ms 84572 KB Output is correct
41 Correct 922 ms 84064 KB Output is correct
42 Correct 927 ms 84108 KB Output is correct
43 Correct 927 ms 85756 KB Output is correct
44 Correct 1022 ms 87288 KB Output is correct
45 Correct 1031 ms 87260 KB Output is correct
46 Correct 1000 ms 84260 KB Output is correct
47 Correct 1002 ms 83800 KB Output is correct
48 Correct 1008 ms 83744 KB Output is correct
49 Correct 1008 ms 85880 KB Output is correct
50 Correct 1117 ms 85564 KB Output is correct
51 Correct 1129 ms 84904 KB Output is correct
52 Correct 1140 ms 83048 KB Output is correct
53 Correct 1094 ms 82704 KB Output is correct
54 Correct 1102 ms 82824 KB Output is correct
55 Correct 1142 ms 84344 KB Output is correct