Box Stack II

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

using st = int;
#define SE_OP(a, b) max(a, b)

const int N = 1<<18;

st S[N*2];

void init() {
  for (int i = 0; i < N*2; ++i) S[i] = 0;
}

void add(int i, st x) {
  i |= N;
  S[i] = x;
  for (i /= 2; i >= 1; i /= 2) {
    S[i] = SE_OP(S[i*2], S[i*2+1]);
  }
}

st get(int a, int b) {
  a |= N; b |= N;
  st s = 0;
  while (a <= b) {
    if (a % 2 == 1) {
      s = SE_OP(s, S[a]);
      ++a;
    } if (b % 2 == 0) {
      s = SE_OP(s, S[b]);
      --b;
    }
    a /= 2; b /= 2;
  }
  return s;
}

tuple<int,int,int,int> T[N];

int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    int a,b,c;
    cin >> a >> b >> c;
    T[i] = {b,a,c,0};
  }
	sort(T,T+n);
	for (int i = 0; i < n; ++i) {
		auto [a,b,c,d] = T[i];
		T[i] = {b,a,c,i};
	}
	sort(T,T+n);
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		auto [a,b,c,j] = T[i];
		ll r = c + get(0,j);
		add(j,r);
		ans = max(ans,r);
	}
	cout << ans << '\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: WRONG ANSWER

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: WRONG ANSWER

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: WRONG ANSWER

Test 38

Verdict: WRONG ANSWER

Test 39

Verdict: WRONG ANSWER

Test 40

Verdict: WRONG ANSWER

Test 41

Verdict: WRONG ANSWER

Test 42

Verdict: WRONG ANSWER

Test 43

Verdict: WRONG ANSWER

Test 44

Verdict: WRONG ANSWER

Test 45

Verdict: WRONG ANSWER

Test 46

Verdict: WRONG ANSWER

Test 47

Verdict: WRONG ANSWER

Test 48

Verdict: WRONG ANSWER

Test 49

Verdict: WRONG ANSWER

Test 50

Verdict: WRONG ANSWER

Test 51

Verdict: WRONG ANSWER

Test 52

Verdict: WRONG ANSWER

Test 53

Verdict: WRONG ANSWER

Test 54

Verdict: WRONG ANSWER

Test 55

Verdict: WRONG ANSWER

Test 56

Verdict: WRONG ANSWER

Test 57

Verdict: WRONG ANSWER

Test 58

Verdict: WRONG ANSWER

Test 59

Verdict: WRONG ANSWER

Test 60

Verdict: WRONG ANSWER

Test 61

Verdict: WRONG ANSWER

Test 62

Verdict: WRONG ANSWER

Test 63

Verdict: WRONG ANSWER

Test 64

Verdict: WRONG ANSWER

Test 65

Verdict: WRONG ANSWER

Test 66

Verdict: WRONG ANSWER

Test 67

Verdict: WRONG ANSWER

Test 68

Verdict: WRONG ANSWER

Test 69

Verdict: WRONG ANSWER

Test 70

Verdict: WRONG ANSWER

Test 71

Verdict: WRONG ANSWER

Test 72

Verdict: WRONG ANSWER

Test 73

Verdict: WRONG ANSWER