# CFR 799 C. Fountains ( Segment Tree )

Problem - C - Codeforces

The first line contains three integers n, c and d (2 ≤ n ≤ 100 000, 0 ≤ c, d ≤ 100 000) — the number of fountains, the number of coins and diamonds Arkady has.
The next n lines describe fountains. Each of these lines contain two integers bi and pi (1 ≤ bi, pi ≤ 100 000) — the beauty and the cost of the i-th fountain, and then a letter "C" or "D", describing in which type of money is the cost of fountain i: in coins or in diamonds, respectively.

O( N lg N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 1e5 );

int N, C, D;
int B[ MAXN ], P[ MAXN ];
string T[ MAXN ];

int cmaxv[ MAXN << 3 ];
int dmaxv[ MAXN << 3 ];

void modify( int *maxv, int k, int v, int lb = 0, int rb = MAXN + 1, int t = 1 ) {
if( lb + 1 == rb ) {
maxv[ t ] = max( maxv[ t ], v );
return;
}
int mid = lb + rb >> 1;
if( k < mid ) {
modify( maxv, k, v, lb, mid, t << 1 );
} else {
modify( maxv, k, v, mid, rb, t << 1 | 1 );
}
maxv[ t ] = max( maxv[ t << 1 ], maxv[ t << 1 | 1 ] );
}

int query( int *maxv, int ql, int qr, int lb = 0, int rb = MAXN + 1, int t = 1 ) {
if( qr <= lb or rb <= ql ) return 0;
if( ql <= lb and rb <= qr ) return maxv[ t ];
int mid = lb + rb >> 1;
return max( query( maxv, ql, qr, lb, mid, t << 1 ), query( maxv, ql, qr, mid, rb, t << 1 | 1 ) );
}

signed main() {
ios::sync_with_stdio( 0 );
cin >> N >> C >> D;
for( int i = 0; i < N; ++i ) {
cin >> B[ i ] >> P[ i ] >> T[ i ];
}
for( int i = 0; i < N; ++i ) {
if( T[ i ] == "C" ) {
modify( cmaxv, P[ i ], B[ i ] );
} else {
modify( dmaxv, P[ i ], B[ i ] );
}
}
int ans = 0;
{ // 1 c 1 d
for( int i = 0; i < N; ++i ) {
if( C < P[ i ] ) continue;
if( T[ i ] == "C" ) {
int maxd = query( dmaxv, 0, D + 1 );
if( maxd > 0 ) {
ans = max( ans, B[ i ] + maxd );
}
}
}
}
{ // 2 c
map< int, priority_queue< int > > mpq;
for( int i = 0; i < N; ++i ) {
if( T[ i ] == "C" ) {
mpq[ P[ i ] ].emplace( B[ i ] );
int f = C - P[ i ];
int r = 0;
if( f < P[ i ] ) {
r = query( cmaxv, 0, f + 1 );
} else {
r = max( query( cmaxv, 0, P[ i ] ), query( cmaxv, P[ i ] + 1, f + 1 ) );
}
if( r > 0 ) {
ans = max( ans, B[ i ] + r );
}
}
}
for( int i = 1; i * 2 <= C; ++i ) {
if( mpq[ i ].size() >= 2 ) {
int a = mpq[ i ].top();
mpq[ i ].pop();
int b = mpq[ i ].top();
mpq[ i ].pop();
ans = max( ans, a + b );
}
}
}
{ // 2 d
map< int, priority_queue< int > > mpq;
for( int i = 0; i < N; ++i ) {
if( T[ i ] == "D" ) {
mpq[ P[ i ] ].emplace( B[ i ] );
int f = D - P[ i ];
int r = 0;
if( f < P[ i ] ) {
r = query( dmaxv, 0, f + 1 );
} else {
r = max( query( dmaxv, 0, P[ i ] ), query( dmaxv, P[ i ] + 1, f + 1 ) );
}
if( r > 0 ) {
ans = max( ans, B[ i ] + r );
}
}
}
for( int i = 1; i * 2 <= D; ++i ) {
if( mpq[ i ].size() >= 2 ) {
int a = mpq[ i ].top();
mpq[ i ].pop();
int b = mpq[ i ].top();
mpq[ i ].pop();
ans = max( ans, a + b );
}
}
}
cout << ans << endl;
return 0;
}
```