CSES - Datatähti Open 2019

CSES - Datatähti Open 2019 - Results

Submission details
Task:	Sunset
Sender:	elektrijanes
Submission time:	2019-01-20 21:24:03 +0200
Language:	C++
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	WRONG ANSWER	0.01 s	1	details
#2	ACCEPTED	0.02 s	1	details
#3	ACCEPTED	0.01 s	1	details
#4	ACCEPTED	0.02 s	1	details
#5	ACCEPTED	0.03 s	1	details
#6	WRONG ANSWER	0.03 s	1	details
#7	ACCEPTED	0.03 s	1	details
#8	ACCEPTED	0.03 s	1	details
#9	ACCEPTED	0.02 s	1	details
#10	ACCEPTED	0.08 s	1	details
#11	WRONG ANSWER	0.02 s	1	details
#12	WRONG ANSWER	0.03 s	1	details
#13	WRONG ANSWER	0.03 s	1	details
#14	ACCEPTED	0.06 s	1	details
#15	WRONG ANSWER	0.03 s	1	details
#16	WRONG ANSWER	0.02 s	1	details
#17	WRONG ANSWER	0.03 s	1	details
#18	ACCEPTED	0.02 s	2	details
#19	WRONG ANSWER	0.37 s	2	details
#20	TIME LIMIT EXCEEDED	--	2	details
#21	WRONG ANSWER	0.36 s	2	details
#22	ACCEPTED	0.38 s	2	details
#23	ACCEPTED	0.32 s	2	details
#24	WRONG ANSWER	0.36 s	2	details
#25	WRONG ANSWER	0.34 s	2	details
#26	ACCEPTED	0.42 s	2	details
#27	ACCEPTED	0.42 s	2	details
#28	ACCEPTED	0.03 s	2	details
#29	ACCEPTED	0.43 s	2	details
#30	ACCEPTED	0.33 s	2	details
#31	WRONG ANSWER	0.34 s	2	details
#32	ACCEPTED	0.02 s	3	details
#33	ACCEPTED	0.56 s	3	details
#34	ACCEPTED	0.57 s	3	details
#35	WRONG ANSWER	0.40 s	3	details
#36	ACCEPTED	0.41 s	3	details
#37	WRONG ANSWER	0.37 s	3	details
#38	ACCEPTED	0.32 s	3	details
#39	WRONG ANSWER	0.41 s	3	details
#40	WRONG ANSWER	0.36 s	3	details
#41	ACCEPTED	0.58 s	3	details
#42	WRONG ANSWER	0.35 s	3	details
#43	WRONG ANSWER	0.41 s	3	details
#44	TIME LIMIT EXCEEDED	--	3	details
#45	TIME LIMIT EXCEEDED	--	3	details
#46	ACCEPTED	0.35 s	3	details
#47	WRONG ANSWER	0.35 s	3	details
#48	WRONG ANSWER	0.38 s	3	details
#49	ACCEPTED	0.34 s	3	details
#50	ACCEPTED	0.38 s	3	details
#51	WRONG ANSWER	0.35 s	3	details
#52	WRONG ANSWER	0.35 s	3	details
#53	TIME LIMIT EXCEEDED	--	3	details
#54	ACCEPTED	0.57 s	3	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:90:7: warning: unused variable 'f' [-Wunused-variable]
   int f=leiap(1,1,c,a,b);
       ^
input/code.cpp: In function 'int leiap(int, int, int, int, int)':
input/code.cpp:65:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Code

#include <bits/stdc++.h>
#define mis(x) cout << #x <<" = " <<x<<endl
#define rep(i, a, b) for(int i=(a);(i)<(b);(i)++)
#define re(i,a) rep((i),0,(a))
using namespace std;
typedef long long ll;
ifstream fin("AAtest.in.txt");
int const cc=1000002;
int n,l,c,k,a,b,q,ma,koht;
ll h,g;
vector<pair<ll,int> > p;
vector<int> m,pai,t;
void loe(){
	cin>>n>>q;
	re(i,n){
		cin>>h;
		p.push_back({h,i});
	}
	sort(p.begin(),p.end());
	m.resize(n);
	g=p[0].first;	l=1;
	re(i,n){
		if(i and g<p[i].first){
			g=p[i].first;
			l++;
		}
		m[p[i].second]=l;
	}
//	for(auto i:m)cout<<i<<" ";cout<<endl;
}

void pane(int n,int x,int y,int i,int v){
	if(i<x or y<i)return;
	if(x==y){t[n]=v;return;	}
	pane(n*2,x,(x+y)/2,i,v);
	pane(n*2+1,(x+y)/2+1,y,i,v);
	t[n]=min(t[n*2],t[n*2+1]);
}

int leia(int n,int x,int y,int i,int j){
	if(j<x or y<i)return cc;
	if(i<=x and y<=j)return t[n];
	return(min(leia(n*2,x,(x+y)/2,i,j),leia(n*2+1,(x+y)/2+1,y,i,j)));
}

void pik(int n,int x,int y,int i,int v){
	if(i<x or y<i)return;
	if(x==y){//cout<<n<<" "<<i<<" "<<v<<endl;	
		t[n]=v;
		return;
	}
	pik(n*2,x,(x+y)/2,i,v);
	pik(n*2+1,(x+y)/2+1,y,i,v);
	t[n]=max(t[n*2],t[n*2+1]);
}

int leiap(int n,int x,int y,int i,int j){//cout<<x<<" "<<y<<" "<<i<<" "<<j<<" "<<ma<<endl;
	if(j<x or y<i)return -1;
	if(x==y){//cout<<x;
		koht=n-c;
		return t[n];
	}
	if(t[n*2]>ma)ma=max(ma,leiap(n*2,x,(x+y)/2,i,j));
	if(t[n*2+1]>ma)ma=max(ma,leiap(n*2+1,(x+y)/2+1,y,i,j));
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);	cout.tie(0);cerr.tie(0);
	loe();
	c=1;while(c<=l)c<<=1;t.resize(2*c+5,cc);
	pai.resize(n,0);
	pai[n-1]=0;
	for(int i=n-1;i>=0;i--){
		k=cc;
		pane(1,1,c,m[i],i);
		if(m[i]<l) k=leia(1,1,c,m[i]+1,l);
		if(k<cc)	pai[i]=pai[k]+1;
	}
	
	//for(auto i:pai)cout<<i<<" ";cout<<endl;
	c=1;while(c<=n)c<<=1;//mis(c);
	t.resize(2*c+5);
	re(i,2*c+5)t[i]=-1;
	re(i,n)	pik(1,1,c,i+1,m[i]);
//	for(auto i:t)cout<<i<<" ";cout<<endl;
	
	re(i,q){
		cin>>a>>b;
		ma=0;koht=0;
		int f=leiap(1,1,c,a,b);
		int vas=pai[a-1]-pai[koht]+1;
//		mis(koht);
//		mis(f);
		cout<<vas<<endl;
	}
}

Test details

Test 1

Group: 1

Verdict: WRONG ANSWER

input
`5 3 4 1 2 2 3 1 5 2 5 3 4` view save

correct output
`1 3 1` view save

user output
`1 1 1` view save

Test 2

Group: 1

Verdict: ACCEPTED

input
`1 1 1 1 1` view save

correct output
`1` view save

user output
`1` view save

Test 3

Group: 1

Verdict: ACCEPTED

input
`2 3 1 1000000000 1 1 2 2 1 2` view save

correct output
`1 1 2` view save

user output
`1 1 2` view save

Test 4

Group: 1

Verdict: ACCEPTED

input
`2 3 1000000000 1 1 1 2 2 1 2` view save

correct output
`1 1 1` view save

user output
`1 1 1` view save

Test 5

Group: 1

Verdict: ACCEPTED

input
`2000 2000 387547790 498212511 224378606 ...` view save

correct output
`14 10 10 3 7 ...` view save

user output
`14 10 10 3 7 ...` Truncated

Test 6

Group: 1

Verdict: WRONG ANSWER

input
`2000 2000 13604803 27447643 34139694 383...` view save

correct output
`198 43 38 58 50 ...` view save

user output
`198 2 1 1 2 ...` Truncated

Test 7

Group: 1

Verdict: ACCEPTED

input
`2000 2000 387547790 498212511 224378606 ...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

Test 8

Group: 1

Verdict: ACCEPTED

input
`2000 2000 409666302 646936685 583741760 ...` view save

correct output
`8 9 12 8 11 ...` view save

user output
`8 9 12 8 11 ...` Truncated

Test 9

Group: 1

Verdict: ACCEPTED

input
`2000 2000 1000000000 1000000000 10000000...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

Test 10

Group: 1

Verdict: ACCEPTED

input
`2000 2000 785263 793567 1573404 1750090 ...` view save

correct output
`2000 2000 2000 2000 2000 ...` view save

user output
`2000 2000 2000 2000 2000 ...` Truncated

Test 11

Group: 1

Verdict: WRONG ANSWER

input
`2000 2000 785263 793567 1573404 1750090 ...` view save

correct output
`1960 1947 1963 1942 1944 ...` view save

user output
`1960 2 2 2 1 ...` Truncated

Test 12

Group: 1

Verdict: WRONG ANSWER

input
`1999 2000 129087461 494922181 482953911 ...` view save

correct output
`10 6 6 7 7 ...` view save

user output
`10 2 1 1 2 ...` Truncated

Test 13

Group: 1

Verdict: WRONG ANSWER

input
`2000 2000 409666302 646936685 583741760 ...` view save

correct output
`8 7 6 7 7 ...` view save

user output
`8 1 1 1 1 ...` Truncated

Test 14

Group: 1

Verdict: ACCEPTED

input
`2000 2000 44989 1437234 1640005 1765235 ...` view save

correct output
`1233 1389 1026 150 796 ...` view save

user output
`1233 1389 1026 150 796 ...` Truncated

Test 15

Group: 1

Verdict: WRONG ANSWER

input
`2000 2000 2 1 4 3 6 5 8 7 10 9 12 11 14 ...` view save

correct output
`988 994 981 979 973 ...` view save

user output
`988 1 1 1 1 ...` Truncated

Test 16

Group: 1

Verdict: WRONG ANSWER

input
`2000 2000 1999 2000 1997 1998 1995 1996 ...` view save

correct output
`1 2 1 1 2 ...` view save

user output
`1 2 1 1 2 ...` Truncated

Test 17

Group: 1

Verdict: WRONG ANSWER

input
`2000 2000 2 1 4 3 5 4 5 2 3 1 2 1 4 3 5 ...` view save

correct output
`2 1 1 2 3 ...` view save

user output
`2 1 1 1 1 ...` Truncated

Test 18

Group: 2

Verdict: ACCEPTED

input
`1 1 1 1 1` view save

correct output
`1` view save

user output
`1` view save

Test 19

Group: 2

Verdict: WRONG ANSWER

input
`100000 200000 32 22 35 59 37 2 5 5 79 53 22 ...` view save

correct output
`4 9 6 5 4 ...` view save

user output
`4 1 1 2 1 ...` Truncated

Test 20

Group: 2

Verdict: TIME LIMIT EXCEEDED

input
`100000 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

correct output
`89 35 59 25 12 ...` view save

user output
(empty)

Test 21

Group: 2

Verdict: WRONG ANSWER

input
`100000 200000 32 22 35 59 37 2 5 5 79 53 22 ...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

Test 22

Group: 2

Verdict: ACCEPTED

input
`100000 200000 72 58 92 12 32 29 55 87 6 49 5...` view save

correct output
`5 7 5 6 2 ...` view save

user output
`5 7 5 6 2 ...` Truncated

Test 23

Group: 2

Verdict: ACCEPTED

input
`100000 200000 100 100 100 100 100 100 100 10...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

Test 24

Group: 2

Verdict: WRONG ANSWER

input
`100000 200000 72 58 92 12 32 29 55 87 6 49 5...` view save

correct output
`4 7 6 7 4 ...` view save

user output
`4 1 1 2 1 ...` Truncated

Test 25

Group: 2

Verdict: WRONG ANSWER

input
`100000 200000 72 58 92 12 32 29 55 87 6 49 5...` view save

correct output
`5 5 5 5 5 ...` view save

user output
`5 1 1 1 1 ...` Truncated

Test 26

Group: 2

Verdict: ACCEPTED

input
`99999 200000 20 47 84 90 88 63 39 16 74 19 ...` view save

correct output
`5 7 6 3 3 ...` view save

user output
`5 7 6 3 3 ...` Truncated

Test 27

Group: 2

Verdict: ACCEPTED

input
`100000 200000 72 58 92 12 32 29 55 87 6 49 5...` view save

correct output
`6 4 9 2 5 ...` view save

user output
`6 4 9 2 5 ...` Truncated

Test 28

Group: 2

Verdict: ACCEPTED

input
`5 1 4 1 5 6 9 1 3` view save

correct output
`2` view save

user output
`2` view save

Test 29

Group: 2

Verdict: ACCEPTED

input
`100000 200000 2 1 4 3 6 5 8 7 10 9 12 11 14 ...` view save

correct output
`44 4 27 46 29 ...` view save

user output
`44 4 27 46 29 ...` Truncated

Test 30

Group: 2

Verdict: ACCEPTED

input
`100000 200000 2 1 4 3 5 4 5 2 3 1 2 1 4 3 5 ...` view save

correct output
`3 3 3 3 2 ...` view save

user output
`3 3 3 3 2 ...` Truncated

Test 31

Group: 2

Verdict: WRONG ANSWER

input
`100000 200000 2 1 4 3 6 5 8 7 10 9 12 11 14 ...` view save

correct output
`39 10 37 20 43 ...` view save

user output
`39 1 1 1 1 ...` Truncated

Test 32

Group: 3

Verdict: ACCEPTED

input
`1 1 1 1 1` view save

correct output
`1` view save

user output
`1` view save

Test 33

Group: 3

Verdict: ACCEPTED

input
`100000 200000 994198482 687493351 579440176 ...` view save

correct output
`8 6 8 10 5 ...` view save

user output
`8 6 8 10 5 ...` Truncated

Test 34

Group: 3

Verdict: ACCEPTED

input
`100000 200000 138644593 592364551 919805093 ...` view save

correct output
`10 11 13 7 12 ...` view save

user output
`10 11 13 7 12 ...` Truncated

Test 35

Group: 3

Verdict: WRONG ANSWER

input
`100000 200000 10770 195579 349462 442791 450...` view save

correct output
`2468 1986 2632 129 4010 ...` view save

user output
`2468 2 1 2 2 ...` Truncated

Test 36

Group: 3

Verdict: ACCEPTED

input
`100000 200000 994198482 687493351 579440176 ...` view save

correct output
`1 2 1 2 1 ...` view save

user output
`1 2 1 2 1 ...` Truncated

Test 37

Group: 3

Verdict: WRONG ANSWER

input
`100000 200000 398809514 622635167 133376912 ...` view save

correct output
`15 13 16 11 17 ...` view save

user output
`15 1 2 1 1 ...` Truncated

Test 38

Group: 3

Verdict: ACCEPTED

input
`100000 200000 1000000000 1000000000 10000000...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

Test 39

Group: 3

Verdict: WRONG ANSWER

input
`100000 200000 398809514 622635167 133376912 ...` view save

correct output
`10 16 7 18 10 ...` view save

user output
`10 1 1 1 1 ...` Truncated

Test 40

Group: 3

Verdict: WRONG ANSWER

input
`100000 200000 11465 15800 19042 19282 20348 ...` view save

correct output
`99542 99728 99391 99890 99716 ...` view save

user output
`99542 1 2 2 2 ...` Truncated

Test 41

Group: 3

Verdict: ACCEPTED

input
`99999 200000 587542096 890780320 258438313 ...` view save

correct output
`8 6 11 11 17 ...` view save

user output
`8 6 11 11 17 ...` Truncated

Test 42

Group: 3

Verdict: WRONG ANSWER

input
`100000 200000 11283 24634 28852 37453 37625 ...` view save

correct output
`100000 100000 100000 100000 100000 ...` view save

user output
`100000 2 2 2 2 ...` Truncated

Test 43

Group: 3

Verdict: WRONG ANSWER

input
`100000 200000 398809514 622635167 133376912 ...` view save

correct output
`13 13 10 15 15 ...` view save

user output
`13 1 1 2 2 ...` Truncated

Test 44

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 200000 11465 15800 19042 19282 20348 ...` view save

correct output
`36112 6013 51073 8123 82052 ...` view save

user output
(empty)

Test 45

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

correct output
`99407 99529 99590 99589 99679 ...` view save

user output
(empty)

Test 46

Group: 3

Verdict: ACCEPTED

input
`100000 200000 100000 99999 99998 99997 99996...` view save

correct output
`1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 ...` Truncated

Test 47

Group: 3

Verdict: WRONG ANSWER

input
`100000 200000 2 1 4 3 6 5 8 7 10 9 12 11 14 ...` view save

correct output
`49946 49703 49786 49864 49720 ...` view save

user output
`49946 1 1 1 1 ...` Truncated

Test 48

Group: 3

Verdict: WRONG ANSWER

input
`100000 200000 99999 100000 99997 99998 99995...` view save

correct output
`2 1 2 2 1 ...` view save

user output
`2 1 2 2 1 ...` Truncated

Test 49

Group: 3

Verdict: ACCEPTED

input
`100000 200000 2 1 4 3 5 4 5 2 3 1 2 1 4 3 5 ...` view save

correct output
`3 3 3 3 2 ...` view save

user output
`3 3 3 3 2 ...` Truncated

Test 50

Group: 3

Verdict: ACCEPTED

input
`100000 200000 2 1 4 3 6 5 8 7 10 9 12 11 14 ...` view save

correct output
`19 23 2 21 4 ...` view save

user output
`19 23 2 21 4 ...` Truncated

Test 51

Group: 3

Verdict: WRONG ANSWER

input
`100000 200000 2 1 4 3 6 5 8 7 10 9 12 11 14 ...` view save

correct output
`112 237 49 141 57 ...` view save

user output
`112 1 1 1 1 ...` Truncated

Test 52

Group: 3

Verdict: WRONG ANSWER

input
`100000 200000 2 1 4 3 6 5 8 7 10 9 12 11 14 ...` view save

correct output
`2457 2199 2351 2450 2475 ...` view save

user output
`2457 1 1 1 1 ...` Truncated

Test 53

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100000 200000 2 1 4 3 6 5 8 7 10 9 12 11 14 ...` view save

correct output
`24841 24973 24865 24823 24969 ...` view save

user output
(empty)

Test 54

Group: 3

Verdict: ACCEPTED

input
`100000 200000 49999 50000 49997 49998 49995 ...` view save

correct output
`210 1 2 2 1 ...` view save

user output
`210 1 2 2 1 ...` Truncated

Datatähti Open 2019

Sunset

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Tasks

Submissions (elektrijanes)