Advertisement
Guest User

Untitled

a guest
Feb 16th, 2019
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.54 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement