— Dark mode

Datatähti Open 2019

Sunset

  • Start: N/A
  • End: N/A
CSES - Datatähti Open 2019 - Results
Submission details
Task:Sunset
Sender:jdnkjasska
Submission time:2019-01-19 21:05:45 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.03 s1details
#20.03 s1details
#3ACCEPTED0.02 s1details
#4ACCEPTED0.02 s1details
#50.02 s1details
#60.01 s1details
#70.02 s1details
#80.02 s1details
#9ACCEPTED0.02 s1details
#100.02 s1details
#110.02 s1details
#120.03 s1details
#130.02 s1details
#140.01 s1details
#150.02 s1details
#16ACCEPTED0.02 s1details
#170.01 s1details
#180.01 s2details
#190.05 s2details
#200.05 s2details
#210.06 s2details
#220.05 s2details
#23ACCEPTED0.10 s2details
#240.04 s2details
#250.05 s2details
#260.05 s2details
#270.05 s2details
#280.02 s2details
#290.04 s2details
#300.04 s2details
#310.04 s2details
#320.02 s3details
#330.07 s3details
#340.08 s3details
#350.06 s3details
#360.08 s3details
#370.09 s3details
#38ACCEPTED0.11 s3details
#390.07 s3details
#400.07 s3details
#410.07 s3details
#420.07 s3details
#430.07 s3details
#440.07 s3details
#450.06 s3details
#460.06 s3details
#470.06 s3details
#48ACCEPTED0.11 s3details
#490.05 s3details
#500.05 s3details
#510.05 s3details
#52ACCEPTED0.13 s3details
#530.08 s3details
#540.06 s3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &N, &Q);
   ~~~~~^~~~~~~~~~~~~~~~
input/code.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &H[i]);
     ~~~~~^~~~~~~~~~~~~
input/code.cpp:59:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int l, r; scanf("%d%d", &l, &r);
               ~~~~~^~~~~~~~~~~~~~~~

Code

#include<bits/stdc++.h>

using namespace std;
using lint = long long;

int N, Q;
int H[int(1.1e5)];
int A[int(1.1e5)], M;

const int LEAF = 1<<18;
int tree[LEAF+LEAF];

void upd(int x, int v) {
  tree[x += LEAF] = v;
  while(x >>= 1) tree[x] = min(tree[x+x], tree[x+x+1]);
}

int get(int l, int r) {
  l += LEAF; r += LEAF;
  int ret = 2e9;
  while(l <= r) {
    if( l & 1) ret = min(ret, tree[l]);
    if(~r & 1) ret = min(ret, tree[r]);
    l = (l+1) >> 1;
    r = (r-1) >> 1;
  }
  return ret;
}

int par[18][int(1.1e5)];

int main() {
  scanf("%d%d", &N, &Q);
  for(int i = 1; i <= N; i++) {
    scanf("%d", &H[i]);
    A[i] = H[i];
  }
  sort(A+1, A+N+1);
  M = distance(A, unique(A+1, A+N+1));
  for(int i = 1; i <= N; i++) {
    H[i] = distance(A, lower_bound(A+1, A+M+1, H[i]));
  }

  fill(tree, tree+LEAF+LEAF, N+1);
  
  for(int i = N; i > 0; i--) {
    par[0][i] = get(H[i]+1, M);
    upd(H[i], i);
  }
  
  par[0][N+1] = N+1;
  for(int k = 1; k < 18; k++) {
    for(int i = 1; i <= N+1; i++) {
      par[k][i] = par[k-1][par[k-1][i]];
    }
  }

  for(int q = 0; q < Q; q++) {
    int l, r; scanf("%d%d", &l, &r);
    int ans = 1;
    l = par[0][l];
    for(int k = 17; k >= 0; k--) {
      //printf("%d %d %d\n", k, l, par[k][l]);
      if(par[k][l] <= r) {
        ans += 1<<k;
        l = par[k][l];
      }
    }
    if(l <= r) {
      ans += 1;
    }
    printf("%d\n", ans);
  }

  
  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:

input
1 1
1
1 1
view save

correct output
1
view save

user output
(empty)

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

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

Test 7

Group: 1

Verdict:

input
2000 2000
387547790 498212511 224378606 ...
view save

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

user output
(empty)

Test 8

Group: 1

Verdict:

input
2000 2000
409666302 646936685 583741760 ...
view save

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

user output
(empty)

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

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

Test 12

Group: 1

Verdict:

input
1999 2000
129087461 494922181 482953911 ...
view save

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

user output
(empty)

Test 13

Group: 1

Verdict:

input
2000 2000
409666302 646936685 583741760 ...
view save

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

user output
(empty)

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

Test 15

Group: 1

Verdict:

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

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:

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

Test 18

Group: 2

Verdict:

input
1 1
1
1 1
view save

correct output
1
view save

user output
(empty)

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

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

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

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

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

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

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

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

Test 28

Group: 2

Verdict:

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

correct output
2
view save

user output
(empty)

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

Test 30

Group: 2

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

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

Test 32

Group: 3

Verdict:

input
1 1
1
1 1
view save

correct output
1
view save

user output
(empty)

Test 33

Group: 3

Verdict:

input
100000 200000
994198482 687493351 579440176 ...
view save

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

user output
(empty)

Test 34

Group: 3

Verdict:

input
100000 200000
138644593 592364551 919805093 ...
view save

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

user output
(empty)

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

Test 36

Group: 3

Verdict:

input
100000 200000
994198482 687493351 579440176 ...
view save

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

user output
(empty)

Test 37

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...
view save

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

user output
(empty)

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

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

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

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:

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

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

user output
(empty)

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

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:

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

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

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

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:

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:

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

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

user output
(empty)

Tasks

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

Submissions (jdnkjasska)

0:27:56 1000:23:49 00:22:46 0