CSES - Datatähti 2019 loppu

CSES - Datatähti 2019 loppu - Results

Submission details
Task:	Auringonlasku
Sender:	Olli Järviniemi
Submission time:	2019-01-17 16:59:06 +0200
Language:	C++
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0
#2	WRONG ANSWER	0
#3	RUNTIME ERROR	0

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

Code

#include <random>
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
#include <set>


using namespace std;


vector<int> v;

const int N = 1e5 + 5;
const int M = 131072;

typedef long long ll;
typedef pair<int, int> pii;

int t[2*M];
int h[N];

int ma(int a, int b) {
    a+=M;
    b+=M;
    int maa = -1;
    while(a <= b) {
        if(a%2 == 1) {
            maa = max(maa, t[a]);
            ++a;
        }
        if(b%2 == 0) {
            maa = max(maa, t[b]);
            --b;
        }
        a/=2; b/=2;
    }
    return maa;
}

void init() {
    for(int i = M-1; i >= 1; --i) {
        t[i] = max(t[2*i], t[2*i + 1]);
    }
    
}

int a[N];


vector<pair<pii, int> > que;

vector<int> sor[5000];

int root;
int n;
int amo(int i, int c) {
    //Amount of numbers in sor[i] below c
    
    int x = root*i - 1;
    for(int b = 12; b >= 0; --b) {
        int nx = x + (1<<b);
        if(nx >= min(root*i + root, n)) continue;
        if(sor[i][nx - root*i] >= c) continue;
        x = nx;
    }
    return x - root*i + 1;
}


ll su[N][111];

int main() {
    iostream::sync_with_stdio(false);
    cin.tie(0);
    
    int q;
    cin >> n >> q;
    for(int i = 0; i < n; ++i) {
        int hh;
        cin >> hh;
        v.push_back(hh);
        t[i+M] = hh;
        h[i] = hh;
    }
    init();
    
    for(int i = 0; i < n; ++i) {
        if(ma(0, i-1) < h[i]) {
            a[i] = -1;
            continue;
        }
        int aa = 0;
        int b = i-1;
        while(aa < b) {
            int mid = (aa+b)/2;
            if(ma(mid+1, b) >= h[i]) {
                aa = mid+1;
            } else {
                b = mid;
            }
        }
        a[i] = aa;
    }

    
    if(n <= 2000) {
        root = 4*sqrt(n);
        int am = (n+root-1)/root;
        
        
        for(int i = 0; i < am; ++i) {
            for(int j = root*i; j < root*i + root; ++j) {
                    sor[i].push_back(a[j]);
            }
            sort(sor[i].begin(), sor[i].end());
        }
        
        
        for(int i = 0; i < q; ++i) {
            int aa, b;
            cin >> aa >> b;
            aa = 1; b = n;
            --aa;
            --b;
            int lowI = aa/root;
            int highI = b/root;
            int ans = 0;
            if(lowI == highI) {
                for(int j = aa; j <= b; ++j) {
                    if(a[j] < aa) ++ans;
                }
              cout << ans << "\n";
                continue;
            }
        for(int j = lowI + 1; j < highI; ++j) {
                ans += amo(j, aa);
            }
            
            for(int j = aa; j < lowI*root + root; ++j) {
                if(a[j] < aa) ++ans;
            }
            
            for(int j = highI*root; j <= b; ++j) {
                if(a[j] < aa) ++ans;
            }
            cout << ans << "\n";
            
        }
    } else {
        set<int> s[111];
        for(int i = n; i >= 1; --i) {
            h[i] = h[i-1];
            s[h[i]].insert(i);
        }
        return 0;
        

        for(int i = 1; i <= q; ++i) {
            int a, b;
            cin >> a >> b;
            int ans = 0;
            for(int j = 100; j >= 1; --j) {
                set<int>::iterator it = s[j].lower_bound(a);
                if(it == s[j].end()) continue;
                if(*it > b) continue;
                ++ans;
                b = *it;
            }
            cout << ans << "\n";
        }
        
        
    }
    
    
    
}

Test details

Test 1

Group: 1

Verdict: WRONG ANSWER

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 1 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: WRONG ANSWER

input
`2 3 1 1000000000 1 1 2 2 1 2` view save

correct output
`1 1 2` view save

user output
`2 2 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: WRONG ANSWER

input
`2000 2000 387547790 498212511 224378606 ...` view save

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

user output
`14 14 14 14 14 ...` Truncated

Test 6

Group: 1

Verdict: WRONG ANSWER

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

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

user output
`202 202 202 202 202 ...` Truncated

Test 7

Group: 1

Verdict: WRONG ANSWER

input
`2000 2000 387547790 498212511 224378606 ...` view save

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

user output
`14 14 14 14 14 ...` Truncated

Test 8

Group: 1

Verdict: WRONG ANSWER

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

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

user output
`9 9 9 9 9 ...` 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: WRONG ANSWER

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

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

user output
`2000 2000 2000 2000 2000 ...` Truncated

Test 12

Group: 1

Verdict: WRONG ANSWER

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

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

user output
`11 11 11 11 11 ...` Truncated

Test 13

Group: 1

Verdict: WRONG ANSWER

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

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

user output
`9 9 9 9 9 ...` Truncated

Test 14

Group: 1

Verdict: WRONG ANSWER

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

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

user output
`2000 2000 2000 2000 2000 ...` Truncated

Test 15

Group: 1

Verdict: WRONG ANSWER

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
`1000 1000 1000 1000 1000 ...` Truncated

Test 16

Group: 1

Verdict: WRONG ANSWER

input
`2000 2000 1999 2000 1997 1998 1995 1996 ...` view save

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

user output
`2 2 2 2 2 ...` Truncated

Test 17

Group: 1

Verdict: WRONG ANSWER

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
`3 3 3 3 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: WRONG ANSWER

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: WRONG ANSWER

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: WRONG ANSWER

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: WRONG ANSWER

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: WRONG ANSWER

input
`100000 200000 100 100 100 100 100 100 100 10...` view save

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

user output
(empty)

Test 24

Group: 2

Verdict: WRONG ANSWER

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: WRONG ANSWER

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: WRONG ANSWER

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: WRONG ANSWER

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: WRONG ANSWER

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

correct output
`2` view save

user output
`4` view save

Test 29

Group: 2

Verdict: WRONG ANSWER

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: WRONG ANSWER

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: WRONG ANSWER

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

input
`1 1 1 1 1` view save

correct output
`1` view save

user output
`1` view save

Test 33

Group: 3

Verdict: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

input
`100000 200000 1000000000 1000000000 10000000...` view save

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

user output
(empty)

Test 39

Group: 3

Verdict: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

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: RUNTIME ERROR

input
`100000 200000 99999 100000 99997 99998 99995...` view save

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

user output
(empty)

Test 49

Group: 3

Verdict: WRONG ANSWER

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: WRONG ANSWER

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: RUNTIME ERROR

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: RUNTIME ERROR

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

Test 53

Group: 3

Verdict: RUNTIME ERROR

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: RUNTIME ERROR

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

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

user output
(empty)

Datatähti 2019 loppu

Auringonlasku

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 (Olli Järviniemi)