CSES - Datatähti Open 2019 - Results
Submission details
Task:Sunset
Sender:egor.lifar
Submission time:2019-01-20 13:38:47 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED16
#2ACCEPTED35
#3ACCEPTED49
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1details
#2ACCEPTED0.03 s1details
#3ACCEPTED0.03 s1details
#4ACCEPTED0.03 s1details
#5ACCEPTED0.02 s1details
#6ACCEPTED0.03 s1details
#7ACCEPTED0.03 s1details
#8ACCEPTED0.03 s1details
#9ACCEPTED0.03 s1details
#10ACCEPTED0.03 s1details
#11ACCEPTED0.03 s1details
#12ACCEPTED0.04 s1details
#13ACCEPTED0.03 s1details
#14ACCEPTED0.03 s1details
#15ACCEPTED0.04 s1details
#16ACCEPTED0.03 s1details
#17ACCEPTED0.03 s1details
#18ACCEPTED0.02 s2details
#19ACCEPTED0.33 s2details
#20ACCEPTED0.33 s2details
#21ACCEPTED0.19 s2details
#22ACCEPTED0.22 s2details
#23ACCEPTED0.22 s2details
#24ACCEPTED0.27 s2details
#25ACCEPTED0.14 s2details
#26ACCEPTED0.33 s2details
#27ACCEPTED0.33 s2details
#28ACCEPTED0.03 s2details
#29ACCEPTED0.22 s2details
#30ACCEPTED0.22 s2details
#31ACCEPTED0.23 s2details
#32ACCEPTED0.03 s3details
#33ACCEPTED0.36 s3details
#34ACCEPTED0.35 s3details
#35ACCEPTED0.33 s3details
#36ACCEPTED0.19 s3details
#37ACCEPTED0.23 s3details
#38ACCEPTED0.22 s3details
#39ACCEPTED0.29 s3details
#40ACCEPTED0.24 s3details
#41ACCEPTED0.36 s3details
#42ACCEPTED0.15 s3details
#43ACCEPTED0.36 s3details
#44ACCEPTED0.36 s3details
#45ACCEPTED0.25 s3details
#46ACCEPTED0.22 s3details
#47ACCEPTED0.24 s3details
#48ACCEPTED0.21 s3details
#49ACCEPTED0.22 s3details
#50ACCEPTED0.23 s3details
#51ACCEPTED0.22 s3details
#52ACCEPTED0.22 s3details
#53ACCEPTED0.25 s3details
#54ACCEPTED0.24 s3details

Code

/*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
*/
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <array>
       
        
using namespace std;
template<typename T1, typename T2>inline void chkmin(T1 &x, T2 y) { if (x > y) x = y; }
template<typename T1, typename T2>inline void chkmax(T1 &x, T2 y) { if (x < y) x = y; } 
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const pair<T, U> &_p) { _out << _p.first << ' ' << _p.second; return _out; }
template<typename T, typename U> inline istream &operator>> (istream &_in, pair<T, U> &_p) { _in >> _p.first >> _p.second; return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const vector<T> &_v) { if (_v.empty()) { return _out; } _out << _v.front(); for (auto _it = ++_v.begin(); _it != _v.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline istream &operator>> (istream &_in, vector<T> &_v) { for (auto &_i : _v) { _in >> _i; } return _in; }
template<typename T> inline ostream &operator<< (ostream &_out, const set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_set<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T> inline ostream &operator<< (ostream &_out, const unordered_multiset<T> &_s) { if (_s.empty()) { return _out; } _out << *_s.begin(); for (auto _it = ++_s.begin(); _it != _s.end(); ++_it) { _out << ' ' << *_it; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
template<typename T, typename U> inline ostream &operator<< (ostream &_out, const unordered_map<T, U> &_m) { if (_m.empty()) { return _out; } _out << '(' << _m.begin()->first << ": " << _m.begin()->second << ')'; for (auto _it = ++_m.begin(); _it != _m.end(); ++_it) { _out << ", (" << _it->first << ": " << _it->second << ')'; } return _out; }
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define left left228
#define right right228
#define rank rank228
#define y1 y1228                                                         
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define files(FILENAME) read(FILENAME), write(FILENAME)
#define pb push_back
const string FILENAME = "input";
const int MAXN = 100228;


int n;
int h[MAXN];
int kek[MAXN];
vector<int> st[MAXN * 4];
int q;


int rmq(int v, int vl, int vr, int l, int r) {
    if (vl > r || vr < l) {
        return 0;
    }
    if (l <= vl && vr <= r) {
        return lower_bound(all(st[v]), l - 1) - st[v].begin();
    }
    return rmq(v * 2, vl, (vl + vr) / 2, l, r) + rmq(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //read(FILENAME);
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    vector<int> sts;
    for (int i = 0; i < n; i++) {
        while (!sts.empty() && h[sts.back()] < h[i]) {
            sts.pop_back();
        }
        kek[i] = (sts.empty() ? -1: sts.back()); 
        sts.pb(i);
    }
    int ss = 1;
    while (ss < n) {
        ss <<= 1;
    }
    for (int i = 0; i < n; i++) {
        st[ss + i].pb(kek[i]);
    }
    for (int i = ss - 1; i >= 1; i--) {
        if (st[i * 2].empty() && st[i * 2 + 1].empty()) {
            continue;
        }
        if (st[i * 2].empty()) {
            st[i] = st[i * 2 + 1];
            continue;
        }
        if (st[i * 2 + 1].empty()) {
            st[i] = st[i * 2];
            continue;
        }
        st[i].resize(sz(st[i * 2]) + sz(st[i * 2 + 1]));
        merge(all(st[i * 2]), all(st[i * 2 + 1]), st[i].begin());
    }
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << rmq(1, 1, ss, l, r) << '\n';
    }
    return 0;       
}

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

input
2000 2000
387547790 498212511 224378606 ...

correct output
14
10
10
3
7
...

user output
14
10
10
3
7
...
Truncated

Test 6

Group: 1

Verdict: ACCEPTED

input
2000 2000
13604803 27447643 34139694 383...

correct output
198
43
38
58
50
...

user output
198
43
38
58
50
...
Truncated

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

Test 8

Group: 1

Verdict: ACCEPTED

input
2000 2000
409666302 646936685 583741760 ...

correct output
8
9
12
8
11
...

user output
8
9
12
8
11
...
Truncated

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

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

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

Test 12

Group: 1

Verdict: ACCEPTED

input
1999 2000
129087461 494922181 482953911 ...

correct output
10
6
6
7
7
...

user output
10
6
6
7
7
...
Truncated

Test 13

Group: 1

Verdict: ACCEPTED

input
2000 2000
409666302 646936685 583741760 ...

correct output
8
7
6
7
7
...

user output
8
7
6
7
7
...
Truncated

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

Test 15

Group: 1

Verdict: ACCEPTED

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
981
979
973
...
Truncated

Test 16

Group: 1

Verdict: ACCEPTED

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

correct output
1
2
1
1
2
...

user output
1
2
1
1
2
...
Truncated

Test 17

Group: 1

Verdict: ACCEPTED

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
2
1
1
2
3
...
Truncated

Test 18

Group: 2

Verdict: ACCEPTED

input
1 1
1
1 1

correct output
1

user output
1

Test 19

Group: 2

Verdict: ACCEPTED

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
6
5
4
...
Truncated

Test 20

Group: 2

Verdict: ACCEPTED

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
59
25
12
...
Truncated

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

Test 22

Group: 2

Verdict: ACCEPTED

input
100000 200000
72 58 92 12 32 29 55 87 6 49 5...

correct output
5
7
5
6
2
...

user output
5
7
5
6
2
...
Truncated

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

Test 24

Group: 2

Verdict: ACCEPTED

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

Test 25

Group: 2

Verdict: ACCEPTED

input
100000 200000
72 58 92 12 32 29 55 87 6 49 5...

correct output
5
5
5
5
5
...

user output
5
5
5
5
5
...
Truncated

Test 26

Group: 2

Verdict: ACCEPTED

input
99999 200000
20 47 84 90 88 63 39 16 74 19 ...

correct output
5
7
6
3
3
...

user output
5
7
6
3
3
...
Truncated

Test 27

Group: 2

Verdict: ACCEPTED

input
100000 200000
72 58 92 12 32 29 55 87 6 49 5...

correct output
6
4
9
2
5
...

user output
6
4
9
2
5
...
Truncated

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

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
27
46
29
...
Truncated

Test 30

Group: 2

Verdict: ACCEPTED

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
2
...
Truncated

Test 31

Group: 2

Verdict: ACCEPTED

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

Test 32

Group: 3

Verdict: ACCEPTED

input
1 1
1
1 1

correct output
1

user output
1

Test 33

Group: 3

Verdict: ACCEPTED

input
100000 200000
994198482 687493351 579440176 ...

correct output
8
6
8
10
5
...

user output
8
6
8
10
5
...
Truncated

Test 34

Group: 3

Verdict: ACCEPTED

input
100000 200000
138644593 592364551 919805093 ...

correct output
10
11
13
7
12
...

user output
10
11
13
7
12
...
Truncated

Test 35

Group: 3

Verdict: ACCEPTED

input
100000 200000
10770 195579 349462 442791 450...

correct output
2468
1986
2632
129
4010
...

user output
2468
1986
2632
129
4010
...
Truncated

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

Test 37

Group: 3

Verdict: ACCEPTED

input
100000 200000
398809514 622635167 133376912 ...

correct output
15
13
16
11
17
...

user output
15
13
16
11
17
...
Truncated

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

Test 39

Group: 3

Verdict: ACCEPTED

input
100000 200000
398809514 622635167 133376912 ...

correct output
10
16
7
18
10
...

user output
10
16
7
18
10
...
Truncated

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

Test 41

Group: 3

Verdict: ACCEPTED

input
99999 200000
587542096 890780320 258438313 ...

correct output
8
6
11
11
17
...

user output
8
6
11
11
17
...
Truncated

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

Test 43

Group: 3

Verdict: ACCEPTED

input
100000 200000
398809514 622635167 133376912 ...

correct output
13
13
10
15
15
...

user output
13
13
10
15
15
...
Truncated

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

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

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

Test 47

Group: 3

Verdict: ACCEPTED

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

Test 48

Group: 3

Verdict: ACCEPTED

input
100000 200000
99999 100000 99997 99998 99995...

correct output
2
1
2
2
1
...

user output
2
1
2
2
1
...
Truncated

Test 49

Group: 3

Verdict: ACCEPTED

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
2
...
Truncated

Test 50

Group: 3

Verdict: ACCEPTED

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
23
2
21
4
...
Truncated

Test 51

Group: 3

Verdict: ACCEPTED

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
112
237
49
141
57
...
Truncated

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

Test 53

Group: 3

Verdict: ACCEPTED

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
24841
24973
24865
24823
24969
...
Truncated

Test 54

Group: 3

Verdict: ACCEPTED

input
100000 200000
49999 50000 49997 49998 49995 ...

correct output
210
1
2
2
1
...

user output
210
1
2
2
1
...
Truncated