oj.uz

Submission #421156

# Submission time Handle Problem Language Result Execution time Memory
421156 2021-06-08T19:28:21 Z Jasiekstrz Rainforest Jumps (APIO21_jumps) C++17
23 / 100
 4000 ms 240064 KB 
#include "jumps.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int NN=2e5;
const int PP=27e4;
const int L=18;
int n;
int tab[NN+10];
int e[NN+10][2];
int jb[NN+10][L+2];
int js[NN+10][L+2];
int pot;
set<pair<int,int>> tree[2*PP+10];
void upd_ans(int &ans,int i,int c)
{
	auto it=tree[i].upper_bound({c,n+10});
	if(it!=tree[i].begin() && (ans==-1 || prev(it)->fi>tab[ans]))
		ans=prev(it)->se;
	return;
}
int read_t(int l,int r,int c) // largest <=c
{
	int ans=-1;
	for(l+=pot-1,r+=pot-1;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			upd_ans(ans,l++,c);
		if(r%2==0)
			upd_ans(ans,r--,c);
	}
	return ans;
}
void init(int N,vector<int> H)
{
	n=N;
	tab[0]=tab[N+1]=N+10;
	e[0][0]=e[0][1]=0;
	e[N+1][0]=e[N+1][1]=N+1;
	for(int i=0;i<N;i++)
		tab[i+1]=H[i];
	vector<int> st;
	st={0};
	for(int i=1;i<=N;i++)
	{
		while(tab[st.back()]<tab[i])
		{
			e[st.back()][1]=i;
			st.pop_back();
		}
		e[i][0]=st.back();
		st.push_back(i);
	}
	while(st.size()>1)
	{
		e[st.back()][1]=N+1;
		st.pop_back();
	}
	for(int i=0;i<=N+1;i++)
	{
		if(tab[e[i][0]]>tab[e[i][1]])
			swap(e[i][0],e[i][1]);
		js[i][0]=e[i][0];
		jb[i][0]=e[i][1];
	}
	for(int l=1;l<=L;l++)
	{
		for(int i=0;i<=N+1;i++)
		{
			js[i][l]=js[js[i][l-1]][l-1];
			jb[i][l]=jb[jb[i][l-1]][l-1];
		}
	}
	for(pot=1;pot<n;pot*=2);
	for(int i=1;i<=N;i++)
	{
		for(int j=i+pot-1;j>0;j/=2)
			tree[j].insert({tab[i],i});
	}
	return;
}
int minimum_jumps(int A,int B,int C,int D)
{
	A++;B++;C++;D++;
	int mx2g=read_t(C,D,n+10);
	int mx2=tab[mx2g];
	int x=read_t(A,B,mx2);
	if(x==-1)
		return -1;
	int ans=0;
#warning C==D
	for(int l=L;l>=0;l--)
	{
		if(tab[jb[x][l]]<=tab[C])
		{
			x=jb[x][l];
			ans+=(1<<l);
		}
	}
	for(int l=L;l>=0;l--)
	{
		if(tab[js[x][l]]<=tab[C])
		{
			x=js[x][l];
			ans+=(1<<l);
		}
	}
	if(x<C || D<x)
		return -1;
	return ans;
}

Compilation message

jumps.cpp:92:2: warning: #warning C==D [-Wcpp]
   92 | #warning C==D
      |  ^~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25672 KB Output is correct
2 Correct 15 ms 25636 KB Output is correct
3 Correct 919 ms 195604 KB Output is correct
4 Correct 3313 ms 239296 KB Output is correct
5 Correct 2309 ms 128412 KB Output is correct
6 Correct 3692 ms 239376 KB Output is correct
7 Correct 2659 ms 171568 KB Output is correct
8 Execution timed out 4003 ms 239296 KB Time limit exceeded

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 25672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 25672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 25672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25672 KB Output is correct
2 Correct 14 ms 25672 KB Output is correct
3 Correct 15 ms 25672 KB Output is correct
4 Correct 776 ms 119268 KB Output is correct
5 Correct 2695 ms 239484 KB Output is correct
6 Correct 953 ms 57720 KB Output is correct
7 Correct 2573 ms 239344 KB Output is correct
8 Correct 1167 ms 95936 KB Output is correct
9 Correct 2655 ms 239376 KB Output is correct
10 Correct 1798 ms 239392 KB Output is correct
11 Correct 2074 ms 239296 KB Output is correct
12 Correct 1939 ms 239316 KB Output is correct
13 Correct 2591 ms 239408 KB Output is correct
14 Correct 2045 ms 239932 KB Output is correct
15 Correct 1849 ms 240036 KB Output is correct
16 Correct 1753 ms 240028 KB Output is correct
17 Correct 15 ms 25672 KB Output is correct
18 Correct 14 ms 25560 KB Output is correct
19 Correct 16 ms 25620 KB Output is correct
20 Correct 17 ms 25800 KB Output is correct
21 Correct 15 ms 25672 KB Output is correct
22 Correct 16 ms 25672 KB Output is correct
23 Correct 17 ms 25688 KB Output is correct
24 Correct 17 ms 25672 KB Output is correct
25 Correct 14 ms 25800 KB Output is correct
26 Correct 16 ms 26184 KB Output is correct
27 Correct 40 ms 27108 KB Output is correct
28 Correct 34 ms 27080 KB Output is correct
29 Correct 43 ms 27056 KB Output is correct
30 Correct 37 ms 27080 KB Output is correct
31 Correct 42 ms 27080 KB Output is correct
32 Correct 14 ms 25672 KB Output is correct
33 Correct 761 ms 143872 KB Output is correct
34 Correct 1500 ms 239300 KB Output is correct
35 Correct 832 ms 239416 KB Output is correct
36 Correct 1399 ms 239500 KB Output is correct
37 Correct 892 ms 239696 KB Output is correct
38 Correct 877 ms 240064 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25672 KB Output is correct
2 Correct 14 ms 25672 KB Output is correct
3 Correct 15 ms 25672 KB Output is correct
4 Correct 776 ms 119268 KB Output is correct
5 Correct 2695 ms 239484 KB Output is correct
6 Correct 953 ms 57720 KB Output is correct
7 Correct 2573 ms 239344 KB Output is correct
8 Correct 1167 ms 95936 KB Output is correct
9 Correct 2655 ms 239376 KB Output is correct
10 Correct 1798 ms 239392 KB Output is correct
11 Correct 2074 ms 239296 KB Output is correct
12 Correct 1939 ms 239316 KB Output is correct
13 Correct 2591 ms 239408 KB Output is correct
14 Correct 2045 ms 239932 KB Output is correct
15 Correct 1849 ms 240036 KB Output is correct
16 Correct 1753 ms 240028 KB Output is correct
17 Correct 15 ms 25672 KB Output is correct
18 Correct 14 ms 25560 KB Output is correct
19 Correct 16 ms 25620 KB Output is correct
20 Correct 17 ms 25800 KB Output is correct
21 Correct 15 ms 25672 KB Output is correct
22 Correct 16 ms 25672 KB Output is correct
23 Correct 17 ms 25688 KB Output is correct
24 Correct 17 ms 25672 KB Output is correct
25 Correct 14 ms 25800 KB Output is correct
26 Correct 16 ms 26184 KB Output is correct
27 Correct 40 ms 27108 KB Output is correct
28 Correct 34 ms 27080 KB Output is correct
29 Correct 43 ms 27056 KB Output is correct
30 Correct 37 ms 27080 KB Output is correct
31 Correct 42 ms 27080 KB Output is correct
32 Correct 14 ms 25672 KB Output is correct
33 Correct 761 ms 143872 KB Output is correct
34 Correct 1500 ms 239300 KB Output is correct
35 Correct 832 ms 239416 KB Output is correct
36 Correct 1399 ms 239500 KB Output is correct
37 Correct 892 ms 239696 KB Output is correct
38 Correct 877 ms 240064 KB Output is correct
39 Correct 14 ms 25672 KB Output is correct
40 Correct 14 ms 25672 KB Output is correct
41 Correct 14 ms 25672 KB Output is correct
42 Correct 866 ms 118972 KB Output is correct
43 Correct 2592 ms 239316 KB Output is correct
44 Correct 880 ms 57796 KB Output is correct
45 Correct 2512 ms 239332 KB Output is correct
46 Correct 992 ms 95920 KB Output is correct
47 Correct 2626 ms 239432 KB Output is correct
48 Correct 1964 ms 239300 KB Output is correct
49 Correct 1924 ms 239460 KB Output is correct
50 Correct 2116 ms 239336 KB Output is correct
51 Correct 2549 ms 239432 KB Output is correct
52 Correct 2173 ms 239772 KB Output is correct
53 Correct 1826 ms 240036 KB Output is correct
54 Correct 1656 ms 240060 KB Output is correct
55 Correct 14 ms 25644 KB Output is correct
56 Incorrect 1721 ms 238456 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 25672 KB Output is correct
2 Correct 15 ms 25636 KB Output is correct
3 Correct 919 ms 195604 KB Output is correct
4 Correct 3313 ms 239296 KB Output is correct
5 Correct 2309 ms 128412 KB Output is correct
6 Correct 3692 ms 239376 KB Output is correct
7 Correct 2659 ms 171568 KB Output is correct
8 Execution timed out 4003 ms 239296 KB Time limit exceeded