fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define TASK ""
  5. #define ll long long
  6. #define pii pair<int, int>
  7. #define pll pair<ll, ll>
  8. #define pb push_back
  9. #define fi first
  10. #define se second
  11. #define REP(i, n) for (int i = 1, _n = (n); i <= _n; i++)
  12. #define REV(i, n) for (int i = (n); i >= 1; i--)
  13. #define FOR(i, k, n) for (int i = (k), _n = (n); i <= _n; i++)
  14. #define FOV(i, k, n) for (int i = (n), _n = (k); i >= _n; i--)
  15. #define MASK(k) (1LL << (k))
  16. #define BIT(i, n) (((n) >> ((i) - 1)) & 1)
  17. #define OFF(i, n) ((n) & ~MASK((i) - 1))
  18. #define ON(i, n) ((n) | MASK((i) - 1))
  19. #define NUM_BIT(n) (__builtin_popcountll(n))
  20.  
  21. const int MAXN = 5e3 + 26;
  22. const int MOD = 1e9 + 7;
  23. int n, x, y, res, b[MAXN], bit[MAXN], gpar[MAXN], lpar[MAXN];
  24. pii p[MAXN];
  25. vector<int> Y;
  26.  
  27. void make_set() {
  28.     REP(i, n) bit[i] = 0;
  29.     FOR(i, 0, n + 1) gpar[i] = lpar[i] = i;
  30. }
  31.  
  32. int find_set(int u, int par[]) {
  33.     return u == par[u] ? u : par[u] = find_set(par[u], par);
  34. }
  35.  
  36. int upper(int y) {
  37.     int pos = find_set(y + 1, gpar);
  38.     if (pos == n + 1) return -1;
  39.     return Y[pos - 1];
  40. }
  41.  
  42. int lower(int y) {
  43.     int pos = find_set(y - 1, lpar);
  44.     if (pos == 0) return -1;
  45.     return Y[pos - 1];
  46. }
  47.  
  48. void del(int y) {
  49.     gpar[y] = y + 1;
  50.     lpar[y] = y - 1;
  51. }
  52.  
  53. void upd(int u, int v) {
  54.     for (; u <= n; u += u & -u) bit[u] += v;
  55. }
  56.  
  57. int get(int u) {
  58.     int ans = 0;
  59.     for (; u; u -= u & -u) ans += bit[u];
  60.     return ans;
  61. }
  62.  
  63. void add(int &a, int b) {
  64.     a += b;
  65.     if (a >= MOD) a -= MOD;
  66. }
  67.  
  68. int main(){
  69.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  70.     cin >> n;
  71.     REP(i, n) {
  72.         cin >> x >> y;
  73.         p[i] = {x, y};
  74.         Y.push_back(y);
  75.     }
  76.     sort(p + 1, p + n + 1);
  77.     sort(Y.begin(), Y.end());
  78.     REP(i, n) b[i] = lower_bound(Y.begin(), Y.end(), p[i].se) - Y.begin() + 1;
  79.     REP(i, n - 1) {
  80.         make_set();
  81.         REP(j, i - 1) del(b[j]);
  82.         FOR(j, i + 1, n) upd(b[j], 1);
  83.         FOV(j, i + 1, n) {
  84.             upd(b[j], -1);
  85.             int mi = min(b[i], b[j]);
  86.             int mx = max(b[i], b[j]);
  87.             if (get(mx) - get(mi - 1) > 0) {
  88.                 del(b[j]);
  89.                 continue;
  90.             }
  91.             int y = lower(mi);
  92.             int v = upper(mx);
  93.             if (y == -1 || v == -1) {
  94.                 del(b[j]);
  95.                 continue;
  96.             }
  97.             int delta = 1LL * (p[j].fi - p[i].fi - 1) * (v - y - 1) % MOD;
  98.             add(res, delta);
  99.             del(b[j]);
  100.         }
  101.     }
  102.     cout << res;
  103.     return 0;
  104. }
  105.  
  106.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IEaLPF
language:
C++14 (clang 8.0)
created:
16 hours 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!