fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. //mt19937 gen(time(NULL));
  6. mt19937 gen(200);
  7.  
  8. struct node {
  9.     pair<int, int> f, s;
  10.     node *le, *ri;
  11.     ll mn, res;
  12.     int tl, tr;
  13.     node() {
  14.         mn = 228;
  15.     }
  16.     node(int l, int r) {
  17.         tl = l; tr = r;
  18.         mn = 228;
  19.         if (l == r) return;
  20.         le = new node(l, (l+r)/2);
  21.         ri = new node((l+r)/2+1, r);
  22.     }
  23.     node (node* a, node* b) {
  24.         le = a; ri = b;
  25.         tl = le->tl; tr = ri->tr;
  26.         if (le->mn == 228) {
  27.             res = ri->res;
  28.             mn = ri->mn;
  29.             f = ri->f;
  30.             s = ri->s;
  31.             return;
  32.         }
  33.         if (ri->mn == 228) {
  34.             res = le->res;
  35.             mn = le->mn;
  36.             f = le->f;
  37.             s = le->s;
  38.             return;
  39.         }
  40.         f = le->f; s = ri->s;
  41.         ll del = 1ll*le->s.second*(ri->f.first-le->s.first);
  42.         res = le->res+del+ri->res;
  43.         mn = min(le->mn, le->res+del);
  44.         mn = min(mn, ri->mn+le->res+del);
  45.     }
  46.     void combine() {
  47.         node tmp(le, ri);
  48.         *this = tmp;
  49.     }
  50.     void update(int id, int time, int speed) {
  51.         if (tl == tr) {
  52.             mn = res = 0;
  53.             f.first = s.first = time;
  54.             f.second = s.second = speed;
  55.             return;
  56.         }
  57.         if (id <= (tl+tr)/2)
  58.             le->update(id, time, speed);
  59.         else
  60.             ri->update(id, time, speed);
  61.         combine();
  62.     }
  63.     void del(int id) {
  64.         if (tl == tr) {
  65.             mn = 228;
  66.             return;
  67.         }
  68.         if (id <= (tl+tr)/2)
  69.             le->del(id);
  70.         else
  71.             ri->del(id);
  72.         combine();
  73.     }
  74.     node* get_seg(int l, int r) {
  75.         if (tr < l || r < tl) return new node();
  76.         if (l <= tl && tr <= r) {
  77.             return this;;
  78.         }
  79.         return new node(le->get_seg(l, r), ri->get_seg(l, r));
  80.     }
  81.     long double simulate(int r, ll v) {
  82.         if (mn == 228) return -1;
  83.         if (v+mn > 0 && v+res+1ll*s.second*(r-s.first) > 0) return -1;
  84.         if (f == s) return s.first-(long double)v/s.second;
  85.         if (le->mn == 228) return ri->simulate(r, v);
  86.         long double to = le->simulate(le->s.first, v);
  87.         if (to != -1) return to;
  88.         v += le->res;
  89.         ll del = 1ll*le->s.second*((ri->mn==228?r:ri->f.first)-le->s.first);
  90.         if (v+del <= 0) return le->s.first-(long double)v/le->s.second;
  91.         v += del;
  92.         return ri->simulate(r, v);
  93.     }
  94.     long double query(int l, int r, int rr, ll v) {
  95.         node* t = get_seg(l, r);
  96.         return t->simulate(rr, v);
  97.     }
  98. };
  99.  
  100. struct query{
  101.     int time, speed, start;
  102.     int l, r, type;
  103.     query() {}
  104. };
  105.  
  106. vector <int> pos;
  107. vector <query> q;
  108.  
  109. int main() {
  110.     ios_base::sync_with_stdio(false);
  111.     #ifdef LOCAL
  112.     freopen("input.txt", "r", stdin);
  113.     freopen("output.txt", "w", stdout);
  114.     #endif // LOCAL
  115.     cout.precision(7);
  116.     int qq; cin >> qq;
  117.     q.resize(qq);
  118.     for (int i = 0; i < qq; ++i) {
  119.         cin >> q[i].type;
  120.         if (q[i].type == 1) {
  121.             cin >> q[i].time >> q[i].speed;
  122.             pos.push_back(q[i].time);
  123.         }
  124.         if (q[i].type == 2) {
  125.             cin >> q[i].time;
  126.         }
  127.         if (q[i].type == 3) {
  128.             cin >> q[i].l >> q[i].r >> q[i].start;
  129.         }
  130.     }
  131.     sort(pos.begin(), pos.end());
  132.     pos.erase(unique(pos.begin(), pos.end()), pos.end());
  133.     if (pos.size() == 0) pos.push_back(0);
  134.     node* t = new node(0, pos.size()-1);
  135.     for (int i = 0; i < qq; ++i) {
  136.         if (q[i].type == 1) {
  137.             int id = lower_bound(pos.begin(), pos.end(), q[i].time)-pos.begin();
  138.             t->update(id, q[i].time, q[i].speed);
  139.         }
  140.         if (q[i].type == 2) {
  141.             int id = lower_bound(pos.begin(), pos.end(), q[i].time)-pos.begin();
  142.             t->del(id);
  143.         }
  144.         if (q[i].type == 3) {
  145.             int l = lower_bound(pos.begin(), pos.end(), q[i].l)-pos.begin();
  146.             int r = --upper_bound(pos.begin(), pos.end(), q[i].r)-pos.begin();
  147.             if (q[i].start == 0)
  148.                 cout << fixed << q[i].l << '\n';
  149.             else
  150.                 cout << fixed << t->query(l, r, q[i].r, q[i].start) << '\n';
  151.         }
  152.     }
  153.     return 0;
  154. }
  155.  
Runtime error #stdin #stdout #stderr 0s 15264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::length_error'
  what():  vector::_M_default_append
https://ideone.com/2jVhHb
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!