Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- using ull = unsigned long long;
- using pii = pair<int, int>;
- using pll = pair<ll, ll>;
- using pld = pair<ld, ld>;
- #define fi first
- #define se second
- #define left BAO
- #define right ANH
- #define pb push_back
- #define pf push_front
- #define mp make_pair
- #define ins insert
- #define btpc __builtin_popcount
- #define btclz __builtin_clz
- #define sz(x) (int)(x.size());
- #define all(x) x.begin(), x.end()
- #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
- int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
- int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
- template<class X, class Y>
- bool minimize(X &x, const Y &y) {
- if (x > y)
- {
- x = y;
- return true;
- }
- return false;
- }
- template<class X, class Y>
- bool maximize(X &x, const Y &y) {
- if (x < y)
- {
- x = y;
- return true;
- }
- return false;
- }
- const int MOD = 1e9 + 7; //998244353
- template<class X, class Y>
- void add(X &x, const Y &y) {
- x = (x + y);
- if(x >= MOD) x -= MOD;
- }
- template<class X, class Y>
- void sub(X &x, const Y &y) {
- x = (x - y);
- if(x < 0) x += MOD;
- }
- /* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/
- const ll INF = 1e9;
- const int N = 2e6 + 10;
- const int K = 20;
- template <typename T> T mod_inv_in_range(T a, T m) {
- // assert(0 <= a && a < m);
- T x = a, y = m;
- T vx = 1, vy = 0;
- while (x) {
- T k = y / x;
- y %= x;
- vy -= k * vx;
- std::swap(x, y);
- std::swap(vx, vy);
- }
- assert(y == 1);
- return vy < 0 ? m + vy : vy;
- }
- template <typename T> T mod_inv(T a, T m) {
- a %= m;
- a = a < 0 ? a + m : a;
- return mod_inv_in_range(a, m);
- }
- template <int MOD_> struct modnum {
- static constexpr int MOD = MOD_;
- static_assert(MOD_ > 0, "MOD must be positive");
- using ll = long long;
- int v;
- public:
- modnum() : v(0) {}
- modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
- explicit operator int() const { return v; }
- friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
- friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
- friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
- friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
- modnum inv() const {
- modnum res;
- res.v = mod_inv_in_range(v, MOD);
- return res;
- }
- friend modnum inv(const modnum& m) { return m.inv(); }
- modnum neg() const {
- modnum res;
- res.v = v ? MOD-v : 0;
- return res;
- }
- friend modnum neg(const modnum& m) { return m.neg(); }
- modnum operator- () const {
- return neg();
- }
- modnum operator+ () const {
- return modnum(*this);
- }
- modnum& operator ++ () {
- v ++;
- if (v == MOD) v = 0;
- return *this;
- }
- modnum& operator -- () {
- if (v == 0) v = MOD;
- v --;
- return *this;
- }
- modnum& operator += (const modnum& o) {
- v -= MOD-o.v;
- v = (v < 0) ? v + MOD : v;
- return *this;
- }
- modnum& operator -= (const modnum& o) {
- v -= o.v;
- v = (v < 0) ? v + MOD : v;
- return *this;
- }
- modnum& operator *= (const modnum& o) {
- v = int(ll(v) * ll(o.v) % MOD);
- return *this;
- }
- modnum& operator /= (const modnum& o) {
- return *this *= o.inv();
- }
- friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
- friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
- friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
- friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
- friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
- friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
- };
- using num = modnum<MOD>;
- num P[K + 5][K + 5];
- num C[K + 5];
- int degree = 0;
- void Gauss(int n) {
- for(int i = 0; i < n; i++) {
- for(int j = i; j < n; j++) {
- if(P[j][i] != 0) {
- for(int k = 0; k <= n; k++) {
- swap(P[j][k], P[i][k]);
- }
- break;
- }
- }
- if(P[i][i] == 0) continue;
- for(int j = 0; j < n; j++) {
- if(i == j) continue;
- num coef = P[j][i] / P[i][i];
- for(int k = 0; k <= n; k++) P[j][k] -= P[i][k] * coef;
- }
- }
- for(int i = 0; i < n; i++) C[i] = P[i][n] / P[i][i];
- degree = n - 1;
- }
- num calc(int x) {
- num T = 1, ans = 0;
- for(int i = 0; i <= degree; i++) {
- ans += T * C[i]; T = T * x;
- }
- return ans;
- }
- struct SegmentTree {
- int n;
- struct NODE {
- num sum, fs, p;
- int val, lazy = 0;
- NODE() {
- sum = fs = p = 0;
- val = lazy;
- }
- };
- vector<num> D;
- vector<NODE> node;
- SegmentTree(vector<int> values = {}) {
- n = values.size();
- node.resize(4 * n + 7);
- D.resize(n + 7);
- for(int i = 1; i <= n; i++) {
- D[i] = calc(values[i - 1]);
- }
- for(int i = 1; i <= 4 * n; i++) node[i] = NODE();
- Build(1, n, 1);
- }
- private:
- NODE merge(const NODE &left, const NODE &right) {
- NODE ans = NODE();
- ans.val = min(left.val, right.val);
- ans.fs = left.fs + right.fs;
- ans.sum = left.sum + right.sum;
- if(ans.val) {
- if(left.val == right.val) ans.p = left.p + right.p;
- else ans.p = (left.val < right.val ? left.p + right.sum : left.sum + right.p);
- }
- return ans;
- }
- void Build(int l, int r, int id) {
- if(l == r) {
- node[id].fs = D[l] - D[l - 1];
- return;
- }
- int mid = (l + r) >> 1;
- Build(l, mid, id << 1);
- Build(mid + 1, r, id << 1 | 1);
- node[id] = merge(node[id << 1], node[id << 1 | 1]);
- }
- void Down(int id) {
- int &x = node[id].lazy;
- if(!x) return;
- for(int i = (id << 1); i <= (id << 1 | 1); i++) {
- if(x > 0) {
- if(!node[i].val) node[i].p = node[i].sum;
- node[i].val += x;
- node[i].sum = node[i].fs;
- node[i].lazy += x;
- } else {
- node[i].val += x;
- if(!node[i].val) node[i].sum = node[i].p;
- node[i].lazy += x;
- }
- }
- x = 0;
- }
- void Update(int l, int r, int lo, int hi, int val, int id) {
- if(l > hi || r < lo) return;
- if(lo <= l && r <= hi) {
- if(val == 1) {
- node[id].val++;
- if(node[id].val == 1) node[id].p = node[id].sum;
- node[id].sum = node[id].fs;
- } else {
- node[id].val--;
- if(!node[id].val) node[id].sum = node[id].p;
- }
- node[id].lazy += val;
- return;
- }
- Down(id);
- int mid = (l + r) >> 1;
- Update(l, mid, lo, hi, val, id << 1);
- Update(mid + 1, r, lo, hi, val, id << 1 | 1);
- node[id] = merge(node[id << 1], node[id << 1 | 1]);
- }
- public:
- void update(int l, int r, int val) {
- Update(1, n, l, r, val, 1);
- }
- };
- struct Recs {
- int x, y, u, v;
- } recs[N];
- vector<pii> events[N];
- void BaoJiaoPisu() {
- int n, k; cin >> n >> k;
- //find formula for 1 ^ k + 2 ^ k + ... + x ^ k
- num S = 0;
- for(int i = 0; i < k + 2; i++) {
- num T = 1;
- for(int j = 1; j <= k; j++) T *= (i + 1);
- S += T;
- T = 1;
- for(int j = 0; j <= k + 1; j++) {
- P[i][j] = T; T = T * (i + 1);
- }
- P[i][k + 2] = S;
- }
- Gauss(k + 2);
- //Sweepline to calculate answer
- vector<int> values;
- for(int i = 1; i <= n; i++) {
- cin >> recs[i].x >> recs[i].y >> recs[i].u >> recs[i].v;
- values.pb(recs[i].x);
- values.pb(recs[i].y);
- values.pb(recs[i].u);
- values.pb(recs[i].v);
- values.pb(recs[i].v + 1);
- values.pb(recs[i].x - 1);
- values.pb(recs[i].u - 1);
- }
- sort(all(values)); values.resize(unique(all(values)) - values.begin());
- SegmentTree IT = SegmentTree(values);
- for(int i = 1; i <= n; i++) {
- recs[i].x = lower_bound(all(values), recs[i].x) - values.begin() + 1;
- recs[i].y = lower_bound(all(values), recs[i].y) - values.begin() + 1;
- recs[i].u = lower_bound(all(values), recs[i].u) - values.begin() + 1;
- recs[i].v = lower_bound(all(values), recs[i].v) - values.begin() + 1;
- events[recs[i].y].pb(mp(recs[i].x, recs[i].u));
- events[recs[i].v + 1].pb(mp(-recs[i].x, recs[i].u));
- }
- num ans = 0;
- int last = 1;
- for(int i = 1; i <= values.size(); i++) {
- if(i > 1) {
- ans += IT.node[1].sum * (calc(values[i - 1] - 1) - calc(last - 1));
- }
- last = values[i - 1];
- for(pii e : events[i]) {
- IT.update(abs(e.fi), e.se, (e.fi < 0 ? -1 : 1));
- }
- }
- cout << ans;
- }
- int main()
- {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- //online
- #endif
- int tc = 1, ddd = 0;
- // cin >> tc;
- while(tc--) {
- //ddd++;
- //cout << "Case #" << ddd << ": ";
- BaoJiaoPisu();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement