oj.uz

Submission #400082

# Submission time Handle Problem Language Result Execution time Memory
400082 2021-05-07T10:12:52 Z keta_tsimakuridze Triple Jump (JOI19_jumps) C++14
100 / 100
 1915 ms 114916 KB 
#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=5e5+5,mod=1e9+7;
int t,a[N],L[N],R[N],lazy[4*N],ans[N],n,F;
pair<int,int> tree[4*N];
vector<int>V[N];
vector<pair<int,int> > q[N];
void update(int u,int start,int end,int l,int r,int val,int f) {
	if(lazy[u]){
			tree[u].s = max(tree[u].s,tree[u].f + lazy[u]);
			if(l!=r){
				lazy[2*u]=max(lazy[2*u],lazy[u]);
				lazy[2*u+1]=max(lazy[2*u+1],lazy[u]);
			}
			lazy[u] = 0;
	}
	if(l>end || r<start) return;
	if(start<=l && r<=end) { 
		if(f == 0) tree[u].f = val,tree[u].s = val;
		else {
			lazy[u] = val;
			tree[u].s = max(tree[u].s,tree[u].f + lazy[u]);
			if(l!=r){
				lazy[2*u]=max(lazy[2*u],lazy[u]);
				lazy[2*u+1]=max(lazy[2*u+1],lazy[u]);
			}
			lazy[u] = 0;
		}
		return;
	}
	int mid=(l+r)/2;
	update(2*u,start,end,l,mid,val,f);
	update(2*u+1,start,end,mid+1,r,val,f);
	tree[u].s = max(tree[2*u].s,tree[2*u+1].s);
	tree[u].f = max(tree[2*u].f,tree[2*u+1].f);
}
int getans(int u,int start,int end,int l,int r){
	if(lazy[u]){
			tree[u].s = max(tree[u].s,tree[u].f + lazy[u]);
			if(l!=r){
				lazy[2*u]=max(lazy[2*u],lazy[u]);
				lazy[2*u+1]=max(lazy[2*u+1],lazy[u]);
			}
			lazy[u] = 0;
	}
	if(l>end || r<start) return 0;
	if(start<=l && r<=end) {
		return tree[u].s;
	}
	int mid=(l+r)/2;
	return max(getans(2*u,start,end,l,mid),getans(2*u+1,start,end,mid+1,r));	
}
string s;
 main(){
	// t=1;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		int x=i-1;
		while(x && a[x]<a[i]){
			x=L[x];
		}
		L[i]=x;
		V[x].push_back(i);
	} 
	for(int i=n;i>=1;i--){
		int x = i+1;
		while(x<=n && a[x]<a[i]){
			x=R[x];
		}
		R[i]=x;
		V[i].push_back(x);
		
	}
	int Q;
	cin>>Q;
	for(int i=1;i<=Q;i++){
		int l,r;
		cin>>l>>r;
		q[l].push_back({r,i});
	}
	for(int i=n;i>=1;i--){
		update(1,i,i,1,n,a[i],0);
		for(int j=0;j<V[i].size();j++){
			int ind = 2*V[i][j]-i;
			if(i==3 && V[i][j]==4) F=1;
			update(1,ind,n,1,n,a[i]+a[V[i][j]],1); F=0;
		}
		for(int j=0;j<q[i].size();j++){
			if(i==2) F=1;
			ans[q[i][j].s]=getans(1,i+2,q[i][j].f,1,n); F=0;
		}
	}
	for(int i=1;i<=Q;i++){
		cout<<ans[i]<<" ";
	}
}

Compilation message

jumps.cpp:57:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   57 |  main(){
      |       ^
jumps.cpp: In function 'int main()':
jumps.cpp:87:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int j=0;j<V[i].size();j++){
      |               ~^~~~~~~~~~~~
jumps.cpp:92:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |   for(int j=0;j<q[i].size();j++){
      |               ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23752 KB Output is correct
2 Correct 15 ms 23756 KB Output is correct
3 Correct 15 ms 23732 KB Output is correct
4 Correct 16 ms 23776 KB Output is correct
5 Correct 15 ms 23756 KB Output is correct
6 Correct 15 ms 23772 KB Output is correct
7 Correct 15 ms 23840 KB Output is correct
8 Correct 15 ms 23788 KB Output is correct
9 Correct 16 ms 23756 KB Output is correct
10 Correct 15 ms 23844 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23752 KB Output is correct
2 Correct 15 ms 23756 KB Output is correct
3 Correct 15 ms 23732 KB Output is correct
4 Correct 16 ms 23776 KB Output is correct
5 Correct 15 ms 23756 KB Output is correct
6 Correct 15 ms 23772 KB Output is correct
7 Correct 15 ms 23840 KB Output is correct
8 Correct 15 ms 23788 KB Output is correct
9 Correct 16 ms 23756 KB Output is correct
10 Correct 15 ms 23844 KB Output is correct
11 Correct 600 ms 51508 KB Output is correct
12 Correct 595 ms 51400 KB Output is correct
13 Correct 613 ms 51440 KB Output is correct
14 Correct 568 ms 51424 KB Output is correct
15 Correct 545 ms 51644 KB Output is correct
16 Correct 566 ms 50832 KB Output is correct
17 Correct 575 ms 50880 KB Output is correct
18 Correct 541 ms 50756 KB Output is correct
19 Correct 529 ms 51428 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 48344 KB Output is correct
2 Correct 239 ms 48656 KB Output is correct
3 Correct 250 ms 47244 KB Output is correct
4 Correct 337 ms 48376 KB Output is correct
5 Correct 328 ms 48324 KB Output is correct
6 Correct 302 ms 48420 KB Output is correct
7 Correct 296 ms 48324 KB Output is correct
8 Correct 301 ms 48464 KB Output is correct
9 Correct 309 ms 48408 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23752 KB Output is correct
2 Correct 15 ms 23756 KB Output is correct
3 Correct 15 ms 23732 KB Output is correct
4 Correct 16 ms 23776 KB Output is correct
5 Correct 15 ms 23756 KB Output is correct
6 Correct 15 ms 23772 KB Output is correct
7 Correct 15 ms 23840 KB Output is correct
8 Correct 15 ms 23788 KB Output is correct
9 Correct 16 ms 23756 KB Output is correct
10 Correct 15 ms 23844 KB Output is correct
11 Correct 600 ms 51508 KB Output is correct
12 Correct 595 ms 51400 KB Output is correct
13 Correct 613 ms 51440 KB Output is correct
14 Correct 568 ms 51424 KB Output is correct
15 Correct 545 ms 51644 KB Output is correct
16 Correct 566 ms 50832 KB Output is correct
17 Correct 575 ms 50880 KB Output is correct
18 Correct 541 ms 50756 KB Output is correct
19 Correct 529 ms 51428 KB Output is correct
20 Correct 327 ms 48344 KB Output is correct
21 Correct 239 ms 48656 KB Output is correct
22 Correct 250 ms 47244 KB Output is correct
23 Correct 337 ms 48376 KB Output is correct
24 Correct 328 ms 48324 KB Output is correct
25 Correct 302 ms 48420 KB Output is correct
26 Correct 296 ms 48324 KB Output is correct
27 Correct 301 ms 48464 KB Output is correct
28 Correct 309 ms 48408 KB Output is correct
29 Correct 1915 ms 111824 KB Output is correct
30 Correct 1647 ms 112616 KB Output is correct
31 Correct 1672 ms 108784 KB Output is correct
32 Correct 1867 ms 111796 KB Output is correct
33 Correct 1886 ms 111880 KB Output is correct
34 Correct 1828 ms 109496 KB Output is correct
35 Correct 1835 ms 109384 KB Output is correct
36 Correct 1837 ms 109252 KB Output is correct
37 Correct 1835 ms 110776 KB Output is correct
38 Correct 1447 ms 114372 KB Output is correct
39 Correct 1462 ms 114540 KB Output is correct
40 Correct 1415 ms 111208 KB Output is correct
41 Correct 1392 ms 110704 KB Output is correct
42 Correct 1388 ms 110564 KB Output is correct
43 Correct 1413 ms 112372 KB Output is correct
44 Correct 1542 ms 114764 KB Output is correct
45 Correct 1536 ms 114756 KB Output is correct
46 Correct 1469 ms 111712 KB Output is correct
47 Correct 1453 ms 111332 KB Output is correct
48 Correct 1474 ms 111208 KB Output is correct
49 Correct 1488 ms 113240 KB Output is correct
50 Correct 1640 ms 114916 KB Output is correct
51 Correct 1631 ms 114900 KB Output is correct
52 Correct 1584 ms 112456 KB Output is correct
53 Correct 1555 ms 112180 KB Output is correct
54 Correct 1564 ms 112316 KB Output is correct
55 Correct 1572 ms 113828 KB Output is correct