— Dark mode

Datatähti Open 2019

Sunset

  • Start: N/A
  • End: N/A
Submission details
Task:Sunset
Sender:elektrijanes
Submission time:2019-01-20 21:52:54 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1details
#2ACCEPTED0.03 s1details
#3ACCEPTED0.01 s1details
#4ACCEPTED0.02 s1details
#50.02 s1details
#60.03 s1details
#7ACCEPTED0.02 s1details
#80.02 s1details
#9ACCEPTED0.02 s1details
#100.03 s1details
#110.02 s1details
#120.02 s1details
#130.02 s1details
#140.03 s1details
#15ACCEPTED0.06 s1details
#160.04 s1details
#17ACCEPTED0.02 s1details
#18ACCEPTED0.02 s2details
#190.36 s2details
#200.35 s2details
#210.38 s2details
#220.35 s2details
#23ACCEPTED0.32 s2details
#240.36 s2details
#250.33 s2details
#260.42 s2details
#270.36 s2details
#28ACCEPTED0.01 s2details
#290.43 s2details
#30ACCEPTED0.34 s2details
#310.44 s2details
#32ACCEPTED0.01 s3details
#330.40 s3details
#340.56 s3details
#350.39 s3details
#360.40 s3details
#370.55 s3details
#38ACCEPTED0.33 s3details
#390.41 s3details
#40--3details
#410.41 s3details
#42--3details
#430.41 s3details
#44--3details
#45--3details
#46ACCEPTED0.35 s3details
#470.35 s3details
#480.37 s3details
#490.33 s3details
#500.38 s3details
#510.34 s3details
#520.35 s3details
#530.37 s3details
#54ACCEPTED0.56 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:83: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:64: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=1000001;
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;
	}
}
 
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]=t[n*2];
}
 
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){
		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){
	if(j<x or y<i)return -1;
	if(x==y){
		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);
	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;
	}
	c=1;while(c<=n)c<<=1;
	t.resize(2*c+5);
	re(i,2*c+5)t[i]=-1;
	re(i,n)	pik(1,1,c,i+1,m[i]);
	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;
		cout<<vas<<endl;
	}
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

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
3
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:

input
2000 2000
387547790 498212511 224378606 ...
view save

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

user output
11
5
7
2
5
...
Truncated

Test 6

Group: 1

Verdict:

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

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

user output
7
0
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:

input
2000 2000
409666302 646936685 583741760 ...
view save

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

user output
11
1
-1
1
1
...
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:

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

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

user output
2000
2
2
2
2
...
Truncated

Test 11

Group: 1

Verdict:

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:

input
1999 2000
129087461 494922181 482953911 ...
view save

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

user output
6
1
8
5
2
...
Truncated

Test 13

Group: 1

Verdict:

input
2000 2000
409666302 646936685 583741760 ...
view save

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

user output
6
1
1
1
1
...
Truncated

Test 14

Group: 1

Verdict:

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

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

user output
1233
1
2
2
2
...
Truncated

Test 15

Group: 1

Verdict: ACCEPTED

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
994
981
979
973
...
Truncated

Test 16

Group: 1

Verdict:

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: ACCEPTED

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
2
3
...
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:

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
5
1
1
1
1
...
Truncated

Test 20

Group: 2

Verdict:

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
89
1
1
1
1
...
Truncated

Test 21

Group: 2

Verdict:

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:

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
3
1
4
5
1
...
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:

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
3
1
1
3
1
...
Truncated

Test 25

Group: 2

Verdict:

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
6
1
1
1
1
...
Truncated

Test 26

Group: 2

Verdict:

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
10
4
3
...
Truncated

Test 27

Group: 2

Verdict:

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
8
1
1
1
1
...
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:

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
45
5
28
47
30
...
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:

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
40
11
38
21
44
...
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:

input
100000 200000
994198482 687493351 579440176 ...
view save

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

user output
2
0
2
1
1
...
Truncated

Test 34

Group: 3

Verdict:

input
100000 200000
138644593 592364551 919805093 ...
view save

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

user output
3
5
9
5
3
...
Truncated

Test 35

Group: 3

Verdict:

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

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

user output
1
1
1
2
1
...
Truncated

Test 36

Group: 3

Verdict:

input
100000 200000
994198482 687493351 579440176 ...
view save

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

user output
1
1
1
1
1
...
Truncated

Test 37

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...
view save

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

user output
4
4
4
4
5
...
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:

input
100000 200000
398809514 622635167 133376912 ...
view save

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

user output
5
1
1
1
1
...
Truncated

Test 40

Group: 3

Verdict:

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

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

user output
(empty)

Test 41

Group: 3

Verdict:

input
99999 200000
587542096 890780320 258438313 ...
view save

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

user output
2
1
1
1
0
...
Truncated

Test 42

Group: 3

Verdict:

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

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

user output
(empty)

Test 43

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...
view save

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

user output
4
1
1
2
1
...
Truncated

Test 44

Group: 3

Verdict:

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:

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:

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:

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:

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
1
1
1
1
...
Truncated

Test 50

Group: 3

Verdict:

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
20
24
3
22
5
...
Truncated

Test 51

Group: 3

Verdict:

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
113
1
1
1
1
...
Truncated

Test 52

Group: 3

Verdict:

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
2458
1
1
1
1
...
Truncated

Test 53

Group: 3

Verdict:

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
24842
1
1
1
1
...
Truncated

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

Tasks

A Sum-B Bit string-C Sunset-D Binary tree-E Function-F Robot-G Classifier-

Submissions (elektrijanes)

2019-01-22 14:40:09 1002019-01-22 14:39:26 02019-01-22 14:37:26 162019-01-22 14:31:32 1002019-01-21 14:05:32 1002019-01-21 13:53:52 02019-01-21 13:21:04 512019-01-21 12:48:07 512019-01-21 12:44:31 162019-01-20 22:14:55 02019-01-20 21:52:54 02019-01-20 21:46:03 02019-01-20 21:39:58 02019-01-20 21:24:03 04:20:38 03:42:19 0