CSES - Datatähti Open 2019

CSES - Datatähti Open 2019 - Results

Submission details
Task:	Sunset
Sender:	bogdan10bos
Submission time:	2019-01-20 11:39:31 +0200
Language:	C++
Status:	READY
Result:	0

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

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

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("1.in", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>

using namespace std;

#define FILE_IO

const int NMAX = 1e5;
const int QMAX = 2e5;

typedef pair<int, int> pii;
typedef pair<pii, int> p3i;

int N, Q;
vector<int> v, stv, sol, lft;
vector< vector<int> > rgt;
vector< vector<pii> > qry;

namespace BinaryIndexedTree
{
    vector<int> aib;

    void init()
    {
        aib.resize(N + 2);
    }

    void U(int pos, int val)
    {
        for(; pos <= N; pos += (pos &(-pos)))
            aib[pos] += val;
    }

    int Q(int pos)
    {
        int ans = 0;
        for(; pos > 0; pos -= (pos & (-pos)))
            ans += aib[pos];
        return ans;
    }
}

int main()
{
    #ifdef FILE_IO
    freopen("1.in", "r", stdin);
    //freopen("1.out", "w", stdout);
    #endif

    cin >> N >> Q;
    v.resize(N + 2);
    rgt.resize(N + 2);
    lft.resize(N + 2);
    for(int i = 1; i <= N; i++)
    {
        cin >> v[i];
        while(!stv.empty() && v[i] > v[stv.back()])
            stv.pop_back();

        if(stv.empty()) lft[i] = 0;
        else    lft[i] = stv.back();
        stv.push_back(i);
        rgt[ lft[i] ].push_back(i);
    }

    BinaryIndexedTree::init();
    for(auto x: rgt[0])
        BinaryIndexedTree::U(x, 1);

    sol.resize(Q + 2);
    qry.resize(N + 2);
    for(int i = 1; i <= Q; i++)
    {
        int st, dr;
        cin >> st >> dr;
        qry[st].emplace_back(dr, i);
    }

    for(int i = 1; i <= N; i++)
    {
        for(auto q: qry[i])
        {
            int id = q.second;
            int st = i, dr = q.first;
            sol[id] = BinaryIndexedTree::Q(dr) - BinaryIndexedTree::Q(st - 1);
        }

        for(auto x: rgt[i])
            BinaryIndexedTree::U(x, 1);
    }

    for(int i = 1; i <= Q; i++)
        cout << sol[i] << '\n';

    return 0;
}

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

Test 2

Group: 1

Verdict: WRONG ANSWER

input
`1 1 1 1 1` view save

correct output
`1` view save

user output
(empty)

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

Test 4

Group: 1

Verdict: WRONG ANSWER

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

correct output
`1 1 1` view save

user output
(empty)

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

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

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

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

Test 9

Group: 1

Verdict: WRONG ANSWER

input
`2000 2000 1000000000 1000000000 10000000...` view save

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

user output
(empty)

Test 10

Group: 1

Verdict: WRONG ANSWER

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

correct output
`2000 2000 2000 2000 2000 ...` view save

user output
(empty)

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

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

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

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

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

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

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

Test 18

Group: 2

Verdict: WRONG ANSWER

input
`1 1 1 1 1` view save

correct output
`1` view save

user output
(empty)

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

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

input
`1 1 1 1 1` view save

correct output
`1` view save

user output
(empty)

Test 33

Group: 3

Verdict: WRONG ANSWER

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

user output
(empty)

Datatähti Open 2019

Sunset

Compiler report

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