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
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#10.01 s1details
#2ACCEPTED0.02 s1details
#30.01 s1details
#4ACCEPTED0.02 s1details
#50.03 s1details
#60.02 s1details
#70.02 s1details
#80.02 s1details
#9ACCEPTED0.01 s1details
#10ACCEPTED0.02 s1details
#110.02 s1details
#120.03 s1details
#130.02 s1details
#140.03 s1details
#150.02 s1details
#160.02 s1details
#170.02 s1details
#18ACCEPTED0.01 s2details
#190.17 s2details
#200.15 s2details
#210.17 s2details
#220.18 s2details
#230.17 s2details
#240.17 s2details
#250.18 s2details
#260.18 s2details
#270.17 s2details
#280.02 s2details
#290.16 s2details
#300.17 s2details
#310.18 s2details
#32ACCEPTED0.02 s3details
#330.15 s3details
#340.17 s3details
#350.14 s3details
#360.15 s3details
#370.15 s3details
#380.14 s3details
#390.15 s3details
#400.05 s3details
#410.15 s3details
#420.06 s3details
#430.15 s3details
#440.06 s3details
#450.05 s3details
#460.14 s3details
#470.10 s3details
#480.15 s3details
#490.17 s3details
#500.16 s3details
#510.14 s3details
#520.15 s3details
#530.12 s3details
#540.14 s3details

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:

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

correct output
1
3
1

user output
1
1
1

Test 2

Group: 1

Verdict: ACCEPTED

input
1 1
1
1 1

correct output
1

user output
1

Test 3

Group: 1

Verdict:

input
2 3
1 1000000000
1 1
2 2
1 2

correct output
1
1
2

user output
2
2
2

Test 4

Group: 1

Verdict: ACCEPTED

input
2 3
1000000000 1
1 1
2 2
1 2

correct output
1
1
1

user output
1
1
1

Test 5

Group: 1

Verdict:

input
2000 2000
387547790 498212511 224378606 ...

correct output
14
10
10
3
7
...

user output
14
14
14
14
14
...

Test 6

Group: 1

Verdict:

input
2000 2000
13604803 27447643 34139694 383...

correct output
198
43
38
58
50
...

user output
202
202
202
202
202
...

Test 7

Group: 1

Verdict:

input
2000 2000
387547790 498212511 224378606 ...

correct output
1
1
1
1
1
...

user output
14
14
14
14
14
...

Test 8

Group: 1

Verdict:

input
2000 2000
409666302 646936685 583741760 ...

correct output
8
9
12
8
11
...

user output
9
9
9
9
9
...

Test 9

Group: 1

Verdict: ACCEPTED

input
2000 2000
1000000000 1000000000 10000000...

correct output
1
1
1
1
1
...

user output
1
1
1
1
1
...

Test 10

Group: 1

Verdict: ACCEPTED

input
2000 2000
785263 793567 1573404 1750090 ...

correct output
2000
2000
2000
2000
2000
...

user output
2000
2000
2000
2000
2000
...

Test 11

Group: 1

Verdict:

input
2000 2000
785263 793567 1573404 1750090 ...

correct output
1960
1947
1963
1942
1944
...

user output
2000
2000
2000
2000
2000
...

Test 12

Group: 1

Verdict:

input
1999 2000
129087461 494922181 482953911 ...

correct output
10
6
6
7
7
...

user output
11
11
11
11
11
...

Test 13

Group: 1

Verdict:

input
2000 2000
409666302 646936685 583741760 ...

correct output
8
7
6
7
7
...

user output
9
9
9
9
9
...

Test 14

Group: 1

Verdict:

input
2000 2000
44989 1437234 1640005 1765235 ...

correct output
1233
1389
1026
150
796
...

user output
2000
2000
2000
2000
2000
...

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

Test 16

Group: 1

Verdict:

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

correct output
1
2
1
1
2
...

user output
2
2
2
2
2
...

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

Test 18

Group: 2

Verdict: ACCEPTED

input
1 1
1
1 1

correct output
1

user output
1

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

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

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

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

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

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

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

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

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

Test 28

Group: 2

Verdict:

input
5 1
4 1 5 6 9
1 3

correct output
2

user output
4

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

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

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

Test 32

Group: 3

Verdict: ACCEPTED

input
1 1
1
1 1

correct output
1

user output
1

Test 33

Group: 3

Verdict:

input
100000 200000
994198482 687493351 579440176 ...

correct output
8
6
8
10
5
...

user output
(empty)

Test 34

Group: 3

Verdict:

input
100000 200000
138644593 592364551 919805093 ...

correct output
10
11
13
7
12
...

user output
(empty)

Test 35

Group: 3

Verdict:

input
100000 200000
10770 195579 349462 442791 450...

correct output
2468
1986
2632
129
4010
...

user output
(empty)

Test 36

Group: 3

Verdict:

input
100000 200000
994198482 687493351 579440176 ...

correct output
1
2
1
2
1
...

user output
(empty)

Test 37

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...

correct output
15
13
16
11
17
...

user output
(empty)

Test 38

Group: 3

Verdict:

input
100000 200000
1000000000 1000000000 10000000...

correct output
1
1
1
1
1
...

user output
(empty)

Test 39

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...

correct output
10
16
7
18
10
...

user output
(empty)

Test 40

Group: 3

Verdict:

input
100000 200000
11465 15800 19042 19282 20348 ...

correct output
99542
99728
99391
99890
99716
...

user output
(empty)

Test 41

Group: 3

Verdict:

input
99999 200000
587542096 890780320 258438313 ...

correct output
8
6
11
11
17
...

user output
(empty)

Test 42

Group: 3

Verdict:

input
100000 200000
11283 24634 28852 37453 37625 ...

correct output
100000
100000
100000
100000
100000
...

user output
(empty)

Test 43

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...

correct output
13
13
10
15
15
...

user output
(empty)

Test 44

Group: 3

Verdict:

input
100000 200000
11465 15800 19042 19282 20348 ...

correct output
36112
6013
51073
8123
82052
...

user output
(empty)

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

Test 46

Group: 3

Verdict:

input
100000 200000
100000 99999 99998 99997 99996...

correct output
1
1
1
1
1
...

user output
(empty)

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

Test 48

Group: 3

Verdict:

input
100000 200000
99999 100000 99997 99998 99995...

correct output
2
1
2
2
1
...

user output
(empty)

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

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

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

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

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

Test 54

Group: 3

Verdict:

input
100000 200000
49999 50000 49997 49998 49995 ...

correct output
210
1
2
2
1
...

user output
(empty)