fork(1) download
copy 
  1. # include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long lin;
  6. typedef long double ld;
  7. typedef pair < int, int > pii;
  8.  
  9. const int N = int(5e5) + 5;
  10. const int inf = (int)1e9 + 7;
  11.  
  12.  
  13. struct segtree{
  14.   int t[N * 4];
  15.   void upd(int v, int tl, int tr, int pos, int val){
  16.     if(tl == tr){
  17.       t[v] = max(t[v], val);
  18.       return;
  19.     }
  20.     int tm = (tl + tr) >> 1;
  21.     if(pos <= tm){
  22.       upd(v * 2, tl, tm, pos, val);
  23.     } else{
  24.       upd(v * 2 + 1, tm + 1, tr, pos, val);
  25.     }
  26.     t[v] = max(t[v * 2], t[v * 2 + 1]);
  27.   }
  28.   int get(int v, int tl, int tr, int l, int r){
  29.     int tm = (tl + tr) >> 1;
  30.     if(tl == l && tr == r){
  31.       return t[v];
  32.     }
  33.     if(l > r){
  34.       return 0;
  35.     }
  36.     return max(get(v * 2, tl, tm, l, min(r, tm)), get(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
  37.   }
  38.  
  39.   int get(int l, int r){
  40.     return get(1, 1, (int)2e5 + 2, l, r);
  41.   }
  42.  
  43.   void upd(int pos, int val){
  44.     upd(1, 1, (int)2e5 + 2, pos, val);
  45.   }
  46.  
  47.   void clear_it(){
  48.     fill(t, t + N * 4, 0);
  49.   }
  50. }t;
  51.  
  52. int n, c, d;
  53. int ans = -1;
  54. vector < pii > dia, coi;
  55.  
  56. void solve(vector < pii > c, int f){
  57.   vector < int > mx((int)c.size(), 0);
  58.   for(int i = 0; i < (int)c.size(); ++i){
  59.     mx[i] = max(i > 0 ? mx[i - 1] : 0, c[i].second);
  60.   }
  61.   for(int i = 0; i < (int)c.size(); ++i){
  62.     int j = lower_bound(c.begin(), c.begin() + i, make_pair(f - c[i].first + 1, -1)) - c.begin();
  63.     --j;
  64.     if(j >= 0){
  65.       ans = max(ans, mx[j] + c[i].second);
  66.     }
  67.   }
  68. }
  69.  
  70. int main(){
  71.   cin >> n >> c >> d;
  72.   for(int i = 1; i <= n; ++i){
  73.     int x, y;
  74.     char e;
  75.     cin >> x >> y >> e;
  76.     if(e == 'C'){
  77.       coi.push_back(make_pair(y, x));
  78.     } else{
  79.       dia.push_back(make_pair(y, x));
  80.     }
  81.   }
  82.   sort(coi.begin(), coi.end());
  83.   sort(dia.begin(), dia.end());
  84.   solve(coi, c);
  85.   solve(dia, d);
  86.   int b1 = -1, b2 = -1;
  87.   for(auto i : coi){
  88.     if(i.first <= c){
  89.       b1 = max(b1, i.second);
  90.     }
  91.   }
  92.   for(auto i : dia){
  93.     if(i.first <= d){
  94.       b2 = max(b2, i.second);
  95.     }
  96.   }
  97.   if(b1 != -1 && b2 != -1){
  98.     ans = max(ans, b1 + b2);
  99.   }
  100.   if(ans == -1){
  101.     ans = 0;
  102.   }
  103.   cout << ans;
  104.   return 0;
  105. }
Success #stdin #stdout 0s 23056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ABTOLj
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!