fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define TIME (1.0* clock()/CLOCKS_PER_SEC)
  3. #define pb push_back
  4. #define eb emplace_back
  5. #define id1 (id<<1)
  6. #define id2 (id<<1)|1
  7. #define ll long long
  8. #define ii pair<int,int>
  9. #define vi vector<int>
  10. #define vii vector<pair<int,int>> 
  11. #define vl vector<long long>
  12. #define vll vector <pair<ll,ll>>
  13. #define li pair<long long,int>
  14. #define vil vector <pair<int,ll>>
  15. #define db double
  16. #define ff first
  17. #define ss second
  18. #define lb lower_bound
  19. #define ub upper_bound
  20. #define FOR(i, a, b) for (int i = (a); i <=(b); i++)
  21. #define F0R(i, a) FOR(i, 0, a-1)
  22. #define ROF(i, a, b) for (int i = (b); i >= (a); i--)
  23. #define R0F(i, a) ROF(i, 0, a-1)
  24. #define rep(a) F0R(_, a)
  25. #define each(a, x) for (auto &a : x)
  26. #define ALL(x) (x).begin(),(x).end()
  27. #define pq priority_queue <li, vector <li>, greater <li>> 
  28. using namespace std;
  29. const int maxn=3e5;
  30. #define int long long
  31.  
  32. int n, sqrtn;
  33. bool check[maxn];
  34. int a[maxn], b[maxn];
  35.  
  36. struct Line {
  37.     int a, b; 
  38.     mutable double xleft;
  39.     bool operator<(const Line &o) const { return a < o.a; }
  40.     double intersect(const Line &o) const {
  41.         return (double)(o.b - b) / (a - o.a);
  42.     }
  43. };
  44.  
  45. vector<Line> groupHull[maxn];
  46. vector<Line> full[maxn];
  47.  
  48. int group(int i) {
  49.     return (i-1)/sqrtn + 1;
  50. }
  51.  
  52. void buildHull(int id) {
  53.     auto &lines = full[id];
  54.     sort(ALL(lines));
  55.     vector<Line> filtered;
  56.     for (int i = 0; i < lines.size(); ++i) {
  57.         if (!filtered.empty() && filtered.back().a == lines[i].a) {
  58.             if (filtered.back().b < lines[i].b)
  59.                 filtered.back().b = lines[i].b;
  60.         } else {
  61.             filtered.push_back(lines[i]);
  62.         }
  63.     }
  64.     vector<Line> hull;
  65.     for (auto l : filtered) {
  66.         while (hull.size() >= 2) {
  67.             auto &l1 = hull[hull.size()-2];
  68.             auto &l2 = hull[hull.size()-1];
  69.             if (l1.intersect(l2) >= l1.intersect(l)) hull.pop_back();
  70.             else break;
  71.         }
  72.         hull.push_back(l);
  73.     }
  74.     groupHull[id] = hull;
  75. }
  76.  
  77. int eval(const Line &l, int x) {
  78.     return l.a * x + l.b;
  79. }
  80.  
  81. int queryHull(const vector<Line> &hull, int x) {
  82.     int l = 0, r = hull.size() - 1;
  83.     while (l < r) {
  84.         int m = (l + r) / 2;
  85.         if (eval(hull[m], x) <= eval(hull[m+1], x)) l = m + 1;
  86.         else r = m;
  87.     }
  88.     return eval(hull[l], x);
  89. }
  90.  
  91. void solve() {
  92.     cin >> n;
  93.     sqrtn = sqrt(n) + 1;
  94.     vector<ii> op(n+1);
  95.     for (int i = 1; i <= n; i++) {
  96.         int t; cin >> t;
  97.         if (t == 1) {
  98.             int A, B; cin >> A >> B;
  99.             a[i] = A; b[i] = B;
  100.             check[i] = true;
  101.             int g = group(i);
  102.             full[g].pb({A, B});
  103.             buildHull(g);
  104.         }
  105.         else if (t == 2) {
  106.             int x;
  107.             cin>>x;
  108.             check[x] = false;
  109.             int g = group(x);
  110.  
  111.             full[g].clear();
  112.             for (int j = (g-1)*sqrtn+1; j <= min(n, g*sqrtn); j++) {
  113.                 if (check[j]) full[g].pb({a[j], b[j]});
  114.             }
  115.             buildHull(g);
  116.         }
  117.         else if (t == 3) {
  118.             int x; cin >> x;
  119.             int res = LLONG_MIN;
  120.             for (int g = 1; g <= group(n); g++) {
  121.                 if (!groupHull[g].empty()) {
  122.                     res = max(res, queryHull(groupHull[g], x));
  123.                 }
  124.             }
  125.             if(res==LLONG_MIN) cout<<"EMPTY SET\n";
  126.             else cout << res << "\n";
  127.         }
  128.     }
  129. }
  130.  
  131. signed main() {
  132.     ios_base::sync_with_stdio(false);
  133.     cin.tie(NULL); cout.tie(NULL);
  134.     if (fopen("TASK.INP", "r")) {
  135.         freopen("TASK.INP", "r", stdin);
  136.         freopen("TASK.OUT", "w", stdout);
  137.     }
  138.     int ntest = 1;
  139.     for (int i = 1; i <= ntest; i++) solve();
  140.     cerr << "\nTime elapsed " << TIME << "s.\n";
  141.     return 0;
  142. }
Success #stdin #stdout #stderr 0.01s 18408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time elapsed 0.010318s.
https://ideone.com/i3OBi6
language:
C++14 (gcc 8.3)
created:
1 day 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!