PlayrixCodescapesCup(CodeforcesRound#413,rated,Div.1+Div.2)C.Fountains【树状数组维护区间最大值】

 1 #include 
 2 #define INF 0x3f3f3f3f
 3 #define ll long long int
 4 using namespace std;
 5 
 6 const int MAXN = 1e5+10;
 7 
 8 int t_1[MAXN], t_2[MAXN];
 9 int N, num_c, num_d;
10 
11 int lowbit(int x)
12 {
13     return x&(-x);
14 }
15 void add(int no, int st, int value)
16 {
17     for(int i = st; i <= MAXN; i+=lowbit(i))
18     {
19         if(no) t_1[i] = max(t_1[i], value);
20         else t_2[i] = max(t_2[i], value);
21     }
22 }
23 
24 int query(int no, int st)
25 {
26     int res = 0;
27     for(int i = st; i > 0; i-=lowbit(i))
28     {
29         if(no) res = max(res, t_1[i]);
30         else res = max(res, t_2[i]);
31     }
32     return res;
33 }
34 int main()
35 {
36     char str[3];
37     int ans_max = 0, a, b, ans = 0;
38     scanf("%d%d%d", &N, &num_c, &num_d);
39     for(int i = 1; i <= N; i++)
40     {
41         scanf("%d%d", &a, &b);
42         scanf("%s", str);
43         if(str[0] == ‘C‘){
44             ans_max = query(0, num_d);
45             if(b > num_c) continue;
46             ans_max = max(ans_max, query(1, num_c-b));
47             add(1, b, a);
48         }
49         else{
50             ans_max = query(1, num_c);
51             if(b > num_d) continue;
52             ans_max = max(ans_max, query(0, num_d-b));
53             add(0, b, a);
54         }
55         if(ans_max) ans = max(ans, ans_max+a);
56     }
57     printf("%d\n", ans);
58     return 0;
59 }