CSES - Datatähti Open 2019 - Results
Submission details
Task:Sunset
Sender:MoNsTeR_CuBe
Submission time:2019-01-21 19:14:52 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1details
#2ACCEPTED0.01 s1details
#3ACCEPTED0.03 s1details
#4ACCEPTED0.02 s1details
#50.02 s1details
#60.02 s1details
#7ACCEPTED0.02 s1details
#80.02 s1details
#9ACCEPTED0.03 s1details
#10ACCEPTED0.02 s1details
#11ACCEPTED0.02 s1details
#120.02 s1details
#130.02 s1details
#14ACCEPTED0.03 s1details
#150.02 s1details
#160.03 s1details
#170.02 s1details
#18ACCEPTED0.01 s2details
#190.29 s2details
#200.29 s2details
#21ACCEPTED0.28 s2details
#220.28 s2details
#23ACCEPTED0.28 s2details
#240.30 s2details
#250.26 s2details
#260.29 s2details
#270.29 s2details
#28ACCEPTED0.01 s2details
#290.28 s2details
#300.28 s2details
#310.28 s2details
#32ACCEPTED0.02 s3details
#330.31 s3details
#340.30 s3details
#350.31 s3details
#36ACCEPTED0.29 s3details
#370.29 s3details
#38ACCEPTED0.31 s3details
#390.28 s3details
#40ACCEPTED0.30 s3details
#410.30 s3details
#42ACCEPTED0.29 s3details
#430.30 s3details
#44ACCEPTED0.32 s3details
#45ACCEPTED0.30 s3details
#46ACCEPTED0.29 s3details
#470.29 s3details
#480.29 s3details
#490.28 s3details
#500.28 s3details
#510.29 s3details
#52ACCEPTED0.29 s3details
#530.28 s3details
#540.29 s3details

Compiler report

input/code.cpp: In function 'long long int sign(long long int)':
input/code.cpp:13:82: warning: control reaches end of non-void function [-Wreturn-type]
 int sign(int a){if(a < 0){ return -1;}if(a == 0) {return 0;}if(a > 0) {return 1;}}
                                                                                  ^

Code

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define INF 9223372036854775807
#define M_PI 3.14159265358979323846
#define double long double

int mod = 1000000007;

int fastPow(int b, int e){int r = 1;while(e){if(e%2 == 1){r*=b;r%=mod;}b*=b;b%=mod;e/=2;}return r;}
int pgcd(int a, int b){ if(a%b == 0) return b; else return pgcd(b, a%b);}
int sign(int a){if(a < 0){ return -1;}if(a == 0) {return 0;}if(a > 0) {return 1;}}
bool isPrime(int a){if(a == 1) {return false;}int f = sqrt(a);for(int i = 2; i<=f; i++){if(a%i == 0){return false;}}return true;}
int toInt(string s){int tot = 0;for(int i = s.size()-1; i >= 0; i--){tot+=((s[i]-'0')%mod)*fastPow(10,i);tot%=mod;}return tot;}
string toString(int a){string s = "";while(a){s = (char)('0'+a%10) + s;a/=10;}return s;}

int bs(vector<int> &v, int x){

    int l = 0;
    int r = v.size()-1;
    while(l < r){
        int mid = (l+r)/2;
        if(v[mid] > x){
            l = mid+1;
        }else if(v[mid] < x){
            r = mid-1;
        }else{
            return v.size()-mid;
        }
    }
    //cout << "REP " << r << endl;
    return v.size()-r;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    vector< tuple<int, int, int> > ve;
    vector<int> ans(q);
    for(int i = 0; i < q; i++){
        int a, b;
        cin >> a >> b;
        ve.push_back(make_tuple(a,b,i));
    }
    sort(ve.begin(), ve.end());
    vector< int > stacke(0);
    vector< int > sIndex(0);
    for(int i = n-1; i >= 0; i--){
        while(!stacke.empty() && stacke.back() <= v[i]){
            stacke.pop_back();
            sIndex.pop_back();
        }
        //if(!stacke.empty())cout << "Stack " << ' ' << i << ' ' << stacke.back() << endl;
        stacke.push_back(v[i]);
        sIndex.push_back(i);
        while(!ve.empty() && get<0>(ve.back())-1 == i){
            int rep = bs(sIndex, get<1>(ve.back())-1);
            ans[get<2>(ve.back())] = rep;
            ve.pop_back();
        }
    }
    for(int a : ans) cout << a << endl;
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

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

correct output
1
3
1

user output
1
3
1

Test 2

Group: 1

Verdict: ACCEPTED

input
1 1
1
1 1

correct output
1

user output
1

Test 3

Group: 1

Verdict: ACCEPTED

input
2 3
1 1000000000
1 1
2 2
1 2

correct output
1
1
2

user output
1
1
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
15
10
10
3
7
...

Test 6

Group: 1

Verdict:

input
2000 2000
13604803 27447643 34139694 383...

correct output
198
43
38
58
50
...

user output
199
43
39
58
51
...

Test 7

Group: 1

Verdict: ACCEPTED

input
2000 2000
387547790 498212511 224378606 ...

correct output
1
1
1
1
1
...

user output
1
1
1
1
1
...

Test 8

Group: 1

Verdict:

input
2000 2000
409666302 646936685 583741760 ...

correct output
8
9
12
8
11
...

user output
8
9
13
8
12
...

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

input
2000 2000
785263 793567 1573404 1750090 ...

correct output
1960
1947
1963
1942
1944
...

user output
1960
1947
1963
1942
1944
...

Test 12

Group: 1

Verdict:

input
1999 2000
129087461 494922181 482953911 ...

correct output
10
6
6
7
7
...

user output
10
6
7
8
8
...

Test 13

Group: 1

Verdict:

input
2000 2000
409666302 646936685 583741760 ...

correct output
8
7
6
7
7
...

user output
8
7
7
8
7
...

Test 14

Group: 1

Verdict: ACCEPTED

input
2000 2000
44989 1437234 1640005 1765235 ...

correct output
1233
1389
1026
150
796
...

user output
1233
1389
1026
150
796
...

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
988
994
982
979
973
...

Test 16

Group: 1

Verdict:

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

correct output
1
2
1
1
2
...

user output
1
3
1
1
3
...

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
1
1
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
4
9
7
6
4
...

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
89
35
60
26
13
...

Test 21

Group: 2

Verdict: ACCEPTED

input
100000 200000
32 22 35 59 37 2 5 5 79 53 22 ...

correct output
1
1
1
1
1
...

user output
1
1
1
1
1
...

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

Test 23

Group: 2

Verdict: ACCEPTED

input
100000 200000
100 100 100 100 100 100 100 10...

correct output
1
1
1
1
1
...

user output
1
1
1
1
1
...

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

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

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

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
7
4
9
3
6
...

Test 28

Group: 2

Verdict: ACCEPTED

input
5 1
4 1 5 6 9
1 3

correct output
2

user output
2

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
44
4
28
46
30
...

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

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
39
10
37
20
43
...

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
9
7
9
10
5
...

Test 34

Group: 3

Verdict:

input
100000 200000
138644593 592364551 919805093 ...

correct output
10
11
13
7
12
...

user output
10
12
14
8
13
...

Test 35

Group: 3

Verdict:

input
100000 200000
10770 195579 349462 442791 450...

correct output
2468
1986
2632
129
4010
...

user output
2468
1987
2632
129
4011
...

Test 36

Group: 3

Verdict: ACCEPTED

input
100000 200000
994198482 687493351 579440176 ...

correct output
1
2
1
2
1
...

user output
1
2
1
2
1
...

Test 37

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...

correct output
15
13
16
11
17
...

user output
15
14
16
12
17
...

Test 38

Group: 3

Verdict: ACCEPTED

input
100000 200000
1000000000 1000000000 10000000...

correct output
1
1
1
1
1
...

user output
1
1
1
1
1
...

Test 39

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...

correct output
10
16
7
18
10
...

user output
10
16
7
18
10
...

Test 40

Group: 3

Verdict: ACCEPTED

input
100000 200000
11465 15800 19042 19282 20348 ...

correct output
99542
99728
99391
99890
99716
...

user output
99542
99728
99391
99890
99716
...

Test 41

Group: 3

Verdict:

input
99999 200000
587542096 890780320 258438313 ...

correct output
8
6
11
11
17
...

user output
8
7
11
12
18
...

Test 42

Group: 3

Verdict: ACCEPTED

input
100000 200000
11283 24634 28852 37453 37625 ...

correct output
100000
100000
100000
100000
100000
...

user output
100000
100000
100000
100000
100000
...

Test 43

Group: 3

Verdict:

input
100000 200000
398809514 622635167 133376912 ...

correct output
13
13
10
15
15
...

user output
14
13
10
15
15
...

Test 44

Group: 3

Verdict: ACCEPTED

input
100000 200000
11465 15800 19042 19282 20348 ...

correct output
36112
6013
51073
8123
82052
...

user output
36112
6013
51073
8123
82052
...

Test 45

Group: 3

Verdict: ACCEPTED

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

Test 46

Group: 3

Verdict: ACCEPTED

input
100000 200000
100000 99999 99998 99997 99996...

correct output
1
1
1
1
1
...

user output
1
1
1
1
1
...

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

Test 48

Group: 3

Verdict:

input
100000 200000
99999 100000 99997 99998 99995...

correct output
2
1
2
2
1
...

user output
3
1
3
3
1
...

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

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
19
24
3
21
4
...

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
113
238
50
141
58
...

Test 52

Group: 3

Verdict: ACCEPTED

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

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
24842
24974
24866
24824
24970
...

Test 54

Group: 3

Verdict:

input
100000 200000
49999 50000 49997 49998 49995 ...

correct output
210
1
2
2
1
...

user output
210
1
3
3
1
...