fork download 
  1. #include <bits/stdc++.h>
  2. // #include <ext/pb_ds/assoc_container.hpp>
  3. // #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace std;
  5. // using namespace __gnu_pbds;
  6.  
  7. using ll = long long;
  8. using bl = bool;
  9. using str = string;
  10. using db = double;
  11.  
  12. struct qhash
  13. {
  14.     static uint64_t splitmix64(uint64_t x)
  15.     {
  16.         // http://x...content-available-to-author-only...i.it/splitmix64.c
  17.         x += 0x9e3779b97f4a7c15;
  18.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  19.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  20.         return x ^ (x >> 31);
  21.     }
  22.  
  23.     size_t operator()(uint64_t x) const
  24.     {
  25.         static const uint64_t FIXED_RANDOM =
  26.             chrono::steady_clock::now().time_since_epoch().count();
  27.         return splitmix64(x + FIXED_RANDOM);
  28.     }
  29. };
  30.  
  31. #define fi first
  32. #define se second
  33.  
  34. #define mp(p1, p2) make_pair(p1, p2)
  35. #define f(i, n) for (ll i = 0; i < n; i += 1)
  36. #define fv(i, v) for (typeof(v.begin()) i = v.begin(); i != v.end(); i++)
  37. #define fu(i, start, end) for (int i = start; i < end; i += 1)
  38. #define fd(i, start, end) for (int i = start; i >= end; i -= 1)
  39. #define bit(var, pos) ((var >> pos) & 1)
  40. #define pb push_back
  41. // #define ordered_set tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update>
  42.  
  43. inline ll power(ll a, ll b)
  44. {
  45.     ll res = 1;
  46.     while (b)
  47.     {
  48.         if (b & 1)
  49.             res *= a;
  50.         a *= a;
  51.         b >>= 1;
  52.     }
  53.     return res;
  54. }
  55.  
  56. bl shit[200000];
  57. vector<ll>arr[200000];
  58. vector<vector<ll>>v;
  59. ll n;
  60.  
  61. // const ll maxn=1e5,inf=1e18;
  62. // const ll m1=1e9+7,m2=1e9+9;
  63. // const ll M1=m1*m1,M2=m2*m2;
  64. const int coso = 1000000000;
  65. const int mucoso = 9;
  66. struct bigint {
  67.    vector<int> a;
  68.    int sign;
  69.    int size(){
  70.       if(a.empty())return 0;
  71.       int ans=(a.size()-1)*mucoso;
  72.       int ca=a.back();while(ca)
  73.          ans++,ca/=10;
  74.       return ans;
  75.    }
  76.    bigint operator ^(const bigint &v){
  77.       bigint ans=1,a=*this,b=v;
  78.       while(!b.isZero()){
  79.          if(b%2) ans*=a;
  80.          a*=a,b/=2;
  81.       }
  82.       return ans;
  83.    }
  84.    string to_string(){
  85.       stringstream ss;ss << *this;
  86.       string s;ss >> s;return s;}
  87.    int sumof(){string s = to_string();
  88.       int ans = 0;for(auto c : s) ans += c - '0';
  89.       return ans;
  90.    }
  91.    bigint() :sign(1) {}
  92.    bigint(long long v) {*this = v;}
  93.    bigint(const string &s) {read(s);}
  94.    void operator=(const bigint &v) {sign = v.sign;a = v.a;}
  95.    void operator=(long long v) {
  96.       sign = 1;a.clear();
  97.       if (v < 0)sign = -1, v = -v;
  98.       for (; v > 0; v = v / coso)a.push_back(v % coso);
  99.    }
  100.    bigint operator+(const bigint &v) const {
  101.       if (sign == v.sign) {
  102.          bigint res = v;
  103.          for (int i = 0, crr = 0; i < (int) max(a.size(), v.a.size()) || crr; ++i) {
  104.             if (i == (int) res.a.size())res.a.push_back(0);
  105.             res.a[i] += crr + (i < (int) a.size() ? a[i] : 0);
  106.             crr = res.a[i] >= coso;
  107.             if (crr)res.a[i] -= coso;
  108.          }return res;
  109.       }return *this - (-v);
  110.    }
  111.    bigint operator-(const bigint &v) const {
  112.       if (sign == v.sign) {
  113.          if (abs() >= v.abs()) {
  114.             bigint res = *this;
  115.             for (int i = 0, crr = 0; i < (int) v.a.size() || crr; ++i) {
  116.                res.a[i] -= crr + (i < (int) v.a.size() ? v.a[i] : 0);
  117.                crr = res.a[i] < 0;
  118.                if (crr)res.a[i] += coso;
  119.             }res.trm();return res;
  120.          }return -(v - *this);
  121.       }return *this + (-v);
  122.    }
  123.    void operator*=(int v) {
  124.       if (v < 0)
  125.          sign = -sign, v = -v;
  126.       for (int i = 0, crr = 0; i < (int) a.size() || crr; ++i) {
  127.          if (i == (int) a.size())
  128.             a.push_back(0);
  129.          long long cur = a[i] * (long long) v + crr;
  130.          crr = (int) (cur / coso);
  131.          a[i] = (int) (cur % coso);
  132.       }trm();
  133.    }
  134.    bigint operator*(int v) const {
  135.       bigint res = *this;
  136.       res *= v;return res;
  137.    }
  138.    void operator*=(long long v) {
  139.       if (v < 0)
  140.          sign = -sign, v = -v;
  141.       if(v > coso){
  142.          *this = *this * (v / coso) * coso + *this * (v % coso);
  143.          return;
  144.       }
  145.       for (int i = 0, crr = 0; i < (int) a.size() || crr; ++i) {
  146.          if (i == (int) a.size())
  147.             a.push_back(0);
  148.          long long cur = a[i] * (long long) v + crr;
  149.          crr = (int) (cur / coso);
  150.          a[i] = (int) (cur % coso);
  151.       }
  152.       trm();
  153.    }
  154.    bigint operator*(long long v) const {
  155.       bigint res = *this;
  156.       res *= v;return res;
  157.    }
  158.    friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) {
  159.       int norm = coso / (b1.a.back() + 1);
  160.       bigint a = a1.abs() * norm;
  161.       bigint b = b1.abs() * norm;
  162.       bigint q, r;
  163.       q.a.resize(a.a.size());
  164.       for (int i = a.a.size() - 1; i >= 0; i--) {
  165.          r *= coso;r += a.a[i];
  166.          int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
  167.          int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
  168.          int d = ((long long) coso * s1 + s2) / b.a.back();
  169.          r -= b * d;
  170.          while (r < 0)
  171.             r += b, --d;
  172.          q.a[i] = d;
  173.       }
  174.       q.sign = a1.sign * b1.sign;
  175.       r.sign = a1.sign;
  176.       q.trm();r.trm();
  177.       return make_pair(q, r / norm);
  178.    }
  179.    bigint operator/(const bigint &v) const {return divmod(*this, v).fi;}
  180.    bigint operator%(const bigint &v) const {return divmod(*this, v).se;}
  181.    void operator/=(int v) {
  182.       if (v < 0)
  183.          sign = -sign, v = -v;
  184.       for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
  185.          long long cur = a[i] + rem * (long long) coso;
  186.          a[i] = (int) (cur / v);
  187.          rem = (int) (cur % v);
  188.       } trm();
  189.    }
  190.    bigint operator/(int v) const {
  191.       bigint res = *this;
  192.       res /= v;return res;
  193.    }
  194.    int operator%(int v) const {
  195.       if (v < 0) v = -v;
  196.       int m = 0;
  197.       for (int i = a.size() - 1; i >= 0; --i)
  198.          m = (a[i] + m * (long long) coso) % v;
  199.       return m * sign;
  200.    }
  201.    void operator+=(const bigint &v) {*this = *this + v;}
  202.    void operator-=(const bigint &v) {*this = *this - v;}
  203.    void operator*=(const bigint &v) {*this = *this * v;}
  204.    void operator/=(const bigint &v) {*this = *this / v;}
  205.    bool operator<(const bigint &v) const {
  206.       if (sign != v.sign) return sign < v.sign;
  207.       if (a.size() != v.a.size()) return a.size() * sign < v.a.size() * v.sign;
  208.       for (int i = a.size() - 1; i >= 0; i--)
  209.          if (a[i] != v.a[i]) return a[i] * sign < v.a[i] * sign;
  210.       return false;
  211.    }
  212.    bool operator>(const bigint &v) const {return v < *this;}
  213.    bool operator<=(const bigint &v) const {return !(v < *this);}
  214.    bool operator>=(const bigint &v) const {return !(*this < v);}
  215.    bool operator==(const bigint &v) const {return !(*this < v) && !(v < *this);}
  216.    bool operator!=(const bigint &v) const {return *this < v || v < *this;}
  217.    void trm() {while (!a.empty() && !a.back())a.pop_back();if (a.empty())sign = 1;}
  218.    bool isZero() const { return a.empty() || (a.size() == 1 && !a[0]); }
  219.    bigint operator-() const {
  220.       bigint res = *this;
  221.       res.sign = -sign;
  222.       return res;
  223.    }
  224.    bigint abs() const {
  225.       bigint res = *this;
  226.       res.sign *= res.sign;
  227.       return res;
  228.    }
  229.    long long longValue() const {
  230.       long long res = 0;
  231.       for (int i = a.size() - 1; i >= 0; i--)
  232.          res = res * coso + a[i];
  233.       return res * sign;
  234.    }
  235.    void read(const string &s) {
  236.       sign = 1;a.clear();int pos = 0;
  237.       while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) {
  238.          if (s[pos] == '-')
  239.             sign = -sign;++pos;
  240.       }
  241.       for (int i = s.size() - 1; i >= pos; i -= mucoso) {
  242.          int x = 0;
  243.          for (int j = max(pos, i - mucoso + 1); j <= i; j++)
  244.             x = x * 10 + s[j] - '0';a.push_back(x);
  245.       } trm();
  246.    }
  247.    friend istream& operator>>(istream &stream, bigint &v) {
  248.       string s;stream >> s;v.read(s);return stream;
  249.    }
  250.    friend ostream& operator<<(ostream &stream, const bigint &v) {
  251.       if (v.sign == -1) stream << '-';
  252.       stream << (v.a.empty() ? 0 : v.a.back());
  253.       for (int i = (int) v.a.size() - 2; i >= 0; --i)
  254.          stream << setw(mucoso) << setfill('0') << v.a[i];
  255.       return stream;
  256.    }
  257.    static vector<int> cv_b(const vector<int> &a, int oldd, int newd) {
  258.       vector<long long> p(max(oldd, newd) + 1);p[0] = 1;
  259.       for (int i = 1; i < (int) p.size(); i++) p[i] = p[i - 1] * 10;
  260.       vector<int> res;
  261.       long long cur = 0;
  262.       int cur_digits = 0;
  263.       for (int i = 0; i < (int) a.size(); i++) {
  264.          cur += a[i] * p[cur_digits];
  265.          cur_digits += oldd;
  266.          while (cur_digits >= newd) {
  267.             res.push_back(int(cur % p[newd]));
  268.             cur /= p[newd];
  269.             cur_digits -= newd;
  270.          }
  271.       }
  272.       res.push_back((int) cur);
  273.       while (!res.empty() && !res.back())
  274.          res.pop_back();
  275.       return res;
  276.    }
  277.    typedef vector<long long> vll;
  278.    static vll mul(const vll &a, const vll &b) {
  279.       int n = a.size();
  280.       vll res(n + n);
  281.       if (n <= 32) {
  282.          for (int i = 0; i < n; i++)
  283.             for (int j = 0; j < n; j++)
  284.                res[i + j] += a[i] * b[j];
  285.          return res;
  286.       }
  287.       int k = n >> 1;
  288.       vll a1(a.begin(), a.begin() + k);
  289.       vll a2(a.begin() + k, a.end());
  290.       vll b1(b.begin(), b.begin() + k);
  291.       vll b2(b.begin() + k, b.end());
  292.       vll a1b1 = mul(a1, b1);
  293.       vll a2b2 = mul(a2, b2);
  294.       for (int i = 0; i < k; i++) a2[i] += a1[i];
  295.       for (int i = 0; i < k; i++) b2[i] += b1[i];
  296.       vll r = mul(a2, b2);
  297.       for (int i = 0; i < (int) a1b1.size(); i++)
  298.          r[i] -= a1b1[i];
  299.       for (int i = 0; i < (int) a2b2.size(); i++)
  300.          r[i] -= a2b2[i];
  301.       for (int i = 0; i < (int) r.size(); i++)
  302.          res[i + k] += r[i];
  303.       for (int i = 0; i < (int) a1b1.size(); i++)
  304.          res[i] += a1b1[i];
  305.       for (int i = 0; i < (int) a2b2.size(); i++)
  306.          res[i + n] += a2b2[i];
  307.       return res;
  308.    }
  309.    bigint operator*(const bigint &v) const {
  310.       vector<int> a6 = cv_b(this->a, mucoso, 6);
  311.       vector<int> b6 = cv_b(v.a, mucoso, 6);
  312.       vll a(a6.begin(), a6.end());
  313.       vll b(b6.begin(), b6.end());while (a.size() < b.size()) a.push_back(0);
  314.       while (b.size() < a.size()) b.push_back(0);while (a.size() & (a.size() - 1))
  315.          a.push_back(0),b.push_back(0);
  316.       vll c = mul(a, b);
  317.       bigint res;
  318.       res.sign = sign * v.sign;
  319.       for (int i = 0, crr = 0; i < (int) c.size(); i++) {
  320.          long long cur = c[i] + crr;
  321.          res.a.push_back((int) (cur % 1000000));
  322.          crr = (int) (cur / 1000000);
  323.       }
  324.       res.a = cv_b(res.a, 6, mucoso);
  325.       res.trm();
  326.       return res;
  327.    }
  328. };
  329. // // a - (b * c)
  330. // ll comp(ll &a, ll b, ll c) {
  331. //     ll val = b * c;
  332. //     if (b != 0 && val / b != c) {
  333. //         return 0;
  334. //     }
  335. //     else 
  336. // }
  337. bl check(bigint core) {
  338.     vector<vector<ll>>ev;
  339.     fill(shit, shit + n, 0);
  340.     f(i, n) {
  341.         ev.push_back({v[i][0], 0, i});
  342.         ev.push_back({v[i][1], 1, i});
  343.     }
  344.     sort(ev.begin(), ev.end());
  345.     bigint need = 0;
  346.     bigint prv = -1;
  347.     bigint cnt = 0;
  348.     vector<ll>cur;
  349.     f(i, ev.size()) {
  350.         ll idx = ev[i][2];
  351.         bigint loc = ev[i][0];
  352.         bigint type = ev[i][1];
  353.         // cout << idx << " " << loc << " " << type << '\n';
  354.         if (type == 0) {
  355.             // ne 
  356.             need -= (loc - 1 - prv) * core;
  357.             if (need < 0) {
  358.                 cnt = 0;
  359.                 for (auto &val : cur) 
  360.                     shit[val] = 1;
  361.                 cur.clear();
  362.             }
  363.             need = max(need, bigint(0));
  364.             prv = loc - 1;
  365.             cnt += v[idx][2];
  366.             need += v[idx][2];
  367.             cur.push_back(idx);
  368.  
  369.         }
  370.         else {
  371.             if (shit[idx]) continue;
  372.             need -= (loc - prv) * core;
  373.             prv = loc;
  374.             if (cnt - need < v[idx][2]) return 0;
  375.             cnt -= v[idx][2];
  376.         }
  377.         // cout << need << " " << prv << " " << cnt << "\n";
  378.     }
  379.     return 1;
  380. }
  381. void solve() {
  382.     ll tras;
  383.     cin >> n >> tras;
  384.     f(i, n) {
  385.         ll a, b, c;
  386.         cin >> a >> b >> c;
  387.         v.push_back({b, c, a});
  388.     }
  389.     sort(v.begin(), v.end());
  390.     ll l = 0, r = 1e17 + 1;
  391.     while (r - l > 1) {
  392.         ll mid = l + (r - l) / 2;
  393.         if (check(mid)) r = mid;
  394.         else l = mid;
  395.     }
  396.     cout << r;
  397. }
  398. int main()
  399. {
  400.  
  401.      freopen("schedule.INP", "r" ,stdin); freopen("schedule.OUT", "w", stdout);
  402.     std::ios_base::sync_with_stdio(0);
  403.     std::cin.tie(nullptr);
  404.     long long test = 1;
  405.  
  406.     // cin >> test;
  407.     for (int i = 0; i < test; i += 1)
  408.     {
  409.         solve();
  410.     }
  411.     return 0;
  412. }
Success #stdin #stdout 0.01s 8488KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/2GjW7i
language:
C++14 (gcc 8.3)
created:
2 years 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!