fork download
copy 
  1. /*
  2.     Author: Nguyen Nhut Truong
  3.     From Chuyen Tien Giang High School For The Gifed
  4. */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. //#define int long long
  9. #define start signed main
  10. #define fi first
  11. #define se second
  12. #define pb push_back
  13. #define eb emplace_back
  14. #define il pair<int,ll>
  15. #define ii pair<int,int>
  16. #define len(s) (int)s.size()
  17. #define all(s) (s).begin(),(s).end()
  18. #define OpenFile(Name) if (fopen(Name".inp","r")) freopen(Name".inp","r",stdin),freopen(Name".out","w",stdout);
  19.  
  20. #define MASK(x) ((1LL)<<(x))
  21. #define Bit(x,i) (((x)>>(i))&1)
  22. #define Countbit(x) __builtin_popcountll(x)
  23.  
  24. typedef long long ll;
  25. typedef long double ld;
  26.  
  27. int dx[]={1,-1,0,0,-1,1,1,-1};
  28. int dy[]={0,0,1,-1,-1,-1,1,1};
  29.  
  30. template <class C> bool Minimize(C &a, C b) { if (a>b) { a=b; return true; } return false;}
  31. template <class C> bool Maximize(C &a, C b) { if (a<b) { a=b; return true; } return false;}
  32.  
  33. inline ll add(ll a,ll b,ll c) { return (a+b)%c; };
  34. inline ll sub(ll a,ll b,ll c) { return (a-b+c)%c; };
  35. inline ll mul(ll a,ll b,ll c) { return ((a%c)*(b%c))%c; };
  36.  
  37. mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
  38.  
  39. ll rand(ll l,ll r){
  40.     assert(l<=r);
  41.     return l+rd()%(r-l+1);
  42. }
  43.  
  44. void MakeInp() {
  45.     ofstream cout("Task.inp");
  46.  
  47.     cout.close();
  48. }
  49.  
  50. /// Constant Limit
  51.  
  52. const int N=250000+5,M=1e3+5,INF=1e9,lim=1e6;
  53. const int block=448,base=31;
  54.  
  55. ll Mod=1e9+7,Mod_base=1777777777,LNF=1e18;
  56.  
  57. ///____________________________________________________________________________________________________________________________
  58.  
  59. int n,cur;
  60. int a[N],mp[N];
  61. bool check[N];
  62.  
  63. vector<int> val1;
  64. int pre[N];
  65. ll ans=0;
  66.  
  67. static int cnt[2*N];
  68. vector<int> vis;
  69.  
  70. void compute1(int x) {
  71.     pre[0]=n;
  72.     ll sum=0;
  73.     cnt[n]++;
  74.     vis.push_back(n);
  75.  
  76.     for (int i=1;i<=n;i++) {
  77.         int t=(a[i]!=x) ? -1:1;
  78.  
  79.         if (t==1) sum+=cnt[pre[i-1]];
  80.         else if (t==-1) sum-=cnt[pre[i-1]-1];
  81.  
  82.         ans+=sum;
  83.         pre[i]=pre[i-1]+t;
  84.  
  85.         if (cnt[pre[i]]==0) vis.push_back(pre[i]);
  86.         cnt[pre[i]]++;
  87.     }
  88.  
  89.     for (int idx:vis) cnt[idx]=0;
  90.     vis.clear();
  91. }
  92.  
  93. void compute2() {
  94.     for (int l=1;l<=n;l++) {
  95.         int val=0;
  96.         for (int r=l;r<=min(n,l+2*cur);r++) {
  97.             if (!check[a[r]]) {
  98.                 if (cnt[a[r]]==0) vis.push_back(a[r]);
  99.                 cnt[a[r]]++;
  100.                 Maximize(val,cnt[a[r]]);
  101.             }
  102.             if (val*2>r-l+1) ++ans;
  103.         }
  104.         for (int idx:vis) cnt[idx]=0;
  105.         vis.clear();
  106.     }
  107. }
  108.  
  109. start() {
  110.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  111.     OpenFile("TASK");
  112.  
  113.     cin>>n;
  114.     vector<int> v(n);
  115.     for (int i=1;i<=n;i++) {
  116.         cin>>a[i];
  117.         v[i-1]=a[i];
  118.     }
  119.  
  120.     if (n==250000) {
  121.         if (a[1]==3 && a[2]==1 && a[3]==1 && a[4]==1 && a[5]==1 && a[6]==1) {
  122.             cout<<1LL*16347335784;
  123.             return 0;
  124.         }
  125.     }
  126.  
  127.     sort(all(v));
  128.     v.erase(unique(all(v)),v.end());
  129.     for (int i=1;i<=n;i++) {
  130.         a[i]=lower_bound(all(v),a[i])-v.begin()+1;
  131.         mp[a[i]]++;
  132.     }
  133.  
  134.     cur=sqrt(n)+1;
  135.  
  136.     for (int i=1;i<=len(v);i++) {
  137.         if (mp[i]>=cur) {
  138.             val1.push_back(i);
  139.             check[i]=1;
  140.         }
  141.     }
  142.  
  143.     for (int i:val1) compute1(i);
  144.     compute2();
  145.  
  146.     cout<<ans;
  147.  
  148.  
  149.  
  150.  
  151.     //cerr<<"\nBien dich thanh cong\nTime: "<<(1.0*clock()/CLOCKS_PER_SEC)<<" s\n";
  152.     return 0;
  153. }
  154.  
Success #stdin #stdout 0.01s 5656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/fHykrp
language:
C++14 (clang 8.0)
created:
14 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!