CSES - IZhO 2017, day 1

CSES - IZhO 2017, day 1 - Results

Submission details
Task:	Money
Sender:	ollpu
Submission time:	2019-02-03 12:01:11 +0200
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	9
#2	ACCEPTED	16
#3	ACCEPTED	20
#4	ACCEPTED	55

Test results
test	verdict	time	group
#1	ACCEPTED	0.02 s	1	details
#2	ACCEPTED	0.02 s	1	details
#3	ACCEPTED	0.02 s	1	details
#4	ACCEPTED	0.02 s	1	details
#5	ACCEPTED	0.02 s	1	details
#6	ACCEPTED	0.01 s	1	details
#7	ACCEPTED	0.02 s	1	details
#8	ACCEPTED	0.02 s	1	details
#9	ACCEPTED	0.01 s	1	details
#10	ACCEPTED	0.01 s	1	details
#11	ACCEPTED	0.02 s	1	details
#12	ACCEPTED	0.04 s	1	details
#13	ACCEPTED	0.01 s	1	details
#14	ACCEPTED	0.03 s	1	details
#15	ACCEPTED	0.01 s	1	details
#16	ACCEPTED	0.02 s	1	details
#17	ACCEPTED	0.03 s	2	details
#18	ACCEPTED	0.03 s	2	details
#19	ACCEPTED	0.03 s	2	details
#20	ACCEPTED	0.02 s	2	details
#21	ACCEPTED	0.02 s	2	details
#22	ACCEPTED	0.02 s	2	details
#23	ACCEPTED	0.02 s	2	details
#24	ACCEPTED	0.01 s	2	details
#25	ACCEPTED	0.03 s	2	details
#26	ACCEPTED	0.01 s	2	details
#27	ACCEPTED	0.03 s	3	details
#28	ACCEPTED	0.03 s	3	details
#29	ACCEPTED	0.02 s	3	details
#30	ACCEPTED	0.02 s	3	details
#31	ACCEPTED	0.01 s	3	details
#32	ACCEPTED	0.02 s	3	details
#33	ACCEPTED	0.01 s	3	details
#34	ACCEPTED	0.02 s	3	details
#35	ACCEPTED	0.02 s	3	details
#36	ACCEPTED	0.02 s	3	details
#37	ACCEPTED	0.02 s	3	details
#38	ACCEPTED	0.01 s	3	details
#39	ACCEPTED	0.15 s	4	details
#40	ACCEPTED	0.27 s	4	details
#41	ACCEPTED	0.13 s	4	details
#42	ACCEPTED	0.13 s	4	details
#43	ACCEPTED	0.10 s	4	details
#44	ACCEPTED	0.32 s	4	details
#45	ACCEPTED	0.31 s	4	details
#46	ACCEPTED	0.31 s	4	details
#47	ACCEPTED	0.25 s	4	details
#48	ACCEPTED	0.28 s	4	details
#49	ACCEPTED	0.77 s	4	details
#50	ACCEPTED	0.78 s	4	details
#51	ACCEPTED	0.79 s	4	details
#52	ACCEPTED	0.77 s	4	details
#53	ACCEPTED	0.78 s	4	details
#54	ACCEPTED	0.76 s	4	details
#55	ACCEPTED	1.37 s	4	details
#56	ACCEPTED	1.40 s	4	details
#57	ACCEPTED	1.38 s	4	details
#58	ACCEPTED	1.40 s	4	details
#59	ACCEPTED	1.38 s	4	details
#60	ACCEPTED	1.38 s	4	details
#61	ACCEPTED	1.39 s	4	details
#62	ACCEPTED	1.40 s	4	details

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int t[n], lc[n];
  for (int i = 0; i < n; ++i) cin >> t[i];
  lc[n-1] = 1;
  for (int i = n-2; i >= 0; --i) {
    if (t[i] <= t[i+1]) lc[i] = lc[i+1]+1;
    else lc[i] = 1;
  }
  set<int> x;
  map<int, int> cst;
  cst[0] = 1;
  vector<int> rmcst[n+1];
  rmcst[0].push_back(0);
  x.insert(2e9);
  for (int i = 0; i < n; ++i) {
    int mx = *x.upper_bound(t[i]);
    int j = upper_bound(t+i, t+i+lc[i], mx)-t;
    int tcst = cst.begin()->first+1;
    cst[tcst]++;
    rmcst[j].push_back(tcst);
    
    x.insert(t[i]);
    for (int k : rmcst[i]) {
      if (!--cst[k]) cst.erase(k);
    }
  }
  cout << cst.begin()->first << endl;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

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

correct output
`3` view save

user output
`3` view save

Test 2

Group: 1

Verdict: ACCEPTED

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

correct output
`4` view save

user output
`4` view save

Test 3

Group: 1

Verdict: ACCEPTED

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

correct output
`4` view save

user output
`4` view save

Test 4

Group: 1

Verdict: ACCEPTED

input
`6 2 3 2 3 2 3` view save

correct output
`3` view save

user output
`3` view save

Test 5

Group: 1

Verdict: ACCEPTED

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

correct output
`2` view save

user output
`2` view save

Test 6

Group: 1

Verdict: ACCEPTED

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

correct output
`3` view save

user output
`3` view save

Test 7

Group: 1

Verdict: ACCEPTED

input
`4 550483 550483 745079 243195` view save

correct output
`2` view save

user output
`2` view save

Test 8

Group: 1

Verdict: ACCEPTED

input
`8 718639 990890 718639 990890 99...` view save

correct output
`3` view save

user output
`3` view save

Test 9

Group: 1

Verdict: ACCEPTED

input
`6 75094 75094 75094 576383 16236...` view save

correct output
`3` view save

user output
`3` view save

Test 10

Group: 1

Verdict: ACCEPTED

input
`8 577594 541467 472059 277648 57...` view save

correct output
`7` view save

user output
`7` view save

Test 11

Group: 1

Verdict: ACCEPTED

input
`8 831697 182542 182542 246377 24...` view save

correct output
`4` view save

user output
`4` view save

Test 12

Group: 1

Verdict: ACCEPTED

input
`8 710010 388188 309143 388188 71...` view save

correct output
`6` view save

user output
`6` view save

Test 13

Group: 1

Verdict: ACCEPTED

input
`8 806776 806776 223756 806776 80...` view save

correct output
`2` view save

user output
`2` view save

Test 14

Group: 1

Verdict: ACCEPTED

input
`8 32911 32911 32911 32911 562837...` view save

correct output
`3` view save

user output
`3` view save

Test 15

Group: 1

Verdict: ACCEPTED

input
`8 997465 997465 968321 968321 39...` view save

correct output
`5` view save

user output
`5` view save

Test 16

Group: 1

Verdict: ACCEPTED

input
`8 468346 200735 468346 200735 88...` view save

correct output
`7` view save

user output
`7` view save

Test 17

Group: 2

Verdict: ACCEPTED

input
`15 179920 568853 179920 568853 84...` view save

correct output
`10` view save

user output
`10` view save

Test 18

Group: 2

Verdict: ACCEPTED

input
`14 626116 805032 60415 626116 388...` view save

correct output
`12` view save

user output
`12` view save

Test 19

Group: 2

Verdict: ACCEPTED

input
`10 494573 746756 237932 746756 81...` view save

correct output
`7` view save

user output
`7` view save

Test 20

Group: 2

Verdict: ACCEPTED

input
`20 371839 10893 10893 10893 98708...` view save

correct output
`11` view save

user output
`11` view save

Test 21

Group: 2

Verdict: ACCEPTED

input
`20 197220 303712 197220 389265 67...` view save

correct output
`13` view save

user output
`13` view save

Test 22

Group: 2

Verdict: ACCEPTED

input
`20 509271 509271 922019 509271 92...` view save

correct output
`6` view save

user output
`6` view save

Test 23

Group: 2

Verdict: ACCEPTED

input
`20 757151 645451 757151 757151 75...` view save

correct output
`8` view save

user output
`8` view save

Test 24

Group: 2

Verdict: ACCEPTED

input
`20 746146 385991 385991 350689 38...` view save

correct output
`11` view save

user output
`11` view save

Test 25

Group: 2

Verdict: ACCEPTED

input
`20 440622 720564 700447 459690 72...` view save

correct output
`16` view save

user output
`16` view save

Test 26

Group: 2

Verdict: ACCEPTED

input
`20 324662 468027 324662 324662 46...` view save

correct output
`14` view save

user output
`14` view save

Test 27

Group: 3

Verdict: ACCEPTED

input
`200 165 2 175 136 128 88 33 189 14...` view save

correct output
`196` view save

user output
`196` view save

Test 28

Group: 3

Verdict: ACCEPTED

input
`81 37 2 58 16 18 65 8 81 21 71 33...` view save

correct output
`77` view save

user output
`77` view save

Test 29

Group: 3

Verdict: ACCEPTED

input
`84 61 43 21 4 3 45 9 72 55 50 41 ...` view save

correct output
`80` view save

user output
`80` view save

Test 30

Group: 3

Verdict: ACCEPTED

input
`81 1 20 53 35 10 3 74 48 22 38 26...` view save

correct output
`77` view save

user output
`77` view save

Test 31

Group: 3

Verdict: ACCEPTED

input
`118 43 2 28 111 5 26 3 23 76 10 11...` view save

correct output
`110` view save

user output
`110` view save

Test 32

Group: 3

Verdict: ACCEPTED

input
`300 145507 564378 903068 564378 47...` view save

correct output
`214` view save

user output
`214` view save

Test 33

Group: 3

Verdict: ACCEPTED

input
`300 198887 496454 496454 176658 19...` view save

correct output
`180` view save

user output
`180` view save

Test 34

Group: 3

Verdict: ACCEPTED

input
`300 97004 968456 968456 968456 136...` view save

correct output
`217` view save

user output
`217` view save

Test 35

Group: 3

Verdict: ACCEPTED

input
`300 376675 480811 480811 480811 48...` view save

correct output
`78` view save

user output
`78` view save

Test 36

Group: 3

Verdict: ACCEPTED

input
`300 581370 581370 716169 581370 81...` view save

correct output
`179` view save

user output
`179` view save

Test 37

Group: 3

Verdict: ACCEPTED

input
`300 531046 550600 550600 401018 40...` view save

correct output
`258` view save

user output
`258` view save

Test 38

Group: 3

Verdict: ACCEPTED

input
`300 739447 739447 571323 571323 57...` view save

correct output
`221` view save

user output
`221` view save

Test 39

Group: 4

Verdict: ACCEPTED

input
`480481 806002 806002 621477 91785 917...` view save

correct output
`320287` view save

user output
`320287` view save

Test 40

Group: 4

Verdict: ACCEPTED

input
`788953 897530 211298 189842 844784 89...` view save

correct output
`658146` view save

user output
`658146` view save

Test 41

Group: 4

Verdict: ACCEPTED

input
`388796 806119 739351 66427 113886 113...` view save

correct output
`232110` view save

user output
`232110` view save

Test 42

Group: 4

Verdict: ACCEPTED

input
`343838 199431 288483 635849 288483 68...` view save

correct output
`297964` view save

user output
`297964` view save

Test 43

Group: 4

Verdict: ACCEPTED

input
`242351 818489 249811 887102 290660 88...` view save

correct output
`211988` view save

user output
`211988` view save

Test 44

Group: 4

Verdict: ACCEPTED

input
`1000000 738237 738237 893082 490298 43...` view save

correct output
`777569` view save

user output
`777569` view save

Test 45

Group: 4

Verdict: ACCEPTED

input
`1000000 74304 74304 74304 325602 71262...` view save

correct output
`714524` view save

user output
`714524` view save

Test 46

Group: 4

Verdict: ACCEPTED

input
`1000000 254366 875788 564327 564327 43...` view save

correct output
`777558` view save

user output
`777558` view save

Test 47

Group: 4

Verdict: ACCEPTED

input
`1000000 937517 114387 114387 114387 93...` view save

correct output
`249890` view save

user output
`249890` view save

Test 48

Group: 4

Verdict: ACCEPTED

input
`1000000 814027 682934 214670 214670 81...` view save

correct output
`500240` view save

user output
`500240` view save

Test 49

Group: 4

Verdict: ACCEPTED

input
`1000000 717896 297551 254872 297551 61...` view save

correct output
`833179` view save

user output
`833179` view save

Test 50

Group: 4

Verdict: ACCEPTED

input
`1000000 563974 664553 563974 609181 56...` view save

correct output
`750197` view save

user output
`750197` view save

Test 51

Group: 4

Verdict: ACCEPTED

input
`1000000 173690 978648 978648 978648 90...` view save

correct output
`874390` view save

user output
`874390` view save

Test 52

Group: 4

Verdict: ACCEPTED

input
`1000000 785890 785890 785890 785890 78...` view save

correct output
`750316` view save

user output
`750316` view save

Test 53

Group: 4

Verdict: ACCEPTED

input
`1000000 119439 119439 119439 354111 73...` view save

correct output
`798579` view save

user output
`798579` view save

Test 54

Group: 4

Verdict: ACCEPTED

input
`1000000 749078 95090 749078 276834 950...` view save

correct output
`750593` view save

user output
`750593` view save

Test 55

Group: 4

Verdict: ACCEPTED

input
`1000000 137937 689287 749751 213838 32...` view save

correct output
`981871` view save

user output
`981871` view save

Test 56

Group: 4

Verdict: ACCEPTED

input
`1000000 473653 274191 673488 575890 73...` view save

correct output
`981543` view save

user output
`981543` view save

Test 57

Group: 4

Verdict: ACCEPTED

input
`1000000 913583 648901 29748 168104 439...` view save

correct output
`981717` view save

user output
`981717` view save

Test 58

Group: 4

Verdict: ACCEPTED

input
`1000000 890981 682430 885587 406305 60...` view save

correct output
`981788` view save

user output
`981788` view save

Test 59

Group: 4

Verdict: ACCEPTED

input
`1000000 1 2 247847 4 767575 281751 982...` view save

correct output
`981660` view save

user output
`981660` view save

Test 60

Group: 4

Verdict: ACCEPTED

input
`1000000 285138 720188 820135 821835 91...` view save

correct output
`982003` view save

user output
`982003` view save

Test 61

Group: 4

Verdict: ACCEPTED

input
`1000000 421947 680547 224842 941720 26...` view save

correct output
`981663` view save

user output
`981663` view save

Test 62

Group: 4

Verdict: ACCEPTED

input
`1000000 963500 2 664028 4 692637 80284...` view save

correct output
`981624` view save

user output
`981624` view save

IZhO 2017, day 1

Money

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

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Test 62

Tasks

Submissions (ollpu)