SHARE
TWEET

Untitled

a guest Feb 16th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. //#define mp make_pair
  6. #define forn(i, n) for (int i = 0; i < int(n); i++)
  7. #define forlr(i, l, r) for (int i = int(l); i <= int(r); i++)
  8. #define repeat(n) for (int hjfjke = 0; hjfjke < int(n); hjfjke++)
  9. #define all(c) c.begin(), c.end()
  10. #define ll long long
  11.  
  12. const int mod = 1000000007;
  13.  
  14. inline int add(int a, int b);
  15. inline int mult(int a, int b);
  16. inline int sub(int a, int b);
  17. inline int divv(int a, int b);
  18.  
  19.  
  20. int a[300500];
  21.  
  22. struct query {
  23.     int type;
  24.     int t;
  25.     int r;
  26.     int v;
  27. };
  28.  
  29. map<int, int> gt;
  30.  
  31. const int max_n = 500500;
  32.  
  33. int rgt[max_n];
  34.  
  35. //int sum_t[4 * max_n];
  36. long long mn[4 * max_n];
  37.  
  38. long long ad[4 * max_n];
  39.  
  40. void add(int v, int l, int r, int a, int b, long long c) {
  41.     if (r <= a || b <= l)
  42.         return;
  43.     if (a <= l && r  <= b) {
  44.         ad[v] += c;
  45.         mn[v] += c;
  46.         return;
  47.     }
  48.  
  49.     int m = (l + r) >> 1;
  50.  
  51.     add(v + v + 1, l, m, a, b, c);
  52.     add(v + v + 2, m, r, a, b, c);
  53.  
  54.     mn[v] = min(mn[v + v + 1], mn[v + v + 2]) + ad[v];
  55. }
  56.  
  57. int get_not_greater(int v, int l, int r, int a, int b, long long c) {
  58.     if (mn[v] > c)
  59.         return -1;
  60.  
  61.     if (r <= a || b <= l)
  62.         return -1;
  63.  
  64.     if (l == r - 1)
  65.         return l;
  66.  
  67.     int m = (l + r) >> 1;
  68.  
  69.     int res = get_not_greater(v + v + 1, l, m, a, b, c - ad[v]);
  70.  
  71.     if (res != -1)
  72.         return res;
  73.  
  74.     return get_not_greater(v + v + 2, m, r, a, b, c - ad[v]);
  75. }
  76.  
  77. long long get(int v, int l, int r, int a, int b) {
  78.     if (r <= a || b <= l)
  79.         return 3e18;
  80.  
  81.     if (a <= l && r <= b) {
  82.         return mn[v];
  83.     }
  84.  
  85.     int m = (l + r) >> 1;
  86.  
  87.     return min(get(v + v + 1, l, m, a, b), get(v + v + 2, m, r, a, b)) + ad[v];
  88. }
  89.  
  90. int how[max_n];
  91.  
  92. int32_t main() {
  93.     std::iostream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  94.     cout << fixed << setprecision(10);
  95.  
  96.     int q;
  97.     cin >> q;
  98.  
  99.     vector<query> qs;
  100.  
  101.     set<int> tms;
  102.  
  103.     for (int i = 0; i < q; i++) {
  104.         int tp;
  105.         cin >> tp;
  106.         int t;
  107.         if (tp == 1) {
  108.             int v;
  109.             cin >> t >> v;
  110.             tms.insert(t);
  111.             qs.push_back({tp, t, 0, v});
  112.         } else if (tp == 2) {
  113.             cin >> t;
  114.             tms.insert(t);
  115.             qs.push_back({tp, t, 0, 0});
  116.         } else {
  117.             int l, r, v;
  118.             cin >> l >> r >> v;
  119.             //tms.insert(l);
  120.             //tms.insert(r);
  121.             qs.push_back({tp, l, r, v});
  122.         }
  123.     }
  124.  
  125.     int cnt = 0;
  126.     tms.insert(1e9 + 5);
  127.     tms.insert(0);
  128.  
  129.     for (int x : tms) {
  130.         gt[x] = cnt;
  131.         rgt[cnt++] = x;
  132.     }
  133.  
  134.     set<int> st;
  135.     st.insert(1e9 + 5);
  136.     st.insert(0);
  137.  
  138.     for (auto &query : qs) {
  139.         if (query.type == 1) {
  140.  
  141.             auto prev = st.lower_bound(query.t);
  142.             prev--;
  143.             auto nxt = st.lower_bound(query.t);
  144.  
  145.  
  146.             int prev_id = gt[*prev];
  147.             int nxt_id = gt[*nxt];
  148.  
  149.             int cur_id = gt[query.t];
  150.             how[cur_id] = query.v;
  151.  
  152.             //cout << -how[prev_id] * 1ll *  (*nxt - *prev) << " " << how[prev_id] * 1ll * (query.t - *prev) << " " << how[cur_id] * 1ll * (*nxt - query.t) << endl;
  153.  
  154.             add(0, 0, cnt, nxt_id, cnt, -how[prev_id] * 1ll *  (*nxt - *prev));
  155.             add(0, 0, cnt, cur_id, cnt, how[prev_id] * 1ll * (query.t - *prev));
  156.             add(0, 0, nxt_id, cnt, cnt, how[cur_id] * 1ll * (*nxt - query.t));
  157.  
  158.             st.insert(query.t);
  159.         } else if (query.type == 2) {
  160.             st.erase(query.t);
  161.  
  162.             auto prev = st.lower_bound(query.t);
  163.             prev--;
  164.             auto nxt = st.lower_bound(query.t);
  165.  
  166.             int prev_id = gt[*prev];
  167.             int nxt_id = gt[*nxt];
  168.  
  169.             int cur_id = gt[query.t];
  170.  
  171.             add(0, 0, cnt, nxt_id, cnt, how[prev_id] * 1ll *  (*nxt - *prev));
  172.             add(0, 0, cnt, cur_id, cnt, -how[prev_id] * 1ll * (query.t - *prev));
  173.             add(0, 0, nxt_id, cnt, cnt, -how[cur_id] * 1ll * (*nxt - query.t));
  174.  
  175.             how[cur_id] = 0;
  176.         } else if (query.type == 3) {
  177.             int l = query.t;
  178.             int r = query.r;
  179.             int v = query.v;
  180.  
  181.             auto prev = st.upper_bound(l);
  182.             prev--;
  183.  
  184.             int prev_id = gt[*prev];
  185.  
  186.             long long u = get(0, 0, cnt, prev_id, prev_id + 1);
  187.  
  188.             int c = how[prev_id];
  189.  
  190.             u += (l - *prev) * 1ll * c;
  191.  
  192.             long long should = u - v;
  193.  
  194.             //cout << should << endl;
  195.  
  196.             int lp = *st.lower_bound(l);
  197.  
  198.             auto it = st.upper_bound(r); it--;
  199.             int rp = *it;
  200.  
  201.             int pos = get_not_greater(0, 0, cnt, gt[lp], gt[rp] + 1, should);
  202.  
  203.             if (pos == -1) {
  204.                 auto nxt = st.lower_bound(r);
  205.  
  206.                 pos = gt[*nxt];
  207.             }
  208.  
  209.             int t = rgt[pos];
  210.             prev = st.lower_bound(t);
  211.             prev--;
  212.  
  213.             long long v1 = get(0, 0, cnt, gt[*prev], gt[*prev] + 1);
  214.             long long v2 = get(0, 0, cnt, gt[t], gt[t] + 1);
  215.  
  216.             bool isans = false;
  217.             double ans = -1;
  218.  
  219.             //cout << v1 << " " << v2 << endl;
  220.  
  221.             if (v1 > should && v2 > should) {
  222.  
  223.             } else if (v1 < should && v2 < should) {
  224.                 isans = true;
  225.                 ans = l;
  226.             } else {
  227.                 int lft = *prev;
  228.                 int rgh = t;
  229.  
  230.                 double k = how[gt[*prev]];
  231.  
  232.                 ans = lft + (should - v1) / k;
  233.  
  234.  
  235.                 /*cout << *prev << " " << k << endl;
  236.                 cout << v1 << " " << should << endl;
  237.                 cout << "!" << ans << endl;*/
  238.  
  239.                 if (ans >= l - 1e-7 && ans <= r + 1e-7)
  240.                     isans = true;
  241.  
  242.                 ans = max(ans, double(l));
  243.                 ans = min(ans, double(r));
  244.             }
  245.  
  246.  
  247.             if (isans)
  248.                 cout << ans << "\n";
  249.             else
  250.                 cout << "-1\n";
  251.         }
  252.     }
  253.  
  254.     return 0;
  255. }
  256.  
  257. int add(int a, int b) {
  258.     int result = a + b;
  259.     if (result >= mod)
  260.         result -= mod;
  261.     return result;
  262. }
  263.  
  264. int sub(int a, int b) {
  265.     int result = a - b;
  266.     if (result < 0)
  267.         result += mod;
  268.     return result;
  269. }
  270.  
  271. int mult(int a, int b) {
  272.     return (a * 1ll * b) % mod;
  273. }
  274.  
  275. int bin(int a, int n) {
  276.     int res = 1;
  277.     while (n) {
  278.         if (n & 1)
  279.             res = mult(res, a);
  280.  
  281.         a = mult(a, a);
  282.         n /= 2;
  283.     }
  284.  
  285.     return res;
  286. }
  287.  
  288. int divv(int a, int b) {
  289.     return mult(a, bin(b, mod - 2));
  290. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top