Advertisement
BaoJIaoPisu

Untitled

Dec 18th, 2021
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.06 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. using ld = long double;
  7. using ull = unsigned long long;
  8.  
  9. using pii = pair<int, int>;
  10. using pll = pair<ll, ll>;
  11. using pld = pair<ld, ld>;
  12.  
  13. #define fi first
  14. #define se second
  15. #define pb push_back
  16. #define pf push_front
  17. #define mp make_pair
  18. #define ins insert
  19.  
  20. #define sz(x) (int)(x.size());
  21. #define all(x) x.begin(), x.end()
  22. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  23.  
  24. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  25.  
  26. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  27. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  28. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  29.  
  30. template<class X, class Y>
  31.     bool minimize(X &x, const Y &y) {
  32.         if (x > y)
  33.         {
  34.             x = y;
  35.             return true;
  36.         }
  37.         return false;
  38.     }
  39. template<class X, class Y>
  40.     bool maximize(X &x, const Y &y) {
  41.         if (x < y)
  42.         {
  43.             x = y;
  44.             return true;
  45.         }
  46.         return false;
  47.     }
  48.  
  49. const int MOD = 1e9 + 7; //998244353
  50.  
  51. template<class X, class Y>
  52.     void add(X &x, const Y &y) {
  53.         x = (x + y);
  54.         if(x >= MOD) x -= MOD;
  55.     }
  56.  
  57. template<class X, class Y>
  58.     void sub(X &x, const Y &y) {
  59.         x = (x - y);
  60.         if(x < 0) x += MOD;
  61.     }
  62.  
  63. /* Author : Le Ngoc Bao Anh, 11A5, LQD High School for Gifted Student*/
  64.  
  65. const ll INF = 1e9;
  66. const int N = 1e6 + 10;
  67.  
  68. pii a[N], b[N];
  69. ll prefA[N], prefB[N];
  70. vector<int> v;
  71.  
  72. void solve() {
  73.     int k; cin >> k;
  74.     int n = 0, m = 0;
  75.  
  76.     v.pb(-INF);
  77.     v.pb(INF);
  78.     for(int i = 1; i <= k; i++) {
  79.         char c;
  80.         int x, y;
  81.         cin >> c >> x >> y;
  82.         if(c == 'A') a[++n] = mp(x, y);
  83.         else b[++m] = mp(x, y);
  84.         v.pb(x - 1);
  85.         v.pb(x);
  86.         v.pb(x + 1);
  87.     }  
  88.  
  89.     sort(all(v));
  90.     v.resize(unique(all(v)) - v.begin());
  91.  
  92.     sort(a + 1, a + 1 + n);
  93.     sort(b + 1, b + 1 + m);
  94.     for(int i = 1; i <= n; i++) {
  95.         a[i].fi = lower_bound(all(v), a[i].fi) - v.begin() + 1;
  96.         prefA[i] = prefA[i - 1] + a[i].se;
  97.     }
  98.  
  99.     for(int i = 1; i <= m; i++) {
  100.         b[i].fi = lower_bound(all(v), b[i].fi) - v.begin() + 1;
  101.         prefB[i] = prefB[i - 1] + b[i].se;
  102.     }
  103.  
  104.     ll ans = -(INF * INF); int res = 0;
  105.     for(int i = 1; i <= v.size(); i++) {
  106.         if(v[i - 1] < -INF || v[i - 1] > INF) continue;
  107.         int L = 1, R = n, posA = 0;
  108.         while(L <= R) {
  109.             int mid = (L + R) >> 1;
  110.             if(a[mid].fi < i) {
  111.                 posA = mid;
  112.                 L = mid + 1;
  113.             } else R = mid - 1;
  114.         }
  115.  
  116.         L = 1, R = m; int posB = 0;
  117.         while(L <= R) {
  118.             int mid = (L + R) >> 1;
  119.             if(b[mid].fi <= i) {
  120.                 posB = mid;
  121.                 L = mid + 1;
  122.             } else R = mid - 1;
  123.         }
  124.  
  125.         if(maximize(ans, 2 * prefA[posA] - prefA[n] + prefB[m] - 2 * prefB[posB])) res = i;
  126.     }
  127.  
  128.     cout << v[res - 1] << " " << ans;
  129. }
  130.  
  131. int main()
  132. {
  133.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  134.     #ifndef ONLINE_JUDGE
  135.     freopen("input.txt", "r", stdin);
  136.     freopen("output.txt", "w", stdout);
  137.     #else
  138.     //online
  139.     #endif
  140.  
  141.     int tc = 1, ddd = 0;
  142.     // cin >> tc;
  143.     while(tc--) {
  144.         //ddd++;
  145.         //cout << "Case #" << ddd << ": ";
  146.         solve();
  147.     }
  148. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement