Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- //#define mp make_pair
- #define forn(i, n) for (int i = 0; i < int(n); i++)
- #define forlr(i, l, r) for (int i = int(l); i <= int(r); i++)
- #define repeat(n) for (int hjfjke = 0; hjfjke < int(n); hjfjke++)
- #define all(c) c.begin(), c.end()
- #define ll long long
- const int mod = 1000000007;
- inline int add(int a, int b);
- inline int mult(int a, int b);
- inline int sub(int a, int b);
- inline int divv(int a, int b);
- int a[300500];
- struct query {
- int type;
- int t;
- int r;
- int v;
- };
- map<int, int> gt;
- const int max_n = 500500;
- int rgt[max_n];
- //int sum_t[4 * max_n];
- long long mn[4 * max_n];
- long long ad[4 * max_n];
- void add(int v, int l, int r, int a, int b, long long c) {
- if (r <= a || b <= l)
- return;
- if (a <= l && r <= b) {
- ad[v] += c;
- mn[v] += c;
- return;
- }
- int m = (l + r) >> 1;
- add(v + v + 1, l, m, a, b, c);
- add(v + v + 2, m, r, a, b, c);
- mn[v] = min(mn[v + v + 1], mn[v + v + 2]) + ad[v];
- }
- int get_not_greater(int v, int l, int r, int a, int b, long long c) {
- if (mn[v] > c)
- return -1;
- if (r <= a || b <= l)
- return -1;
- if (l == r - 1)
- return l;
- int m = (l + r) >> 1;
- int res = get_not_greater(v + v + 1, l, m, a, b, c - ad[v]);
- if (res != -1)
- return res;
- return get_not_greater(v + v + 2, m, r, a, b, c - ad[v]);
- }
- long long get(int v, int l, int r, int a, int b) {
- if (r <= a || b <= l)
- return 3e18;
- if (a <= l && r <= b) {
- return mn[v];
- }
- int m = (l + r) >> 1;
- return min(get(v + v + 1, l, m, a, b), get(v + v + 2, m, r, a, b)) + ad[v];
- }
- int how[max_n];
- int32_t main() {
- std::iostream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- cout << fixed << setprecision(10);
- int q;
- cin >> q;
- vector<query> qs;
- set<int> tms;
- for (int i = 0; i < q; i++) {
- int tp;
- cin >> tp;
- int t;
- if (tp == 1) {
- int v;
- cin >> t >> v;
- tms.insert(t);
- qs.push_back({tp, t, 0, v});
- } else if (tp == 2) {
- cin >> t;
- tms.insert(t);
- qs.push_back({tp, t, 0, 0});
- } else {
- int l, r, v;
- cin >> l >> r >> v;
- //tms.insert(l);
- //tms.insert(r);
- qs.push_back({tp, l, r, v});
- }
- }
- int cnt = 0;
- tms.insert(1e9 + 5);
- tms.insert(0);
- for (int x : tms) {
- gt[x] = cnt;
- rgt[cnt++] = x;
- }
- set<int> st;
- st.insert(1e9 + 5);
- st.insert(0);
- for (auto &query : qs) {
- if (query.type == 1) {
- auto prev = st.lower_bound(query.t);
- prev--;
- auto nxt = st.lower_bound(query.t);
- int prev_id = gt[*prev];
- int nxt_id = gt[*nxt];
- int cur_id = gt[query.t];
- how[cur_id] = query.v;
- //cout << -how[prev_id] * 1ll * (*nxt - *prev) << " " << how[prev_id] * 1ll * (query.t - *prev) << " " << how[cur_id] * 1ll * (*nxt - query.t) << endl;
- add(0, 0, cnt, nxt_id, cnt, -how[prev_id] * 1ll * (*nxt - *prev));
- add(0, 0, cnt, cur_id, cnt, how[prev_id] * 1ll * (query.t - *prev));
- add(0, 0, nxt_id, cnt, cnt, how[cur_id] * 1ll * (*nxt - query.t));
- st.insert(query.t);
- } else if (query.type == 2) {
- st.erase(query.t);
- auto prev = st.lower_bound(query.t);
- prev--;
- auto nxt = st.lower_bound(query.t);
- int prev_id = gt[*prev];
- int nxt_id = gt[*nxt];
- int cur_id = gt[query.t];
- add(0, 0, cnt, nxt_id, cnt, how[prev_id] * 1ll * (*nxt - *prev));
- add(0, 0, cnt, cur_id, cnt, -how[prev_id] * 1ll * (query.t - *prev));
- add(0, 0, nxt_id, cnt, cnt, -how[cur_id] * 1ll * (*nxt - query.t));
- how[cur_id] = 0;
- } else if (query.type == 3) {
- int l = query.t;
- int r = query.r;
- int v = query.v;
- auto prev = st.upper_bound(l);
- prev--;
- int prev_id = gt[*prev];
- long long u = get(0, 0, cnt, prev_id, prev_id + 1);
- int c = how[prev_id];
- u += (l - *prev) * 1ll * c;
- long long should = u - v;
- //cout << should << endl;
- int lp = *st.lower_bound(l);
- auto it = st.upper_bound(r); it--;
- int rp = *it;
- int pos = get_not_greater(0, 0, cnt, gt[lp], gt[rp] + 1, should);
- if (pos == -1) {
- auto nxt = st.lower_bound(r);
- pos = gt[*nxt];
- }
- int t = rgt[pos];
- prev = st.lower_bound(t);
- prev--;
- long long v1 = get(0, 0, cnt, gt[*prev], gt[*prev] + 1);
- long long v2 = get(0, 0, cnt, gt[t], gt[t] + 1);
- bool isans = false;
- double ans = -1;
- //cout << v1 << " " << v2 << endl;
- if (v1 > should && v2 > should) {
- } else if (v1 < should && v2 < should) {
- isans = true;
- ans = l;
- } else {
- int lft = *prev;
- int rgh = t;
- double k = how[gt[*prev]];
- ans = lft + (should - v1) / k;
- /*cout << *prev << " " << k << endl;
- cout << v1 << " " << should << endl;
- cout << "!" << ans << endl;*/
- if (ans >= l - 1e-7 && ans <= r + 1e-7)
- isans = true;
- ans = max(ans, double(l));
- ans = min(ans, double(r));
- }
- if (isans)
- cout << ans << "\n";
- else
- cout << "-1\n";
- }
- }
- return 0;
- }
- int add(int a, int b) {
- int result = a + b;
- if (result >= mod)
- result -= mod;
- return result;
- }
- int sub(int a, int b) {
- int result = a - b;
- if (result < 0)
- result += mod;
- return result;
- }
- int mult(int a, int b) {
- return (a * 1ll * b) % mod;
- }
- int bin(int a, int n) {
- int res = 1;
- while (n) {
- if (n & 1)
- res = mult(res, a);
- a = mult(a, a);
- n /= 2;
- }
- return res;
- }
- int divv(int a, int b) {
- return mult(a, bin(b, mod - 2));
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement