Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * if you are using <set>, are you sure you do not need a <multiset>?
- * overflow BITCH
- * n = 1, n = 0.
- */
- #include <bits/stdc++.h>
- #define F first
- #define S second
- #define pb push_back
- //#define mp make_pair
- using namespace std;
- typedef long long ll;
- typedef pair <ll, ll> pll;
- const int maxN = 3e5 + 9;
- const int MOD = 1e9 + 7;
- struct val {
- long long x[3], mul;
- val () {
- }
- val (ll a, ll b, ll c) {
- x[0] = a;
- x[1] = b;
- x[2] = c;
- mul = a * b % MOD * c % MOD;
- }
- void flex () {
- sort (x, x + 3);
- }
- };
- long long segTree[4 * maxN], lazy[4 * maxN];
- long long bp (ll a, ll b) {
- if (b == 0)
- return 1ll;
- long long tmp = bp (a, b / 2);
- if (b & 1)
- return tmp * tmp % MOD * a % MOD;
- return tmp * tmp % MOD;
- }
- void push (long long v) {
- segTree[v] *= lazy[v];
- segTree[v] %= MOD;
- lazy[2 * v] *= lazy[v];
- lazy[2 * v] %= MOD;
- lazy[2 * v + 1] *= lazy[v];
- lazy[2 * v + 1] %= MOD;
- lazy[v] = 1;
- return;
- }
- void updateRange (int v, int l, int r, int L, int R, ll x) {
- push (v);
- if (L > R)
- return;
- if (l > r)
- return;
- if (l > R || r < L)
- return;
- if (L <= l && r <= R) {
- lazy[v] *= x;
- lazy[v] %= MOD;
- push (v);
- return;
- }
- int mid = (l + r) / 2;
- updateRange (2 * v, l, mid, L, R, x);
- updateRange (2 * v + 1, mid + 1, r, L, R, x);
- segTree[v] = (segTree[2 * v] + segTree[2 * v + 1]) % MOD;
- }
- long long getSum (int v, int l, int r, int L, int R) {
- push (v);
- if (L > R)
- return 0;
- if (l > r)
- return 0;
- if (l > R || r < L)
- return 0;
- if (L <= l && r <= R)
- return segTree[v];
- int mid = (l + r) / 2;
- return (getSum (2 * v, l, mid, L, R) +
- getSum(2 * v + 1, mid + 1, r, L, R)) % MOD;
- }
- struct str {
- int l, r;
- long long x;
- str (ll X, int L, int R) {
- x = X;
- l = L;
- r = R;
- }
- };
- long long inv (ll x) {
- return bp (x, MOD - 2);
- }
- void solve () {
- int n;
- cin >> n;
- for (int i = 1; i < 4 * maxN; i++) {
- lazy[i] = 1;
- segTree[i] = 1;
- }
- vector <val> A (n + 1);
- for (int i = 1; i <= n; i++) {
- long long a, b, c;
- cin >> a >> b >> c;
- A[i] = val(a, b, c);
- A[i].flex();
- }
- stack <str> maxA, maxB, maxC;
- long long res = 0;
- for (int i = 1; i <= n; i++) {
- int a = A[i].x[0];
- int b = A[i].x[1];
- int c = A[i].x[2];
- //a
- updateRange (1, 1, n, i, i, a);
- if (maxA.empty() || maxA.top().x > a) {
- maxA.push (str (a, i, i));
- } else if (maxA.top().x == a) {
- auto y = maxA.top();
- maxA.pop();
- maxA.push (str (a, y.l, y.r + 1));
- } else {
- int l = maxA.top().l;
- while (maxA.size() && maxA.top().x < a) {
- l = min (maxA.top().l, l);
- updateRange (1, 1, n, maxA.top().l, maxA.top().r, a * inv(maxA.top().x) % MOD);
- maxA.pop();
- }
- maxA.push (str (a, l, i));
- }
- //b
- updateRange (1, 1, n, i, i, b);
- if (maxB.empty() || maxB.top().x > b) {
- maxB.push (str (b, i, i));
- } else if (maxB.top().x == b) {
- auto y = maxB.top();
- maxB.pop();
- maxB.push (str (b, y.l, y.r + 1));
- } else {
- int l = maxB.top().l;
- while (maxB.size() && maxB.top().x < b) {
- l = min (maxB.top().l, l);
- updateRange (1, 1, n, maxB.top().l, maxB.top().r, b * inv(maxB.top().x) % MOD);
- maxB.pop();
- }
- maxB.push (str (b, l, i));
- }
- //c
- updateRange (1, 1, n, i, i, c);
- if (maxC.empty() || maxC.top().x > c) {
- maxC.push (str (c, i, i));
- } else if (maxC.top().x == c) {
- auto y = maxC.top();
- maxC.pop();
- maxC.push (str (c, y.l, y.r + 1));
- } else {
- int l = maxC.top().l;
- while (maxC.size() && maxC.top().x < c) {
- l = min (maxC.top().l, l);
- updateRange (1, 1, n, maxC.top().l, maxC.top().r, c * inv(maxC.top().x) % MOD);
- maxC.pop();
- }
- maxC.push (str (c, l, i));
- }
- //cout << getSum (1, 1, n, 1, i) << "\n";
- res += getSum (1, 1, n, 1, i);
- res %= MOD;
- }
- long long ways = n * (n - 1) / 2 + n;
- //cout << res << "\n";
- ways %= MOD;
- cout << res * bp (ways, MOD - 2) % MOD << "\n";
- return;
- }
- int main () {
- //ios_base::sync_with_stdio (0);
- //cin.tie (0);
- long long testCases = 1;
- //cin >> testCases;
- //setIO ("billboard");
- //preCalc ();
- while (testCases--) {
- //initialize common variables
- //go solve
- solve ();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment