SHARE
TWEET

Untitled

a guest Feb 16th, 2020 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //#pragma comment(linker, "/stack:200000000")
  2. //#pragma GCC optimize("Ofast")
  3. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. //#pragma GCC optimize("unroll-loops")
  5.  
  6. #include <iostream>
  7. #include <stdlib.h>
  8. #include <cmath>
  9. #include <algorithm>
  10. #include <vector>
  11. #include <queue>
  12. #include <deque>
  13. #include <set>
  14. #include <map>
  15. #include <unordered_map>
  16. #include <unordered_set>
  17. #include <random>
  18. #include <assert.h>
  19. #include <memory.h>
  20. #include <time.h>
  21. #include <bitset>
  22.  
  23. #define uint unsigned int
  24. #define ll long long
  25. #define ull unsigned long long
  26. #define ld long double
  27. #define rep(i, l, r) for (int i = (l); i < (r); i++)
  28. #define repb(i, r, l) for (int i = (r); i > (l); i--)
  29. #define sz(a) (int)a.size()
  30. #define fi first
  31. #define se second
  32. #define mp(a, b) make_pair(a, b)
  33. #define rank qwertyuio
  34. #define next dfghjk
  35. #define prev fhsgfhjf
  36. #define plus fsghsf
  37. #define minus ytryr
  38.  
  39. using namespace std;
  40.  
  41. inline bool setmin(int &x, int y) { return (y < x) ? x = y, 1 : 0; }
  42. inline bool setmax(int &x, int y) { return (y > x) ? x = y, 1 : 0; }
  43. inline bool setmin(ll &x, ll y) { return (y < x) ? x = y, 1 : 0; }
  44. inline bool setmax(ll &x, ll y) { return (y > x) ? x = y, 1 : 0; }
  45.  
  46. const int N = 200000 + 239;
  47. const int inf = (int)1e9 + 1;
  48. const ll big = (ll)1e18 + 1;
  49. const int P = 239;
  50. const int P1 = 31;
  51. const int P2 = 57;
  52. const int MOD = (int)1e9 + 7;
  53. const int MOD1 = (int)1e9 + 9;
  54. const int MOD2 = 998244353;
  55. const ld eps = 1e-12;
  56. const double pi = atan2(0, -1);
  57. const int ABC = 26;
  58.  
  59. ll a[N];
  60.  
  61. void add(int l, int r, int k, int t) {
  62.     if (l > r) {
  63.         return;
  64.     }
  65.     int k1 = k + (r - l) * t;
  66.     a[l] += k;
  67.     a[l + 1] += t - k;
  68.     a[r + 1] += -(k1 + t);
  69.     a[r + 2] += k1;
  70. }
  71.  
  72. void eval() {
  73.     rep(j, 0, 2) {
  74.         rep(i, 1, N) {
  75.             a[i] += a[i - 1];
  76.         }
  77.     }
  78. }
  79.  
  80. int main()
  81. {
  82.     //freopen("a.in", "r", stdin);
  83.     //freopen("a.out", "w", stdout);
  84.     ios_base::sync_with_stdio(0);
  85.     cin.tie(0);
  86.     cout.precision(20);
  87.     cout << fixed;
  88.     //ll TL = 10.95 * CLOCKS_PER_SEC;
  89.     //clock_t time = clock();
  90.     int n;
  91.     cin >> n;
  92.     int b[n];
  93.     rep(i, 0, n) {
  94.         cin >> b[i];
  95.     }
  96.     map<int, int> last;
  97.     rep(i, 0, n) {
  98.         int lst = -1;
  99.         if (last.count(b[i])) {
  100.             lst = last[b[i]];
  101.         }
  102.         last[b[i]] = i;
  103.         int cur = 1;
  104.         int m1 = 1, m2 = min(i - lst, n - i), m3 = max(i - lst, n - i), m4 = n - lst;
  105.         add(m1, m2 - 1, cur, 1);
  106.         cur += 1 * (m2 - m1);
  107.         add(m2, m3 - 1, cur, 0);
  108.         cur += 0 * (m3 - m2);
  109.         add(m3, m4, cur, -1);
  110.     }
  111.     eval();
  112.     rep(i, 1, n + 1) {
  113.         cout << a[i] << " ";
  114.     }
  115.     cout << "\n";
  116.     return 0;
  117. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top