CSES - Aalto Competitive Programming 2024 - wk8 - Wed

CSES - Aalto Competitive Programming 2024 - wk8 - Wed - Results

Submission details
Task:	Frog and flies
Sender:	aalto2024i_001
Submission time:	2024-10-30 17:46:50 +0200
Language:	C++ (C++20)
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.00 s	details
#2	ACCEPTED	0.00 s	details
#3	ACCEPTED	0.00 s	details
#4	ACCEPTED	0.00 s	details
#5	ACCEPTED	0.00 s	details
#6	ACCEPTED	0.00 s	details
#7	ACCEPTED	0.00 s	details
#8	ACCEPTED	0.00 s	details
#9	ACCEPTED	0.00 s	details
#10	ACCEPTED	0.00 s	details
#11	ACCEPTED	0.00 s	details
#12	ACCEPTED	0.00 s	details
#13	ACCEPTED	0.00 s	details
#14	ACCEPTED	0.00 s	details
#15	ACCEPTED	0.00 s	details
#16	ACCEPTED	0.00 s	details
#17	ACCEPTED	0.00 s	details
#18	ACCEPTED	0.00 s	details
#19	ACCEPTED	0.00 s	details
#20	ACCEPTED	0.00 s	details
#21	ACCEPTED	0.00 s	details
#22	ACCEPTED	0.00 s	details
#23	ACCEPTED	0.00 s	details
#24	ACCEPTED	0.00 s	details
#25	ACCEPTED	0.00 s	details
#26	ACCEPTED	0.00 s	details
#27	ACCEPTED	0.00 s	details
#28	ACCEPTED	0.00 s	details
#29	ACCEPTED	0.00 s	details
#30	ACCEPTED	0.00 s	details
#31	ACCEPTED	0.00 s	details
#32	ACCEPTED	0.00 s	details
#33	ACCEPTED	0.00 s	details
#34	ACCEPTED	0.00 s	details
#35	ACCEPTED	0.00 s	details
#36	ACCEPTED	0.00 s	details
#37	ACCEPTED	0.00 s	details
#38	ACCEPTED	0.00 s	details
#39	ACCEPTED	0.00 s	details
#40	ACCEPTED	0.00 s	details
#41	ACCEPTED	0.00 s	details
#42	ACCEPTED	0.00 s	details
#43	ACCEPTED	0.00 s	details
#44	ACCEPTED	0.00 s	details
#45	ACCEPTED	0.00 s	details
#46	ACCEPTED	0.00 s	details
#47	ACCEPTED	0.00 s	details
#48	ACCEPTED	0.00 s	details
#49	ACCEPTED	0.00 s	details
#50	ACCEPTED	0.00 s	details
#51	ACCEPTED	0.00 s	details
#52	ACCEPTED	0.00 s	details
#53	ACCEPTED	0.01 s	details
#54	ACCEPTED	0.01 s	details
#55	ACCEPTED	0.01 s	details
#56	ACCEPTED	0.01 s	details
#57	ACCEPTED	0.01 s	details
#58	ACCEPTED	0.01 s	details
#59	ACCEPTED	0.01 s	details
#60	ACCEPTED	0.01 s	details
#61	ACCEPTED	0.01 s	details
#62	ACCEPTED	0.01 s	details
#63	ACCEPTED	0.16 s	details
#64	ACCEPTED	0.16 s	details
#65	ACCEPTED	0.16 s	details
#66	ACCEPTED	0.16 s	details
#67	ACCEPTED	0.14 s	details

Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class SegmentTree {
private:
    int size;
    vector<long long> tree;

    void build(int node, int l, int r) {
        if (l == r){
            tree[node] = 0;
        } 
        else {
            int mid = (l + r) >> 1;
            build(2*node, l, mid);
            build(2*node+1, mid+1, r);
            tree[node] = max(tree[2*node], tree[2*node+1]);
        }
    }

    void update(int node, int l, int r, int pos, long long val) {
        if (l == r){
            tree[node] = val;
        } 
        else {
            int mid = (l + r) >> 1;
            if (pos <= mid)
                update(2*node, l, mid, pos, val);
            else
                update(2*node+1, mid+1, r, pos, val);
            tree[node] = max(tree[2*node], tree[2*node+1]);
        }
    }

    long long query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql)
            return 0;
        if (ql <= l && r <= qr)
            return tree[node];
        int mid = (l + r) >> 1;
        return max(query(2*node, l, mid, ql, qr),
                   query(2*node+1, mid+1, r, ql, qr));
    }

public:
    SegmentTree(int n) : size(n) {
        tree.resize(4*n, 0);
        build(1, 1, n);
    }

    void update(int pos, long long val) {
        update(1, 1, size, pos, val);
    }

    long long query(int l, int r) {
        if (l > r) return 0;
        return query(1, 1, size, l, r);
    }
};

int main() {
    int n;
    cin >> n;
    vector<long long> a(n+1);
    vector<int> b(n+1), c(n+1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i] >> c[i];
    }

    vector<long long> dp(n+1, 0);
    SegmentTree st(n);

    for (int i = n; i >= 1; --i) {
        long long current_max = st.query(b[i], c[i]);
        dp[i] = a[i] + current_max;
        st.update(i, dp[i]);
    }

    long long res = 0;
    for (int i = 1; i <= n; ++i) {
        res = max(res, dp[i]);
    }
    cout << res << endl;
}

Test details

Test 1

Verdict: ACCEPTED

input
`1 9 1 1` view save

correct output
`9` view save

user output
`9` view save

Test 2

Verdict: ACCEPTED

input
`2 9 2 2 3 2 2` view save

correct output
`12` view save

user output
`12` view save

Test 3

Verdict: ACCEPTED

input
`2 20 2 2 16 2 2` view save

correct output
`36` view save

user output
`36` view save

Test 4

Verdict: ACCEPTED

input
`2 9 2 2 19 2 2` view save

correct output
`28` view save

user output
`28` view save

Test 5

Verdict: ACCEPTED

input
`3 17 3 3 19 2 3 16 3 3` view save

correct output
`35` view save

user output
`35` view save

Test 6

Verdict: ACCEPTED

input
`3 4 2 3 15 2 3 14 3 3` view save

correct output
`33` view save

user output
`33` view save

Test 7

Verdict: ACCEPTED

input
`3 20 2 3 15 3 3 15 3 3` view save

correct output
`50` view save

user output
`50` view save

Test 8

Verdict: ACCEPTED

input
`4 10 2 2 17 2 4 10 3 4 20 4 4` view save

correct output
`57` view save

user output
`57` view save

Test 9

Verdict: ACCEPTED

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

correct output
`29` view save

user output
`29` view save

Test 10

Verdict: ACCEPTED

input
`4 17 4 4 16 2 4 3 3 4 9 4 4` view save

correct output
`28` view save

user output
`28` view save

Test 11

Verdict: ACCEPTED

input
`4 9 1 1 11 2 4 13 3 3 19 4 4` view save

correct output
`30` view save

user output
`30` view save

Test 12

Verdict: ACCEPTED

input
`4 13 1 3 15 2 3 2 3 4 15 4 4` view save

correct output
`45` view save

user output
`45` view save

Test 13

Verdict: ACCEPTED

input
`5 17 3 5 11 4 5 13 5 5 9 5 5 ...` view save

correct output
`32` view save

user output
`32` view save

Test 14

Verdict: ACCEPTED

input
`5 19 4 5 7 2 2 5 3 5 4 4 4 ...` view save

correct output
`33` view save

user output
`33` view save

Test 15

Verdict: ACCEPTED

input
`5 19 1 1 9 4 5 7 4 4 5 4 4 ...` view save

correct output
`19` view save

user output
`19` view save

Test 16

Verdict: ACCEPTED

input
`5 17 1 5 11 3 5 9 4 5 3 5 5 ...` view save

correct output
`45` view save

user output
`45` view save

Test 17

Verdict: ACCEPTED

input
`5 19 1 5 11 2 5 4 3 5 20 4 5 ...` view save

correct output
`72` view save

user output
`72` view save

Test 18

Verdict: ACCEPTED

input
`5 17 1 5 19 2 3 2 4 5 16 4 5 ...` view save

correct output
`64` view save

user output
`64` view save

Test 19

Verdict: ACCEPTED

input
`5 5 5 5 1 5 5 20 4 5 11 5 5 ...` view save

correct output
`42` view save

user output
`42` view save

Test 20

Verdict: ACCEPTED

input
`5 7 2 4 15 3 5 7 4 5 11 4 5 ...` view save

correct output
`49` view save

user output
`49` view save

Test 21

Verdict: ACCEPTED

input
`5 5 1 5 11 5 5 9 5 5 9 4 5 ...` view save

correct output
`25` view save

user output
`25` view save

Test 22

Verdict: ACCEPTED

input
`5 10 2 3 3 2 3 1 3 3 9 4 5 ...` view save

correct output
`14` view save

user output
`14` view save

Test 23

Verdict: ACCEPTED

input
`10 17 6 10 11 7 10 13 9 10 9 8 10 ...` view save

correct output
`65` view save

user output
`65` view save

Test 24

Verdict: ACCEPTED

input
`10 19 8 10 7 2 3 5 4 10 4 4 6 ...` view save

correct output
`61` view save

user output
`61` view save

Test 25

Verdict: ACCEPTED

input
`10 19 1 2 9 6 10 7 6 6 5 5 6 ...` view save

correct output
`79` view save

user output
`79` view save

Test 26

Verdict: ACCEPTED

input
`10 17 1 10 11 4 10 9 7 10 3 10 10 ...` view save

correct output
`75` view save

user output
`75` view save

Test 27

Verdict: ACCEPTED

input
`10 19 1 10 11 2 10 4 3 10 20 4 10 ...` view save

correct output
`131` view save

user output
`131` view save

Test 28

Verdict: ACCEPTED

input
`10 17 1 9 19 3 5 2 6 10 16 6 8 ...` view save

correct output
`85` view save

user output
`85` view save

Test 29

Verdict: ACCEPTED

input
`10 5 10 10 1 9 10 20 5 10 11 8 10 ...` view save

correct output
`69` view save

user output
`69` view save

Test 30

Verdict: ACCEPTED

input
`10 7 3 8 15 5 10 7 6 10 11 5 7 ...` view save

correct output
`60` view save

user output
`60` view save

Test 31

Verdict: ACCEPTED

input
`10 5 1 10 11 9 10 9 9 10 9 4 10 ...` view save

correct output
`66` view save

user output
`66` view save

Test 32

Verdict: ACCEPTED

input
`10 10 4 6 3 2 6 1 4 5 9 5 10 ...` view save

correct output
`88` view save

user output
`88` view save

Test 33

Verdict: ACCEPTED

input
`100 906523441 60 92 585063857 61 96 669546421 86 98 469855690 66 85 ...` view save

correct output
`10771464872` view save

user output
`10771464872` view save

Test 34

Verdict: ACCEPTED

input
`100 122816 73 100 157577940 14 31 425825313 12 26 371043004 22 41 ...` view save

correct output
`14222241248` view save

user output
`14222241248` view save

Test 35

Verdict: ACCEPTED

input
`100 590195590 3 19 520495379 45 95 354694313 34 44 750398099 18 23 ...` view save

correct output
`12737127344` view save

user output
`12737127344` view save

Test 36

Verdict: ACCEPTED

input
`100 901888417 8 76 548496961 30 47 469291685 58 97 134846207 90 100 ...` view save

correct output
`8869447580` view save

user output
`8869447580` view save

Test 37

Verdict: ACCEPTED

input
`100 967034924 1 100 587586158 2 100 185430194 3 100 918715995 4 100 ...` view save

correct output
`48013661869` view save

user output
`48013661869` view save

Test 38

Verdict: ACCEPTED

input
`100 892631472 6 88 986350949 22 38 96444602 50 98 822387303 42 63 ...` view save

correct output
`15455597701` view save

user output
`15455597701` view save

Test 39

Verdict: ACCEPTED

input
`100 224848374 95 100 44771412 83 93 638932295 39 54 653343572 13 64 ...` view save

correct output
`10260736901` view save

user output
`10260736901` view save

Test 40

Verdict: ACCEPTED

input
`100 342493822 23 78 776814822 45 98 330726191 47 98 538074003 29 56 ...` view save

correct output
`11666821579` view save

user output
`11666821579` view save

Test 41

Verdict: ACCEPTED

input
`100 257096283 2 98 570001955 88 99 453495728 83 94 462212374 5 67 ...` view save

correct output
`10202755399` view save

user output
`10202755399` view save

Test 42

Verdict: ACCEPTED

input
`100 535937150 37 51 143698367 2 51 14304401 16 33 449369743 25 89 ...` view save

correct output
`17948258094` view save

user output
`17948258094` view save

Test 43

Verdict: ACCEPTED

input
`200 906523441 119 180 585063857 121 191 669546421 170 188 469855690 131 164 ...` view save

correct output
`14287251667` view save

user output
`14287251667` view save

Test 44

Verdict: ACCEPTED

input
`200 122816 145 200 157577940 27 62 425825313 21 49 371043004 40 80 ...` view save

correct output
`23839250714` view save

user output
`23839250714` view save

Test 45

Verdict: ACCEPTED

input
`200 590195590 6 38 520495379 88 190 354694313 66 86 750398099 34 44 ...` view save

correct output
`22543028553` view save

user output
`22543028553` view save

Test 46

Verdict: ACCEPTED

input
`200 901888417 15 149 548496961 59 85 469291685 115 192 134846207 180 190 ...` view save

correct output
`13373790403` view save

user output
`13373790403` view save

Test 47

Verdict: ACCEPTED

input
`200 967034924 1 200 587586158 2 200 185430194 3 200 918715995 4 200 ...` view save

correct output
`99932744816` view save

user output
`99932744816` view save

Test 48

Verdict: ACCEPTED

input
`200 892631472 12 175 986350949 43 74 96444602 99 196 822387303 82 124 ...` view save

correct output
`19585794045` view save

user output
`19585794045` view save

Test 49

Verdict: ACCEPTED

input
`200 224848374 190 200 44771412 165 176 638932295 76 98 653343572 23 122 ...` view save

correct output
`12979170792` view save

user output
`12979170792` view save

Test 50

Verdict: ACCEPTED

input
`200 342493822 46 156 776814822 89 196 330726191 93 196 538074003 55 110 ...` view save

correct output
`15243236118` view save

user output
`15243236118` view save

Test 51

Verdict: ACCEPTED

input
`200 257096283 3 195 570001955 174 190 453495728 164 180 462212374 6 129 ...` view save

correct output
`14283982608` view save

user output
`14283982608` view save

Test 52

Verdict: ACCEPTED

input
`200 535937150 73 101 143698367 3 100 14304401 31 65 449369743 47 176 ...` view save

correct output
`18543618567` view save

user output
`18543618567` view save

Test 53

Verdict: ACCEPTED

input
`1000 906523441 593 887 585063857 604 946 669546421 848 918 469855690 647 789 ...` view save

correct output
`32453898968` view save

user output
`32453898968` view save

Test 54

Verdict: ACCEPTED

input
`1000 122816 721 998 157577940 129 304 425825313 95 238 371043004 189 390 ...` view save

correct output
`45899314427` view save

user output
`45899314427` view save

Test 55

Verdict: ACCEPTED

input
`1000 590195590 26 186 520495379 436 948 354694313 322 422 750398099 157 208 ...` view save

correct output
`49394640341` view save

user output
`49394640341` view save

Test 56

Verdict: ACCEPTED

input
`1000 901888417 71 732 548496961 292 386 469291685 571 956 134846207 897 908 ...` view save

correct output
`29453089763` view save

user output
`29453089763` view save

Test 57

Verdict: ACCEPTED

input
`1000 967034924 1 1000 587586158 2 1000 185430194 3 1000 918715995 4 1000 ...` view save

correct output
`506241655029` view save

user output
`506241655029` view save

Test 58

Verdict: ACCEPTED

input
`1000 892631472 56 871 986350949 208 365 96444602 490 980 822387303 399 613 ...` view save

correct output
`44324051778` view save

user output
`44324051778` view save

Test 59

Verdict: ACCEPTED

input
`1000 224848374 948 972 44771412 822 842 638932295 372 448 653343572 103 583 ...` view save

correct output
`30967398959` view save

user output
`30967398959` view save

Test 60

Verdict: ACCEPTED

input
`1000 342493822 228 780 776814822 439 979 330726191 457 979 538074003 267 540 ...` view save

correct output
`43469922656` view save

user output
`43469922656` view save

Test 61

Verdict: ACCEPTED

input
`1000 257096283 12 970 570001955 870 925 453495728 817 867 462212374 15 622 ...` view save

correct output
`34202519364` view save

user output
`34202519364` view save

Test 62

Verdict: ACCEPTED

input
`1000 535937150 365 502 143698367 9 497 14304401 144 318 449369743 221 878 ...` view save

correct output
`46138944399` view save

user output
`46138944399` view save

Test 63

Verdict: ACCEPTED

input
`100000 906523441 59286 88407 585063857 60277 94359 669546421 84727 91203 469855690 64592 78208 ...` view save

correct output
`313668791775` view save

user output
`313668791775` view save

Test 64

Verdict: ACCEPTED

input
`100000 122816 72034 99721 157577940 12814 30235 425825313 9236 23611 371043004 18629 38794 ...` view save

correct output
`442748272142` view save

user output
`442748272142` view save

Test 65

Verdict: ACCEPTED

input
`100000 590195590 2593 18509 520495379 43533 94774 354694313 32056 42039 750398099 15446 20468 ...` view save

correct output
`441063322118` view save

user output
`441063322118` view save

Test 66

Verdict: ACCEPTED

input
`100000 901888417 7073 72882 548496961 29092 37704 469291685 56933 95391 134846207 89632 89836 ...` view save

correct output
`308915267694` view save

user output
`308915267694` view save

Test 67

Verdict: ACCEPTED

input
`100000 967034924 1 100000 587586158 2 100000 185430194 3 100000 918715995 4 100000 ...` view save

correct output
`49936734769054` view save

user output
`49936734769054` view save

Aalto Competitive Programming 2024 - wk8 - Wed

Frog and flies

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

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Test 62

Test 63

Test 64

Test 65

Test 66

Test 67

Tasks

Submissions (aalto2024i_001)