CSES - Datatähti Open 2019

Submission details
Task:	Sunset
Sender:	Diuven
Submission time:	2019-01-18 04:36:40 +0200
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	16
#2	ACCEPTED	35
#3	ACCEPTED	49

Test results
test	verdict	time	group
#1	ACCEPTED	0.03 s	1	details
#2	ACCEPTED	0.03 s	1	details
#3	ACCEPTED	0.02 s	1	details
#4	ACCEPTED	0.01 s	1	details
#5	ACCEPTED	0.02 s	1	details
#6	ACCEPTED	0.03 s	1	details
#7	ACCEPTED	0.03 s	1	details
#8	ACCEPTED	0.01 s	1	details
#9	ACCEPTED	0.02 s	1	details
#10	ACCEPTED	0.02 s	1	details
#11	ACCEPTED	0.02 s	1	details
#12	ACCEPTED	0.02 s	1	details
#13	ACCEPTED	0.02 s	1	details
#14	ACCEPTED	0.02 s	1	details
#15	ACCEPTED	0.02 s	1	details
#16	ACCEPTED	0.02 s	1	details
#17	ACCEPTED	0.02 s	1	details
#18	ACCEPTED	0.02 s	2	details
#19	ACCEPTED	0.14 s	2	details
#20	ACCEPTED	0.14 s	2	details
#21	ACCEPTED	0.14 s	2	details
#22	ACCEPTED	0.13 s	2	details
#23	ACCEPTED	0.12 s	2	details
#24	ACCEPTED	0.13 s	2	details
#25	ACCEPTED	0.10 s	2	details
#26	ACCEPTED	0.14 s	2	details
#27	ACCEPTED	0.16 s	2	details
#28	ACCEPTED	0.02 s	2	details
#29	ACCEPTED	0.13 s	2	details
#30	ACCEPTED	0.12 s	2	details
#31	ACCEPTED	0.13 s	2	details
#32	ACCEPTED	0.02 s	3	details
#33	ACCEPTED	0.15 s	3	details
#34	ACCEPTED	0.15 s	3	details
#35	ACCEPTED	0.15 s	3	details
#36	ACCEPTED	0.16 s	3	details
#37	ACCEPTED	0.13 s	3	details
#38	ACCEPTED	0.13 s	3	details
#39	ACCEPTED	0.15 s	3	details
#40	ACCEPTED	0.14 s	3	details
#41	ACCEPTED	0.15 s	3	details
#42	ACCEPTED	0.11 s	3	details
#43	ACCEPTED	0.15 s	3	details
#44	ACCEPTED	0.15 s	3	details
#45	ACCEPTED	0.12 s	3	details
#46	ACCEPTED	0.12 s	3	details
#47	ACCEPTED	0.14 s	3	details
#48	ACCEPTED	0.13 s	3	details
#49	ACCEPTED	0.12 s	3	details
#50	ACCEPTED	0.13 s	3	details
#51	ACCEPTED	0.14 s	3	details
#52	ACCEPTED	0.13 s	3	details
#53	ACCEPTED	0.13 s	3	details
#54	ACCEPTED	0.12 s	3	details

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MX = 200010;
const int MOD = 1e9+7;
const int inf = 2e9;
const ll linf = 2e18;

int n, q;
int H[MX], lft[MX];

struct _st{ int l, r, idx, ans; } query[MX];

int tree[MX];
void upt(int x, int d){
	for(; 0<x && x<=n; x+=x&(-x)) tree[x]+=d;
}
int sum(int x){
	int ans=0;
	for(; 0<x; x-=x&(-x)) ans+=tree[x];
	return ans;
}


int main(){
	ios::sync_with_stdio(0), cin.tie(0);
	cin>>n>>q;
	for(int i=1; i<=n; i++) cin>>H[i];
	for(int i=1; i<=q; i++){
		int l,r; cin>>l>>r;
		query[i] = {l,r,i};
	}

	stack<int> stk;
	for(int i=n; i>=1; i--){
		while(!stk.empty()){
			int j = stk.top();
			if(H[i]>=H[j]) lft[j]=i, stk.pop();
			else break;
		}
		stk.push(i);
	}
	while(!stk.empty()){
		int j = stk.top(); stk.pop();
		lft[j]=0;
	}

	int frt=0, bck=0;
	pii V[MX];
	for(int i=1; i<=n; i++) V[bck++] = {lft[i], i};
	sort(V, V+bck);

	sort(query+1, query+q+1, [](_st &a, _st &b){ return a.l<b.l; });

	for(int i=1; i<=q; i++){
		int l=query[i].l, r=query[i].r;
		while(frt<bck){
			int x,j; tie(x,j) = V[frt];
			if(x>=l) break;
			upt(j,1); frt++;
		}
		query[i].ans = sum(r) - sum(l-1);
	}

	sort(query+1, query+q+1, [](_st &a, _st &b){ return a.idx < b.idx; });

	for(int i=1; i<=q; i++) cout<<query[i].ans<<'\n';

	return 0;
}

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

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

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

user output
`198 43 38 58 50 ...` 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: ACCEPTED

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

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

user output
`1960 1947 1963 1942 1944 ...` Truncated

Test 12

Group: 1

Verdict: ACCEPTED

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

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

user output
`10 6 6 7 7 ...` Truncated

Test 13

Group: 1

Verdict: ACCEPTED

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

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

user output
`8 7 6 7 7 ...` 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: 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: ACCEPTED

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

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 9 6 5 4 ...` Truncated

Test 20

Group: 2

Verdict: ACCEPTED

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 35 59 25 12 ...` Truncated

Test 21

Group: 2

Verdict: ACCEPTED

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

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 7 6 7 4 ...` Truncated

Test 25

Group: 2

Verdict: ACCEPTED

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 5 5 5 5 ...` 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: ACCEPTED

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 10 37 20 43 ...` 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: ACCEPTED

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

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

user output
`2468 1986 2632 129 4010 ...` 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: ACCEPTED

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

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

user output
`15 13 16 11 17 ...` 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: ACCEPTED

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

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

user output
`10 16 7 18 10 ...` Truncated

Test 40

Group: 3

Verdict: ACCEPTED

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

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

user output
`99542 99728 99391 99890 99716 ...` 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: ACCEPTED

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

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

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

Test 43

Group: 3

Verdict: ACCEPTED

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

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

user output
`13 13 10 15 15 ...` Truncated

Test 44

Group: 3

Verdict: ACCEPTED

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

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

user output
`36112 6013 51073 8123 82052 ...` Truncated

Test 45

Group: 3

Verdict: ACCEPTED

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
`99407 99529 99590 99589 99679 ...` Truncated

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

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 49703 49786 49864 49720 ...` Truncated

Test 48

Group: 3

Verdict: ACCEPTED

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

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 237 49 141 57 ...` Truncated

Test 52

Group: 3

Verdict: ACCEPTED

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 2199 2351 2450 2475 ...` Truncated

Test 53

Group: 3

Verdict: ACCEPTED

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
`24841 24973 24865 24823 24969 ...` 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

Datatähti Open 2019

Sunset

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 (Diuven)