Fshl0

Untitled

Jul 28th, 2022
1,379
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.43 KB | None | 0 0
  1. /*
  2.  * if you are using <set>, are you sure you do not need a <multiset>?
  3.  * overflow BITCH
  4.  * n = 1, n = 0.
  5.  */
  6.  
  7. #include <bits/stdc++.h>
  8. #define F first
  9. #define S second
  10. #define pb push_back
  11. //#define mp make_pair
  12.  
  13. using namespace std;
  14. typedef long long ll;
  15. typedef pair <ll,  ll>  pll;
  16.  
  17. const int maxN = 3e5 + 9;
  18. const int MOD = 1e9 + 7;
  19.  
  20. struct val {
  21.     long long x[3], mul;
  22.    
  23.     val () {
  24.        
  25.     }
  26.    
  27.     val (ll a, ll b, ll c) {
  28.         x[0] = a;
  29.         x[1] = b;
  30.         x[2] = c;
  31.        
  32.         mul = a * b % MOD * c % MOD;
  33.     }
  34.    
  35.     void flex () {
  36.         sort (x, x + 3);
  37.     }
  38. };
  39.  
  40. long long segTree[4 * maxN], lazy[4 * maxN];
  41.  
  42. long long bp (ll a, ll b) {
  43.     if (b == 0)
  44.         return 1ll;
  45.    
  46.     long long tmp = bp (a, b / 2);
  47.     if (b & 1)
  48.         return tmp * tmp % MOD * a % MOD;
  49.     return tmp * tmp % MOD;
  50. }
  51.  
  52.  
  53. void push (long long v) {
  54.     segTree[v] *= lazy[v];
  55.     segTree[v] %= MOD;
  56.  
  57.     lazy[2 * v] *= lazy[v];
  58.     lazy[2 * v] %= MOD;
  59.    
  60.     lazy[2 * v + 1] *= lazy[v];
  61.     lazy[2 * v + 1] %= MOD;
  62.    
  63.     lazy[v] = 1;
  64.     return;
  65. }
  66.  
  67. void updateRange (int v, int l, int r, int L, int R, ll x) {
  68.     push (v);
  69.    
  70.     if (L > R)
  71.         return;
  72.        
  73.     if (l > r)
  74.         return;
  75.        
  76.     if (l > R || r < L)
  77.         return;
  78.    
  79.     if (L <= l && r <= R) {
  80.         lazy[v] *= x;
  81.         lazy[v] %= MOD;
  82.        
  83.         push (v);
  84.         return;
  85.     }
  86.        
  87.     int mid = (l + r) / 2;
  88.    
  89.     updateRange (2 * v, l, mid, L, R, x);
  90.     updateRange (2 * v + 1, mid + 1, r, L, R, x);
  91.     segTree[v] = (segTree[2 * v] + segTree[2 * v + 1]) % MOD;
  92. }
  93.  
  94. long long getSum (int v, int l, int r, int L, int R) {
  95.     push (v);
  96.    
  97.     if (L > R)
  98.         return 0;
  99.        
  100.     if (l > r)
  101.         return 0;
  102.    
  103.     if (l > R || r < L)
  104.         return 0;
  105.    
  106.     if (L <= l && r <= R)
  107.         return segTree[v];
  108.        
  109.     int mid = (l + r) / 2;
  110.     return  (getSum (2 * v, l, mid, L, R) +
  111.         getSum(2 * v + 1, mid + 1, r, L, R)) % MOD;
  112. }
  113.  
  114. struct str {
  115.     int l, r;
  116.     long long x;
  117.    
  118.     str (ll X, int L, int R) {
  119.         x = X;
  120.         l = L;
  121.         r = R;
  122.     }
  123. };
  124.  
  125. long long inv (ll x) {
  126.     return bp (x, MOD - 2);
  127. }
  128.  
  129. void solve () {
  130.     int n;
  131.     cin >> n;
  132.    
  133.     for (int i = 1; i < 4 * maxN; i++) {
  134.         lazy[i] = 1;
  135.         segTree[i] = 1;
  136.     }
  137.    
  138.     vector <val> A (n + 1);
  139.     for (int i = 1; i <= n; i++) {
  140.         long long a, b, c;
  141.         cin >> a >> b >> c;
  142.        
  143.         A[i] = val(a, b, c);
  144.         A[i].flex();
  145.     }
  146.    
  147.     stack <str> maxA, maxB, maxC;
  148.     long long res = 0;
  149.    
  150.     for (int i = 1; i <= n; i++) {
  151.         int a = A[i].x[0];
  152.         int b = A[i].x[1];
  153.         int c = A[i].x[2];
  154.        
  155.         //a
  156.         updateRange (1, 1, n, i, i, a);
  157.        
  158.         if (maxA.empty() || maxA.top().x > a) {
  159.             maxA.push (str (a, i, i));
  160.         } else if (maxA.top().x == a) {
  161.             auto y = maxA.top();
  162.             maxA.pop();
  163.             maxA.push (str (a, y.l, y.r + 1));
  164.         } else {
  165.             int l = maxA.top().l;
  166.             while (maxA.size() && maxA.top().x < a) {
  167.                 l = min (maxA.top().l, l);
  168.                 updateRange (1, 1, n, maxA.top().l, maxA.top().r, a * inv(maxA.top().x) % MOD);
  169.                
  170.                 maxA.pop();
  171.             }
  172.            
  173.             maxA.push (str (a, l, i));
  174.         }
  175.        
  176.         //b
  177.         updateRange (1, 1, n, i, i, b);
  178.        
  179.         if (maxB.empty() || maxB.top().x > b) {
  180.             maxB.push (str (b, i, i));
  181.         } else if (maxB.top().x == b) {
  182.             auto y = maxB.top();
  183.             maxB.pop();
  184.             maxB.push (str (b, y.l, y.r + 1));
  185.         } else {
  186.             int l = maxB.top().l;
  187.             while (maxB.size() && maxB.top().x < b) {
  188.                 l = min (maxB.top().l, l);
  189.                 updateRange (1, 1, n, maxB.top().l, maxB.top().r, b * inv(maxB.top().x) % MOD);
  190.                
  191.                 maxB.pop();
  192.             }
  193.            
  194.             maxB.push (str (b, l, i));
  195.         }
  196.        
  197.         //c
  198.         updateRange (1, 1, n, i, i, c);
  199.        
  200.         if (maxC.empty() || maxC.top().x > c) {
  201.             maxC.push (str (c, i, i));
  202.         } else if (maxC.top().x == c) {
  203.             auto y = maxC.top();
  204.             maxC.pop();
  205.             maxC.push (str (c, y.l, y.r + 1));
  206.         } else {
  207.             int l = maxC.top().l;
  208.             while (maxC.size() && maxC.top().x < c) {
  209.                 l = min (maxC.top().l, l);
  210.                 updateRange (1, 1, n, maxC.top().l, maxC.top().r, c * inv(maxC.top().x) % MOD);
  211.                
  212.                 maxC.pop();
  213.             }
  214.            
  215.             maxC.push (str (c, l, i));
  216.         }
  217.        
  218.         //cout << getSum (1, 1, n, 1, i) << "\n";
  219.         res += getSum (1, 1, n, 1, i);
  220.         res %= MOD;
  221.     }
  222.    
  223.     long long ways = n * (n - 1) / 2 + n;
  224.    
  225.     //cout << res << "\n";
  226.     ways %= MOD;
  227.    
  228.     cout << res * bp (ways, MOD - 2) % MOD << "\n";
  229.     return;
  230. }
  231.  
  232. int main () {
  233.     //ios_base::sync_with_stdio (0);
  234.     //cin.tie (0);
  235.    
  236.     long long testCases = 1;
  237.     //cin >> testCases;
  238.    
  239.     //setIO ("billboard");
  240.     //preCalc ();
  241.    
  242.     while (testCases--) {
  243.         //initialize common variables
  244.        
  245.         //go solve
  246.         solve ();
  247.     }
  248.    
  249.     return 0;
  250. }
  251.  
Advertisement
Add Comment
Please, Sign In to add comment