fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define fi first
  6. #define se second
  7. #define TASK "D"
  8.  
  9. const int MOD = 998244353;
  10.  
  11. int n, dem, ans, s, s2, s3, x, y, z;
  12. int p[2505], q[2505], cnt[2505];
  13. pair<int, pair<int, int>> tong[2505];
  14. map<int, int> mp;
  15. pair<int, int> a[2505];
  16.  
  17. bool check(int a, int b, int c) {
  18.   return a < b + c && b < a + c && c < a + b;
  19. }
  20.  
  21. void add(int &x, int val) {
  22.   x += val;
  23.   if (x >= MOD) x %= MOD;
  24.   if (x < 0) x += MOD;
  25. }
  26.  
  27. void sub(int &x, int val) {
  28.   x -= val;
  29.   if (x >= MOD) x %= MOD;
  30.   if (x < 0) x += MOD;
  31. }
  32.  
  33. int mul(int x, int val) {
  34.   return ((x % MOD) * (val % MOD)) % MOD;
  35. }
  36.  
  37. int add_2(int x, int val) {
  38.   return ((x % MOD) + (val % MOD)) % MOD;
  39. }
  40.  
  41. int sub_2(int x, int val) {
  42.   return ((x % MOD) - (val % MOD) + MOD) % MOD;
  43. }
  44.  
  45. signed main() {
  46.   ios_base::sync_with_stdio(0);
  47.   cin.tie(0); cout.tie(0);
  48.   if (fopen(TASK".INP", "r")) {
  49.     freopen(TASK".INP", "r", stdin);
  50.     freopen(TASK".OUT", "w", stdout);
  51.   }
  52.   cin >> n;
  53.   for (int i = 1; i <= n; i++) {
  54.     cin >> a[i].fi >> a[i].se;
  55.     mp[a[i].se] = 1;
  56.   }
  57.  
  58.   /// Nén số
  59.   int m = 0;
  60.   for (auto &it : mp) it.se = ++m;
  61.   for (int i = 1; i <= n; i++) a[i].se = mp[a[i].se];
  62.  
  63.   /// Sort để 2 con trỏ
  64.   sort(a + 1, a + n + 1);
  65.   for (int i = 1; i <= n; i++) {
  66.     p[i] = a[i].fi % MOD;
  67.     q[i] = a[i].se;
  68.   }
  69.  
  70.   /// Xử lý
  71.   for (int i = 3; i <= n; i++) {
  72.     int sum = p[1],
  73.         sum2 = mul(p[1], p[1]),
  74.         sum3 = mul(sum2, p[1]);
  75.     int k = 1;
  76.     cnt[q[1]] = 1;
  77.     tong[q[1]].fi = sum;
  78.     tong[q[1]].se.fi = sum2;
  79.     tong[q[1]].se.se = sum3;
  80.     for (int j = 2; j < i; j++) {
  81.       if (check(p[i], p[j], p[k])) {
  82.         if (k > 1) {
  83.           k--;
  84.           while (check(p[i], p[j], p[k])) {
  85.             cnt[q[k]]++;
  86.             x = p[k], y = mul(p[k], p[k]), z = mul(y, p[k]);
  87.             add(sum, x);
  88.             add(sum2, y);
  89.             add(sum3, z);
  90.             add(tong[q[k]].fi, x);
  91.             add(tong[q[k]].se.fi, y);
  92.             add(tong[q[k]].se.se, z);
  93.             k--;
  94.           }
  95.           k++;
  96.         }
  97.       } else {
  98.         while (k < j && !check(p[i], p[j], p[k])) {
  99.           cnt[q[k]]--;
  100.           x = p[k], y = mul(p[k], p[k]), z = mul(y, p[k]);
  101.           sub(sum, x);
  102.           sub(sum2, y);
  103.           sub(sum3, z);
  104.           sub(tong[q[k]].fi, x);
  105.           sub(tong[q[k]].se.fi, y);
  106.           sub(tong[q[k]].se.se, z);
  107.           k++;
  108.         }
  109.       }
  110.       x = add_2(p[i], p[j]);
  111.       y = mul(x, x);
  112.       z = mul(x, y);
  113.       if (q[i] == q[j]) {
  114.         /// q[i] = q[j] = q[k]
  115.         add(ans, add_2(mul(cnt[q[i]], x), tong[q[i]].fi));
  116.         /// q[i] = q[j]; q[i] != q[k]
  117.         dem = j - k - cnt[q[i]];
  118.         if (dem) {
  119.           s = sub_2(sum, tong[q[i]].fi);
  120.           s2 = sub_2(sum2, tong[q[i]].se.fi);
  121.           add(ans, add_2(mul(dem, y) + mul(mul(2, x), s), s2));
  122.         }
  123.       } else {
  124.         /// q[i] != q[j]; q[i] = q[k]
  125.         add(ans, add_2(mul(cnt[q[i]], y) + mul(mul(2, x), tong[q[i]].fi), tong[q[i]].se.fi));
  126.         /// q[i] != q[j]; q[j] = q[k]
  127.         add(ans, add_2(mul(cnt[q[j]], y) + mul(mul(2, x), tong[q[j]].fi), tong[q[j]].se.fi));
  128.         /// q[i] != q[j]; q[i] != q[k]; q[j] != q[k]
  129.         dem = j - k - cnt[q[i]] - cnt[q[j]];
  130.         if (dem) {
  131.           s = sub_2(sub_2(sum, tong[q[i]].fi), tong[q[j]].fi);
  132.           s2 = sub_2(sub_2(sum2, tong[q[i]].se.fi), tong[q[j]].se.fi);
  133.           s3 = sub_2(sub_2(sum3, tong[q[i]].se.se), tong[q[j]].se.se);
  134.           add(ans, add_2(add_2(mul(dem, z), mul(mul(3, y), s)), add_2(mul(mul(3, x), s2), s3)));
  135.         }
  136.       }
  137.       cnt[q[j]]++;
  138.       x = p[j], y = mul(x, x), z = mul(x, y);
  139.       add(sum, x);
  140.       add(sum2, y);
  141.       add(sum3, z);
  142.       add(tong[q[j]].fi, x);
  143.       add(tong[q[j]].se.fi, y);
  144.       add(tong[q[j]].se.se, z);
  145.     }
  146.     for (int j = 1; j < i; j++) cnt[q[j]] = tong[q[j]].fi = tong[q[j]].se.fi = tong[q[j]].se.se = 0;
  147.   }
  148.   cout << ans;
  149.   return 0;
  150. }
  151.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UEMfY8
language:
C++14 (gcc 8.3)
created:
6 days 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!