CSES - Datatähti Open 2019 - Results
Submission details
Task:Sunset
Sender:Saboon
Submission time:2019-01-18 17:13:40 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1details
#20.01 s1details
#30.03 s1details
#40.02 s1details
#50.02 s1details
#60.02 s1details
#70.02 s1details
#8ACCEPTED0.03 s1details
#90.02 s1details
#100.02 s1details
#110.02 s1details
#120.02 s1details
#130.03 s1details
#140.02 s1details
#150.02 s1details
#160.02 s1details
#170.02 s1details
#180.01 s2details
#190.49 s2details
#200.45 s2details
#210.33 s2details
#220.42 s2details
#230.41 s2details
#240.45 s2details
#250.35 s2details
#260.48 s2details
#270.48 s2details
#280.01 s2details
#290.41 s2details
#300.42 s2details
#310.41 s2details
#320.02 s3details
#330.46 s3details
#340.47 s3details
#350.44 s3details
#360.35 s3details
#37ACCEPTED0.41 s3details
#380.43 s3details
#390.46 s3details
#400.42 s3details
#410.48 s3details
#420.37 s3details
#430.48 s3details
#440.45 s3details
#450.43 s3details
#46ACCEPTED0.40 s3details
#470.43 s3details
#480.40 s3details
#490.41 s3details
#500.41 s3details
#510.40 s3details
#520.40 s3details
#530.41 s3details
#540.42 s3details

Code

/**
 *    author:  Atreus
 *    created: 18.01.2019
**/
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;

int seg[22][maxn];

int answer = 0;
void get(int id, int L, int R, int l, int r, int x, int h = 0){
	if (L == l and R == r){
		int idx = lower_bound(seg[h] + L, seg[h] + R, x) - (seg[h] + L);
		answer += idx;
		return;
	}
	int mid = (L + R) >> 1;
	if (mid > l)
		get(2 * id + 0, L, mid, l, min(mid, r), x, h + 1);
	if (mid < r)
		get(2 * id + 1, mid, R, max(l, mid), r, x, h + 1);
}

int pre[maxn], a[maxn];

void build(int id, int L, int R, int h = 0){
	if (L + 1 == R){
		seg[h][L] = pre[L];
		return;
	}
	int mid = (L + R) >> 1;
	build(2 * id + 0, L, mid, h + 1);
	build(2 * id + 1, mid, R, h + 1);
	for (int i = L; i < R; i++)
		seg[h][i] = seg[h + 1][i];
	sort(seg[h] + L, seg[h] + R);
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	stack <int> s;
	a[0] = 1000 * 1000 * 1000 + 1;
	s.push(0);
	for (int i = 1; i <= n; i++){
		while (a[i] >= a[s.top()])
			s.pop();
		pre[i] = s.top();
		s.push(i);
	}
	build(1, 1, n + 1);
	for (int i = 0; i < q; i++){
		int l, r;
		cin >> l >> r;
		answer = 0;
		get(1, 1, n + 1, l, r, l);
		cout << answer << '\n';
	}
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
5 3
4 1 2 2 3
1 5
2 5
3 4

correct output
1
3
1

user output
1
3
1

Test 2

Group: 1

Verdict:

input
1 1
1
1 1

correct output
1

user output
0

Test 3

Group: 1

Verdict:

input
2 3
1 1000000000
1 1
2 2
1 2

correct output
1
1
2

user output
0
0
1

Test 4

Group: 1

Verdict:

input
2 3
1000000000 1
1 1
2 2
1 2

correct output
1
1
1

user output
0
0
1

Test 5

Group: 1

Verdict:

input
2000 2000
387547790 498212511 224378606 ...

correct output
14
10
10
3
7
...

user output
14
10
10
3
7
...
Truncated

Test 6

Group: 1

Verdict:

input
2000 2000
13604803 27447643 34139694 383...

correct output
198
43
38
58
50
...

user output
198
42
38
58
50
...
Truncated

Test 7

Group: 1

Verdict:

input
2000 2000
387547790 498212511 224378606 ...

correct output
1
1
1
1
1
...

user output
0
0
0
0
0
...
Truncated

Test 8

Group: 1

Verdict: ACCEPTED

input
2000 2000
409666302 646936685 583741760 ...

correct output
8
9
12
8
11
...

user output
8
9
12
8
11
...
Truncated

Test 9

Group: 1

Verdict:

input
2000 2000
1000000000 1000000000 10000000...

correct output
1
1
1
1
1
...

user output
1973
1959
1963
1951
1965
...
Truncated

Test 10

Group: 1

Verdict:

input
2000 2000
785263 793567 1573404 1750090 ...

correct output
2000
2000
2000
2000
2000
...

user output
1999
1999
1999
1999
1999
...
Truncated

Test 11

Group: 1

Verdict:

input
2000 2000
785263 793567 1573404 1750090 ...

correct output
1960
1947
1963
1942
1944
...

user output
1959
1946
1962
1941
1943
...
Truncated

Test 12

Group: 1

Verdict:

input
1999 2000
129087461 494922181 482953911 ...

correct output
10
6
6
7
7
...

user output
10
6
6
7
7
...
Truncated

Test 13

Group: 1

Verdict:

input
2000 2000
409666302 646936685 583741760 ...

correct output
8
7
6
7
7
...

user output
8
7
6
7
7
...
Truncated

Test 14

Group: 1

Verdict:

input
2000 2000
44989 1437234 1640005 1765235 ...

correct output
1233
1389
1026
150
796
...

user output
1232
1388
1025
149
795
...
Truncated

Test 15

Group: 1

Verdict:

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

correct output
988
994
981
979
973
...

user output
987
993
981
979
973
...
Truncated

Test 16

Group: 1

Verdict:

input
2000 2000
1999 2000 1997 1998 1995 1996 ...

correct output
1
2
1
1
2
...

user output
1
2
1
1
2
...
Truncated

Test 17

Group: 1

Verdict:

input
2000 2000
2 1 4 3 5 4 5 2 3 1 2 1 4 3 5 ...

correct output
2
1
1
2
3
...

user output
397
394
389
392
394
...
Truncated

Test 18

Group: 2

Verdict:

input
1 1
1
1 1

correct output
1

user output
0

Test 19

Group: 2

Verdict:

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

correct output
4
9
6
5
4
...

user output
668
737
422
433
727
...
Truncated

Test 20

Group: 2

Verdict:

input
100000 200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

correct output
89
35
59
25
12
...

user output
8845
3969
6197
2742
1056
...
Truncated

Test 21

Group: 2

Verdict:

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

correct output
1
1
1
1
1
...

user output
0
0
0
0
0
...
Truncated

Test 22

Group: 2

Verdict:

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

correct output
5
7
5
6
2
...

user output
1063
1064
1066
1063
1059
...
Truncated

Test 23

Group: 2

Verdict:

input
100000 200000
100 100 100 100 100 100 100 10...

correct output
1
1
1
1
1
...

user output
99853
99474
99624
99384
99719
...
Truncated

Test 24

Group: 2

Verdict:

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

correct output
4
7
6
7
4
...

user output
812
243
572
444
526
...
Truncated

Test 25

Group: 2

Verdict:

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

correct output
5
5
5
5
5
...

user output
1066
1066
1066
1066
1066
...
Truncated

Test 26

Group: 2

Verdict:

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

correct output
5
7
6
3
3
...

user output
385
756
166
41
211
...
Truncated

Test 27

Group: 2

Verdict:

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

correct output
6
4
9
2
5
...

user output
871
311
638
428
206
...
Truncated

Test 28

Group: 2

Verdict:

input
5 1
4 1 5 6 9
1 3

correct output
2

user output
1

Test 29

Group: 2

Verdict:

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

correct output
44
4
27
46
29
...

user output
1038
998
1023
1042
1023
...
Truncated

Test 30

Group: 2

Verdict:

input
100000 200000
2 1 4 3 5 4 5 2 3 1 2 1 4 3 5 ...

correct output
3
3
3
3
2
...

user output
19892
19945
19882
19924
19878
...
Truncated

Test 31

Group: 2

Verdict:

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

correct output
39
10
37
20
43
...

user output
1033
1003
1031
1015
1042
...
Truncated

Test 32

Group: 3

Verdict:

input
1 1
1
1 1

correct output
1

user output
0

Test 33

Group: 3

Verdict:

input
100000 200000
994198482 687493351 579440176 ...

correct output
8
6
8
10
5
...

user output
8
6
8
10
5
...
Truncated

Test 34

Group: 3

Verdict:

input
100000 200000
138644593 592364551 919805093 ...

correct output
10
11
13
7
12
...

user output
10
11
13
7
12
...
Truncated

Test 35

Group: 3

Verdict:

input
100000 200000
10770 195579 349462 442791 450...

correct output
2468
1986
2632
129
4010
...

user output
2467
1986
2632
129
4010
...
Truncated

Test 36

Group: 3

Verdict:

input
100000 200000
994198482 687493351 579440176 ...

correct output
1
2
1
2
1
...

user output
1
1
0
1
0
...
Truncated

Test 37

Group: 3

Verdict: ACCEPTED

input
100000 200000
398809514 622635167 133376912 ...

correct output
15
13
16
11
17
...

user output
15
13
16
11
17
...
Truncated

Test 38

Group: 3

Verdict:

input
100000 200000
1000000000 1000000000 10000000...

correct output
1
1
1
1
1
...

user output
99732
99392
99641
99684
99478
...
Truncated

Test 39

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...

correct output
10
16
7
18
10
...

user output
10
16
7
18
10
...
Truncated

Test 40

Group: 3

Verdict:

input
100000 200000
11465 15800 19042 19282 20348 ...

correct output
99542
99728
99391
99890
99716
...

user output
99541
99727
99390
99889
99715
...
Truncated

Test 41

Group: 3

Verdict:

input
99999 200000
587542096 890780320 258438313 ...

correct output
8
6
11
11
17
...

user output
8
6
11
11
17
...
Truncated

Test 42

Group: 3

Verdict:

input
100000 200000
11283 24634 28852 37453 37625 ...

correct output
100000
100000
100000
100000
100000
...

user output
99999
99999
99999
99999
99999
...
Truncated

Test 43

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...

correct output
13
13
10
15
15
...

user output
13
13
10
15
15
...
Truncated

Test 44

Group: 3

Verdict:

input
100000 200000
11465 15800 19042 19282 20348 ...

correct output
36112
6013
51073
8123
82052
...

user output
36111
6012
51072
8122
82051
...
Truncated

Test 45

Group: 3

Verdict:

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

correct output
99407
99529
99590
99589
99679
...

user output
99406
99528
99589
99588
99678
...
Truncated

Test 46

Group: 3

Verdict: ACCEPTED

input
100000 200000
100000 99999 99998 99997 99996...

correct output
1
1
1
1
1
...

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

correct output
49946
49703
49786
49864
49720
...

user output
49946
49702
49785
49863
49719
...
Truncated

Test 48

Group: 3

Verdict:

input
100000 200000
99999 100000 99997 99998 99995...

correct output
2
1
2
2
1
...

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

correct output
3
3
3
3
2
...

user output
19892
19945
19882
19924
19878
...
Truncated

Test 50

Group: 3

Verdict:

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

correct output
19
23
2
21
4
...

user output
2008
2011
1995
2016
1995
...
Truncated

Test 51

Group: 3

Verdict:

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

correct output
112
237
49
141
57
...

user output
311
436
248
340
256
...
Truncated

Test 52

Group: 3

Verdict:

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

correct output
2457
2199
2351
2450
2475
...

user output
2476
2218
2370
2469
2494
...
Truncated

Test 53

Group: 3

Verdict:

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

correct output
24841
24973
24865
24823
24969
...

user output
24842
24974
24866
24824
24970
...
Truncated

Test 54

Group: 3

Verdict:

input
100000 200000
49999 50000 49997 49998 49995 ...

correct output
210
1
2
2
1
...

user output
210
1
2
2
1
...
Truncated