CSES - Aalto Competitive Programming 2024 - wk8 - Wed - Results
Submission details
Task:Frog and flies
Sender:AleksandrPolitov
Submission time:2024-10-30 16:41:53 +0200
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.00 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.01 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails
#15ACCEPTED0.00 sdetails
#16ACCEPTED0.00 sdetails
#17ACCEPTED0.00 sdetails
#18ACCEPTED0.00 sdetails
#19ACCEPTED0.00 sdetails
#20ACCEPTED0.00 sdetails
#21ACCEPTED0.00 sdetails
#22ACCEPTED0.00 sdetails
#23ACCEPTED0.00 sdetails
#24ACCEPTED0.00 sdetails
#25ACCEPTED0.00 sdetails
#26ACCEPTED0.00 sdetails
#27ACCEPTED0.00 sdetails
#28ACCEPTED0.00 sdetails
#29ACCEPTED0.00 sdetails
#30ACCEPTED0.00 sdetails
#31ACCEPTED0.00 sdetails
#32ACCEPTED0.00 sdetails
#33ACCEPTED0.00 sdetails
#34ACCEPTED0.00 sdetails
#35ACCEPTED0.00 sdetails
#36ACCEPTED0.00 sdetails
#37ACCEPTED0.00 sdetails
#38ACCEPTED0.00 sdetails
#39ACCEPTED0.00 sdetails
#40ACCEPTED0.00 sdetails
#41ACCEPTED0.00 sdetails
#42ACCEPTED0.00 sdetails
#43ACCEPTED0.00 sdetails
#44ACCEPTED0.00 sdetails
#45ACCEPTED0.00 sdetails
#46ACCEPTED0.00 sdetails
#47ACCEPTED0.00 sdetails
#48ACCEPTED0.00 sdetails
#49ACCEPTED0.00 sdetails
#50ACCEPTED0.00 sdetails
#51ACCEPTED0.00 sdetails
#52ACCEPTED0.00 sdetails
#53ACCEPTED0.00 sdetails
#54ACCEPTED0.00 sdetails
#55ACCEPTED0.00 sdetails
#56ACCEPTED0.00 sdetails
#57ACCEPTED0.00 sdetails
#58ACCEPTED0.00 sdetails
#59ACCEPTED0.00 sdetails
#60ACCEPTED0.00 sdetails
#61ACCEPTED0.00 sdetails
#62ACCEPTED0.00 sdetails
#63ACCEPTED0.06 sdetails
#64ACCEPTED0.06 sdetails
#65ACCEPTED0.06 sdetails
#66ACCEPTED0.06 sdetails
#67ACCEPTED0.05 sdetails

Code

#ifdef ONPC
    #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>

#define char unsigned char
#define rep(i, a, b) for(int i=a; i< (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back

#define LSOne(S) ((S) & -(S))

using namespace std;
// mt19937 rnd(239);
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

template <typename T> int sgn(T x) { return (T(0) < x) - (x < T(0)); }
typedef long double T;
typedef complex<T> pt;
#define X real()
#define Y imag()

template<class T>
istream& operator>> (istream& is, complex<T>& p) {
    T value;
    is >> value;
    p.real(value);
    is >> value;
    p.imag(value);
    return is;
}

typedef long long ll;
typedef long double ld;

using pi = pair<ll, ll>;
using vi = vector<ll>;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }

#define MIN(v) *min_element(all(v))
#define MAX(v) *max_element(all(v))
#define LB(c, x) distance((c).begin(), lower_bound(all(c), (x)))
#define UB(c, x) distance((c).begin(), upper_bound(all(c), (x)))

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif

template<typename S, typename T = S> void chmin(S &s, T t) {s = s < t ? s : t;}
template<typename S, typename T = S> void chmax(S &s, T t) {s = s > t ? s : t;}

const int INF = 1e9; // 10^9 = 1B is < 2^31-1
const ll LLINF = 4e18; // 4*10^18 is < 2^63-1
const double EPS = 1e-9;
const ll MOD = 1e9+7;

const int N=1e5+10;

struct Tree {
    typedef int T;
    static constexpr T unit = INT_MIN;
    T f(T a, T b) { return max(a, b); } // (any associative fn)
    vector<T> s; int n;
    Tree(int n = 0, T def = unit) : s(2*n, def), n(n) {}
    void update(int pos, T val) {
        for (s[pos += n] = val; pos /= 2;)
            s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
    }
    T query(int b, int e) { // query [b, e)
        T ra = unit, rb = unit;
        for (b += n, e += n; b < e; b /= 2, e /= 2) {
            if (b % 2) ra = f(ra, s[b++]);
            if (e % 2) rb = f(s[--e], rb);
        }
        return f(ra, rb);
    }
};

int solve() {
    int n; std::cin >> n;
    Tree tree(n);
    vector<array<ll, 3>> v(n);
    for (int i = 0; i < n; i++) {
        ll a,b,c; std::cin >> a >> b >> c;
        v[i]={a,b,c};
        tree.update(i, 0);
    }



    for (int i = n-1; i >= 0; i--) {
        array<ll, 3> curr=v[i];
        curr[1]--;
        curr[2]--;
        ll now=curr[0]+tree.query(curr[1], curr[2]+1);
        tree.update(i, now);
    }


    std::cout << tree.query(0, n) << std::endl;

    return 0;
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1;
    //cin >> TET;
    for (int i = 1; i <= TET; i++) {
        #ifdef ONPC
            cout << "TEST CASE#" << i << endl;
        #endif
        
        if (solve()) {
            break;
        }

        #ifdef ONPC
            cout << "__________________________" << endl;
        #endif
    }
    #ifdef ONPC
        cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
    #endif
}

Test details

Test 1

Verdict: ACCEPTED

input
1
9 1 1

correct output
9

user output
9

Test 2

Verdict: ACCEPTED

input
2
9 2 2
3 2 2

correct output
12

user output
12

Test 3

Verdict: ACCEPTED

input
2
20 2 2
16 2 2

correct output
36

user output
36

Test 4

Verdict: ACCEPTED

input
2
9 2 2
19 2 2

correct output
28

user output
28

Test 5

Verdict: ACCEPTED

input
3
17 3 3
19 2 3
16 3 3

correct output
35

user output
35

Test 6

Verdict: ACCEPTED

input
3
4 2 3
15 2 3
14 3 3

correct output
33

user output
33

Test 7

Verdict: ACCEPTED

input
3
20 2 3
15 3 3
15 3 3

correct output
50

user output
50

Test 8

Verdict: ACCEPTED

input
4
10 2 2
17 2 4
10 3 4
20 4 4

correct output
57

user output
57

Test 9

Verdict: ACCEPTED

input
4
9 1 4
15 3 4
1 3 3
5 4 4

correct output
29

user output
29

Test 10

Verdict: ACCEPTED

input
4
17 4 4
16 2 4
3 3 4
9 4 4

correct output
28

user output
28

Test 11

Verdict: ACCEPTED

input
4
9 1 1
11 2 4
13 3 3
19 4 4

correct output
30

user output
30

Test 12

Verdict: ACCEPTED

input
4
13 1 3
15 2 3
2 3 4
15 4 4

correct output
45

user output
45

Test 13

Verdict: ACCEPTED

input
5
17 3 5
11 4 5
13 5 5
9 5 5
...

correct output
32

user output
32

Test 14

Verdict: ACCEPTED

input
5
19 4 5
7 2 2
5 3 5
4 4 4
...

correct output
33

user output
33

Test 15

Verdict: ACCEPTED

input
5
19 1 1
9 4 5
7 4 4
5 4 4
...

correct output
19

user output
19

Test 16

Verdict: ACCEPTED

input
5
17 1 5
11 3 5
9 4 5
3 5 5
...

correct output
45

user output
45

Test 17

Verdict: ACCEPTED

input
5
19 1 5
11 2 5
4 3 5
20 4 5
...

correct output
72

user output
72

Test 18

Verdict: ACCEPTED

input
5
17 1 5
19 2 3
2 4 5
16 4 5
...

correct output
64

user output
64

Test 19

Verdict: ACCEPTED

input
5
5 5 5
1 5 5
20 4 5
11 5 5
...

correct output
42

user output
42

Test 20

Verdict: ACCEPTED

input
5
7 2 4
15 3 5
7 4 5
11 4 5
...

correct output
49

user output
49

Test 21

Verdict: ACCEPTED

input
5
5 1 5
11 5 5
9 5 5
9 4 5
...

correct output
25

user output
25

Test 22

Verdict: ACCEPTED

input
5
10 2 3
3 2 3
1 3 3
9 4 5
...

correct output
14

user output
14

Test 23

Verdict: ACCEPTED

input
10
17 6 10
11 7 10
13 9 10
9 8 10
...

correct output
65

user output
65

Test 24

Verdict: ACCEPTED

input
10
19 8 10
7 2 3
5 4 10
4 4 6
...

correct output
61

user output
61

Test 25

Verdict: ACCEPTED

input
10
19 1 2
9 6 10
7 6 6
5 5 6
...

correct output
79

user output
79

Test 26

Verdict: ACCEPTED

input
10
17 1 10
11 4 10
9 7 10
3 10 10
...

correct output
75

user output
75

Test 27

Verdict: ACCEPTED

input
10
19 1 10
11 2 10
4 3 10
20 4 10
...

correct output
131

user output
131

Test 28

Verdict: ACCEPTED

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

correct output
85

user output
85

Test 29

Verdict: ACCEPTED

input
10
5 10 10
1 9 10
20 5 10
11 8 10
...

correct output
69

user output
69

Test 30

Verdict: ACCEPTED

input
10
7 3 8
15 5 10
7 6 10
11 5 7
...

correct output
60

user output
60

Test 31

Verdict: ACCEPTED

input
10
5 1 10
11 9 10
9 9 10
9 4 10
...

correct output
66

user output
66

Test 32

Verdict: ACCEPTED

input
10
10 4 6
3 2 6
1 4 5
9 5 10
...

correct output
88

user output
88

Test 33

Verdict: ACCEPTED

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

correct output
10771464872

user output
2122407944

Test 34

Verdict: ACCEPTED

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

correct output
14222241248

user output
2128790750

Test 35

Verdict: ACCEPTED

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

correct output
12737127344

user output
2141630608

Test 36

Verdict: ACCEPTED

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

correct output
8869447580

user output
2135490356

Test 37

Verdict: ACCEPTED

input
100
967034924 1 100
587586158 2 100
185430194 3 100
918715995 4 100
...

correct output
48013661869

user output
2145478322

Test 38

Verdict: ACCEPTED

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

correct output
15455597701

user output
2106023257

Test 39

Verdict: ACCEPTED

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

correct output
10260736901

user output
2109507973

Test 40

Verdict: ACCEPTED

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

correct output
11666821579

user output
2127868070

Test 41

Verdict: ACCEPTED

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

correct output
10202755399

user output
2115324173

Test 42

Verdict: ACCEPTED

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

correct output
17948258094

user output
2142753634

Test 43

Verdict: ACCEPTED

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

correct output
14287251667

user output
2145672644

Test 44

Verdict: ACCEPTED

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

correct output
23839250714

user output
2141620234

Test 45

Verdict: ACCEPTED

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

correct output
22543028553

user output
2138572703

Test 46

Verdict: ACCEPTED

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

correct output
13373790403

user output
2141795264

Test 47

Verdict: ACCEPTED

input
200
967034924 1 200
587586158 2 200
185430194 3 200
918715995 4 200
...

correct output
99932744816

user output
2144464892

Test 48

Verdict: ACCEPTED

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

correct output
19585794045

user output
2139025319

Test 49

Verdict: ACCEPTED

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

correct output
12979170792

user output
2142739205

Test 50

Verdict: ACCEPTED

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

correct output
15243236118

user output
2147364198

Test 51

Verdict: ACCEPTED

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

correct output
14283982608

user output
2144165478

Test 52

Verdict: ACCEPTED

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

correct output
18543618567

user output
2146853749

Test 53

Verdict: ACCEPTED

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

correct output
32453898968

user output
2147057377

Test 54

Verdict: ACCEPTED

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

correct output
45899314427

user output
2146680984

Test 55

Verdict: ACCEPTED

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

correct output
49394640341

user output
2147067338

Test 56

Verdict: ACCEPTED

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

correct output
29453089763

user output
2146906282

Test 57

Verdict: ACCEPTED

input
1000
967034924 1 1000
587586158 2 1000
185430194 3 1000
918715995 4 1000
...

correct output
506241655029

user output
2146661542

Test 58

Verdict: ACCEPTED

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

correct output
44324051778

user output
2145973655

Test 59

Verdict: ACCEPTED

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

correct output
30967398959

user output
2147109151

Test 60

Verdict: ACCEPTED

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

correct output
43469922656

user output
2146558272

Test 61

Verdict: ACCEPTED

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

correct output
34202519364

user output
2147216913

Test 62

Verdict: ACCEPTED

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

correct output
46138944399

user output
2144957978

Test 63

Verdict: ACCEPTED

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

correct output
313668791775

user output
2147472406

Test 64

Verdict: ACCEPTED

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

correct output
442748272142

user output
2147469309

Test 65

Verdict: ACCEPTED

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

correct output
441063322118

user output
2147467321

Test 66

Verdict: ACCEPTED

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

correct output
308915267694

user output
2147475967

Test 67

Verdict: ACCEPTED

input
100000
967034924 1 100000
587586158 2 100000
185430194 3 100000
918715995 4 100000
...

correct output
49936734769054

user output
2147467369