Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2018
487
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.39 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define SQ(a) (a)*(a)
  4.  
  5. #define F0R(i, a) for(int i = 0; i < (a); i++)
  6. #define FOR(i, a, b) for(int i = (a); i < (b); i++)
  7. #define R0F(i, a) for(int i = (a) - 1; i >= 0; i--)
  8. #define ROF(i, a, b) for(int i = (b) - 1; i >= (a); i--)
  9.  
  10. #define ran() (rand() & 0x7FFF)
  11. #define rand31() ((ran() << 16) | (ran() << 1) | (ran() & 1))
  12. #define rand32() ((ran() << 17) | (ran() << 2) | (ran() & 3))
  13. #define rand63() (((ll)ran() << 48) | ((ll)ran() << 33) | ((ll)ran() << 18) | ((ll)ran() << 3) | ((ll)ran() & 7))
  14. #define rand64() (((ll)ran() << 49) | ((ll)ran() << 34) | ((ll)ran() << 19) | ((ll)ran() << 4) | ((ll)ran() & 15))
  15.  
  16. #define F first
  17. #define S second
  18. #define PB push_back
  19. #define MP make_pair
  20. #define MT make_tuple
  21. #define UB upper_bound
  22. #define LB lower_bound
  23. #define X real()
  24. #define Y imag()
  25. #define R real()
  26. #define I image()
  27. #define PI acos(-1)
  28. #define MAXN 100000
  29. #define MOD 1000000007
  30.  
  31. using namespace std;
  32.  
  33. typedef long long ll;
  34. typedef unsigned long long ull;
  35. typedef long double ld;
  36. typedef pair<int, int> pii;
  37. typedef vector<int> vi;
  38. typedef complex<ld> point;
  39. typedef complex<ld> cld;
  40.  
  41. int n;
  42. ll yVal[MAXN], w[MAXN], f[MAXN], fSqPrefix[MAXN], fPrefix[MAXN];
  43.  
  44. int main() {
  45.     ifstream fin("sprinklers.in");
  46.     ofstream fout("sprinklers.out");
  47.     fin >> n;
  48.     F0R(i, n) {
  49.         int x, y;
  50.         fin >> x >> y;
  51.         yVal[x] = y;
  52.     }
  53.     w[0] = yVal[0];
  54.     FOR(i, 1, n) w[i] = min(yVal[i], w[i - 1]);
  55.     f[n - 1] = yVal[n - 1];
  56.     R0F(i, n - 1) f[i] = max(yVal[i], f[i + 1]);
  57.     fSqPrefix[0] = SQ(f[0]) % MOD;
  58.     FOR(i, 1, n) fSqPrefix[i] = (fSqPrefix[i - 1] + SQ(f[i]) % MOD) % MOD;
  59.     fPrefix[0] = f[0];
  60.     FOR(i, 1, n) fPrefix[i] = (fPrefix[i - 1] + f[i] % MOD) % MOD;
  61.     ll res = 0;
  62.     int maxEnd = 0;
  63.     F0R(s, n) {
  64.         while(maxEnd < n - 1 && f[maxEnd + 1] > w[s]) maxEnd++;
  65.         int numEnds = maxEnd - s;
  66.         ll add = (fSqPrefix[maxEnd] + MOD - fSqPrefix[s]) % MOD;
  67.         add += MOD - (2 * w[s] * ((fPrefix[maxEnd] + MOD - fPrefix[s]) % MOD)) % MOD;
  68.         add %= MOD;
  69.         add += numEnds * (SQ(w[s]) % MOD);
  70.         add %= MOD;
  71.         add += (fPrefix[maxEnd] + MOD - fPrefix[s]) % MOD;
  72.         add %= MOD;
  73.         add += MOD - (numEnds * w[s]) % MOD;
  74.         add %= MOD;
  75.         add = add * 500000004 % MOD;
  76.         res = (res + add) % MOD;
  77.     }
  78.     fout << res << endl;
  79.     return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement