oj.uz

Submission #329841

# Submission time Handle Problem Language Result Execution time Memory
329841 2020-11-22T20:27:46 Z GioChkhaidze Triple Jump (JOI19_jumps) C++14
100 / 100
 1321 ms 90500 KB 
#include <bits/stdc++.h>

#define Tree int h,int l,int r
#define Left (h<<1),l,(l+r)>>1
#define Right ((h<<1)|1),((l+r)>>1)+1,r
#define F first
#define S second

using namespace std;

const int N=5e5+5;

int n,q;
int a[N],ans[N];
deque < int > dq;
vector < pair < int , int > > Q[N],E[N];

typedef struct { int li; int r; int ans; } node;

node v[4*N];

void B(int h) {
	v[h].ans=max(v[h].ans,v[h].li+v[h].r);
	return ;
}

void Shift(Tree) {
	v[(h<<1)].li=max(v[(h<<1)].li,v[h].li);
	v[((h<<1)|1)].li=max(v[((h<<1)|1)].li,v[h].li);
	B((h<<1)),B(((h<<1)|1));
}

void Upd(Tree,int L,int R,int vl) {
	if (r<L || R<l) return ;
	if (L<=l && r<=R) {
		v[h].li=max(v[h].li,vl);
		B(h);
		return ;
	}
	
	Shift(h,l,r);
	Upd(Left,L,R,vl);
	Upd(Right,L,R,vl);
	v[h].ans=max(v[(h<<1)].ans,v[((h<<1)|1)].ans);
}

int L,R;
int get(Tree) {
	if (r<L || R<l) return 0;
	if (L<=l && r<=R) return v[h].ans;
	Shift(h,l,r);
	int x=get(Left);
	int y=get(Right);
	return max(x,y);
}

void Build(Tree) {
	if (l==r) {
		v[h].r=a[r];
		return ;
	}
	
	Build(Left);
	Build(Right);
	v[h].r=max(v[(h<<1)].r,v[((h<<1)|1)].r);
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	
	cin>>n;
	
	a[0]=1e8+1;
	for (int i=1; i<=n; i++) {
		cin>>a[i];
	}

	dq.push_back(0);
	for (int l,i=1,r; i<=n; i++) {
		while (a[dq.back()]<a[i]) 
			dq.pop_back();
		
		l=dq.back();	
		if (l) {
			r=i+i-l;
			if (r<=n) 
				E[l].push_back({r,a[l]+a[i]});
		}
	
		dq.push_back(i);
	}
	 
	while (dq.size()) dq.pop_back();
	
	dq.push_back(0);
	for (int l=n,i,r; l>=1; l--) {
		while (a[dq.back()]<a[l])
			dq.pop_back();
		
		i=dq.back();	
		if (i) {
			r=i+i-l;
			if (r<=n)
				E[l].push_back({r,a[l]+a[i]});
		}
		
		dq.push_back(l);
	}
	
	Build(1,1,n);
	
	cin>>q;
	for (int i=1; i<=q; i++) {
		int l,r;
		cin>>l>>r;
		Q[l].push_back({r,i});
	}
	
	for (L=n; L>=1; --L) {
		for (int j=0; j<E[L].size(); j++) {
			Upd(1,1,n,E[L][j].F,n,E[L][j].S);
		}
		
		for (int j=0; j<Q[L].size(); j++) {
			int id=Q[L][j].S;
			R=Q[L][j].F;
			ans[id]=get(1,1,n);
		}
	}
	
	for (int i=1; i<=q; i++)
		cout<<ans[i]<<"\n";
}

Compilation message

jumps.cpp:68:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   68 | main () {
      |       ^
jumps.cpp: In function 'int main()':
jumps.cpp:121:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |   for (int j=0; j<E[L].size(); j++) {
      |                 ~^~~~~~~~~~~~
jumps.cpp:125:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   for (int j=0; j<Q[L].size(); j++) {
      |                 ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 17 ms 23916 KB Output is correct
3 Correct 17 ms 23788 KB Output is correct
4 Correct 17 ms 23788 KB Output is correct
5 Correct 16 ms 23916 KB Output is correct
6 Correct 16 ms 23916 KB Output is correct
7 Correct 17 ms 23788 KB Output is correct
8 Correct 16 ms 23916 KB Output is correct
9 Correct 17 ms 23788 KB Output is correct
10 Correct 17 ms 24044 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 17 ms 23916 KB Output is correct
3 Correct 17 ms 23788 KB Output is correct
4 Correct 17 ms 23788 KB Output is correct
5 Correct 16 ms 23916 KB Output is correct
6 Correct 16 ms 23916 KB Output is correct
7 Correct 17 ms 23788 KB Output is correct
8 Correct 16 ms 23916 KB Output is correct
9 Correct 17 ms 23788 KB Output is correct
10 Correct 17 ms 24044 KB Output is correct
11 Correct 378 ms 42936 KB Output is correct
12 Correct 369 ms 42860 KB Output is correct
13 Correct 371 ms 42952 KB Output is correct
14 Correct 367 ms 43008 KB Output is correct
15 Correct 366 ms 42860 KB Output is correct
16 Correct 385 ms 42220 KB Output is correct
17 Correct 367 ms 42220 KB Output is correct
18 Correct 381 ms 42220 KB Output is correct
19 Correct 367 ms 42792 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 40044 KB Output is correct
2 Correct 130 ms 39788 KB Output is correct
3 Correct 136 ms 39788 KB Output is correct
4 Correct 214 ms 40044 KB Output is correct
5 Correct 212 ms 40188 KB Output is correct
6 Correct 204 ms 39404 KB Output is correct
7 Correct 213 ms 39372 KB Output is correct
8 Correct 206 ms 39276 KB Output is correct
9 Correct 207 ms 39680 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 17 ms 23916 KB Output is correct
3 Correct 17 ms 23788 KB Output is correct
4 Correct 17 ms 23788 KB Output is correct
5 Correct 16 ms 23916 KB Output is correct
6 Correct 16 ms 23916 KB Output is correct
7 Correct 17 ms 23788 KB Output is correct
8 Correct 16 ms 23916 KB Output is correct
9 Correct 17 ms 23788 KB Output is correct
10 Correct 17 ms 24044 KB Output is correct
11 Correct 378 ms 42936 KB Output is correct
12 Correct 369 ms 42860 KB Output is correct
13 Correct 371 ms 42952 KB Output is correct
14 Correct 367 ms 43008 KB Output is correct
15 Correct 366 ms 42860 KB Output is correct
16 Correct 385 ms 42220 KB Output is correct
17 Correct 367 ms 42220 KB Output is correct
18 Correct 381 ms 42220 KB Output is correct
19 Correct 367 ms 42792 KB Output is correct
20 Correct 220 ms 40044 KB Output is correct
21 Correct 130 ms 39788 KB Output is correct
22 Correct 136 ms 39788 KB Output is correct
23 Correct 214 ms 40044 KB Output is correct
24 Correct 212 ms 40188 KB Output is correct
25 Correct 204 ms 39404 KB Output is correct
26 Correct 213 ms 39372 KB Output is correct
27 Correct 206 ms 39276 KB Output is correct
28 Correct 207 ms 39680 KB Output is correct
29 Correct 1321 ms 84724 KB Output is correct
30 Correct 1113 ms 83600 KB Output is correct
31 Correct 1128 ms 81776 KB Output is correct
32 Correct 1298 ms 84948 KB Output is correct
33 Correct 1296 ms 84844 KB Output is correct
34 Correct 1308 ms 82540 KB Output is correct
35 Correct 1297 ms 82156 KB Output is correct
36 Correct 1306 ms 82112 KB Output is correct
37 Correct 1312 ms 83692 KB Output is correct
38 Correct 970 ms 90476 KB Output is correct
39 Correct 965 ms 90500 KB Output is correct
40 Correct 952 ms 87276 KB Output is correct
41 Correct 943 ms 86636 KB Output is correct
42 Correct 945 ms 86636 KB Output is correct
43 Correct 954 ms 88428 KB Output is correct
44 Correct 1022 ms 89716 KB Output is correct
45 Correct 1024 ms 89836 KB Output is correct
46 Correct 1012 ms 86680 KB Output is correct
47 Correct 997 ms 86208 KB Output is correct
48 Correct 998 ms 86204 KB Output is correct
49 Correct 1004 ms 88272 KB Output is correct
50 Correct 1096 ms 88044 KB Output is correct
51 Correct 1086 ms 87916 KB Output is correct
52 Correct 1079 ms 85476 KB Output is correct
53 Correct 1077 ms 85100 KB Output is correct
54 Correct 1088 ms 85228 KB Output is correct
55 Correct 1077 ms 86892 KB Output is correct