fork download
copy 
  1.  
  2.  
  3.  
  4. /*************************************************************************************************************
  5.                                         ⣿⣿⣿⣿⣿⣿⣿⣿⡿⠿⠛⠛⠛⠋⠉⠈⠉⠉⠉⠉⠛⠻⢿⣿⣿⣿⣿⣿⣿⣿
  6.                                         ⣿⣿⣿⣿⣿⡿⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠛⢿⣿⣿⣿⣿
  7.                                         ⣿⣿⣿⣿⡏⣀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⣤⣄⡀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣿⣿
  8.                                         ⣿⣿⣿⢏⣴⣿⣷⠀⠀⠀⠀⠀⢾⣿⣿⣿⣿⣿⣿⡆⠀⠀⠀⠀⠀⠀⠀⠈⣿⣿
  9.                                         ⣿⣿⣟⣾⣿⡟⠁⠀⠀⠀⠀⠀⢀⣾⣿⣿⣿⣿⣿⣷⢢⠀⠀⠀⠀⠀⠀⠀⢸⣿
  10.                                         ⣿⣿⣿⣿⣟⠀⡴⠄⠀⠀⠀⠀⠀⠀⠙⠻⣿⣿⣿⣿⣷⣄⠀⠀⠀⠀⠀⠀⠀⣿
  11.                                         ⣿⣿⣿⠟⠻⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠶⢴⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⣿
  12.                                         ⣿⣁⡀⠀⠀⢰⢠⣦⠀⠀⠀⠀⠀⠀⠀⠀⢀⣼⣿⣿⣿⣿⣿⡄⠀⣴⣶⣿⡄⣿
  13.                                         ⣿⡋⠀⠀⠀⠎⢸⣿⡆⠀⠀⠀⠀⠀⠀⣴⣿⣿⣿⣿⣿⣿⣿⠗⢘⣿⣟⠛⠿⣼
  14.                                         ⣿⣿⠋⢀⡌⢰⣿⡿⢿⡀⠀⠀⠀⠀⠀⠙⠿⣿⣿⣿⣿⣿⡇⠀⢸⣿⣿⣧⢀⣼
  15.                                         ⣿⣿⣷⢻⠄⠘⠛⠋⠛⠃⠀⠀⠀⠀⠀⢿⣧⠈⠉⠙⠛⠋⠀⠀⠀⣿⣿⣿⣿⣿
  16.                                         ⣿⣿⣧⠀⠈⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠟⠀⠀⠀⠀⢀⢃⠀⠀⢸⣿⣿⣿⣿
  17.                                         ⣿⣿⡿⠀⠴⢗⣠⣤⣴⡶⠶⠖⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡸⠀⣿⣿⣿⣿
  18.                                         ⣿⣿⣿⡀⢠⣾⣿⠏⠀⠠⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠛⠉⠀⣿⣿⣿⣿
  19.                                         ⣿⣿⣿⣧⠈⢹⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣰⣿⣿⣿⣿
  20.                                         ⣿⣿⣿⣿⡄⠈⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣴⣾⣿⣿⣿⣿⣿
  21.                                         ⣿⣿⣿⣿⣧⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿
  22.                                         ⣿⣿⣿⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  23.                                         ⣿⣿⣿⣿⣿⣦⣄⣀⣀⣀⣀⠀⠀⠀⠀⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  24.                                         ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡄⠀⠀⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
  25.                                         ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠙⣿⣿⡟⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿
  26.                                         ⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠁⠀⠀⠹⣿⠃⠀⣿⣿⣿⣿⣿⣿⣿⣿⣿
  27.                                         ⣿⣿⣿⣿⣿⣿⣿⣿⡿⠛⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⢐⣿⣿⣿⣿⣿⣿⣿⣿⣿
  28.                                         ⣿⣿⣿⣿⠿⠛⠉⠉⠁⠀⢻⣿⡇⠀⠀⠀⠀⠀⠀⢀⠈⣿⣿⡿⠉⠛⠛⠛⠉⠉
  29.                                         ⣿⡿⠋⠁⠀⠀⢀⣀⣠⡴⣸⣿⣇⡄⠀⠀⠀⠀⢀⡿⠄⠙⠛⠀⣀⣠⣤⣤⠄
  30. *************************************************************************************************************/       
  31.  
  32. #include "bits/stdc++.h"
  33.  
  34. using namespace std;
  35.  
  36. #define ll long long int
  37. #define pll pair<ll,ll> 
  38. #include <ext/pb_ds/assoc_container.hpp>
  39. #include <ext/pb_ds/tree_policy.hpp>
  40. using namespace __gnu_pbds;
  41. using namespace chrono;
  42. #define ordered_set tree<ll, null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
  43. typedef tree<pll, null_type,less<pll>, rb_tree_tag,tree_order_statistics_node_update>ordered_multiset;
  44. #define ugp gp_hash_table<ll,ll,custom_hash>
  45. #define umap unordered_map<ll,ll,custom_hash>
  46. #define pb push_back
  47. #define len(v) ((ll)(v.size()))
  48. #define all(v) v.begin(),v.end()
  49. #define rall(v) v.rbegin(),v.rend()
  50. #define ff first
  51. #define ss second
  52. #define inp(a) for(auto &x:a) cin>>x;
  53. #define vll vector<ll>
  54. #define vvll vector<vector<ll>>
  55. #define vs vector<string>
  56. #define vpll vector<pair<ll,ll>> 
  57. #define pn cout<<"NO\n"
  58. #define py cout<<"YES\n"
  59. #define mid(s,e) s+(e-s)/2
  60. #define endl '\n'
  61. const ll MAX_SIZE = 200005;
  62. const ll ninf = (-1)*(1ll<<60);
  63. const ll inf = 1ll<<60;
  64. const ll mod = 1000000007;
  65.  
  66. //typedef long long ll;
  67. typedef unsigned long long ull;
  68. typedef long double lld;
  69.  
  70. #ifndef ONLINE_JUDGE
  71. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  72. #else
  73. #define debug(x)
  74. #endif
  75.  
  76. void _print(ll t) {cerr << t;}
  77. void _print(int t) {cerr << t;}
  78. void _print(string t) {cerr << t;}
  79. void _print(char t) {cerr << t;}
  80. void _print(lld t) {cerr << t;}
  81. void _print(double t) {cerr << t;}
  82. void _print(ull t) {cerr << t;}
  83.  
  84. template <class T, class V> void _print(pair <T, V> p);
  85. template <class T> void _print(vector <T> v);
  86. template <class T> void _print(set <T> v);
  87. template <class T, class V> void _print(map <T, V> v);
  88. template <class T> void _print(multiset <T> v);
  89. template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
  90. template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  91. template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  92. template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  93. template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  94. struct custom_hash {
  95.     static uint64_t splitmix64(uint64_t x) {
  96.         // http://x...content-available-to-author-only...i.it/splitmix64.c
  97.         x += 0x9e3779b97f4a7c15;
  98.         x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
  99.         x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
  100.         return x ^ (x >> 31);
  101.     }
  102.  
  103.     size_t operator()(uint64_t x) const {
  104.         static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
  105.         return splitmix64(x + FIXED_RANDOM);
  106.     }
  107. };
  108.  
  109. ll setbits(ll x){
  110.     return __builtin_popcountll(x);
  111. }
  112. ll tz(ll x){
  113.     return __builtin_ctz(x);
  114. }
  115. ll fastpow(ll a ,ll b){
  116.     ll res=1;
  117.     while(b){
  118.        if(b&1) res=(res*a)%mod;
  119.        a=(a*a)%mod;
  120.        b/=2;
  121.     }
  122.     return res;
  123. }
  124. //bitset<1000001> isprime; 
  125. //void seive(){
  126. //    isprime.set();
  127. //    isprime[1]=0;
  128. //    for(ll i=4;i<MAX_SIZE;i+=2) isprime[i]=false;
  129. //
  130. //    for(ll i=3;i<MAX_SIZE;i+=2){
  131. //        if(isprime[i]){
  132. //            ll j=i;
  133. //            while(j*i<MAX_SIZE){
  134. //                isprime[j*i]=false;
  135. //                j+=2;
  136. //            }
  137. //        }
  138. //    }
  139. //
  140. //} 
  141.  
  142.  
  143. const ll p=31;
  144. const ll k=fastpow(p,mod-2);
  145.  
  146.  
  147.  
  148. void Excuse_Me(ll TC)
  149. {
  150.  
  151. 	ll n;
  152. 	cin>>n;
  153.  
  154.     string s;
  155.     cin>>s;
  156.  
  157.     vll great(n+1),equal(n+1),less(n+1,0);
  158.  
  159.  
  160.  
  161.     vll pre(n+1),pt(n+1),inv(n+1);
  162.  
  163.     pt[0]=1;
  164.     inv[0]=1;
  165.     pre[0]=0;
  166.  
  167.     for(ll i=1;i<=n;i++){
  168.     	pre[i]=(pre[i-1]+(s[i-1]-'a'+1)*pt[i-1])%mod;
  169.     	pt[i]=(pt[i-1]*p)%mod;
  170.     	inv[i]=(inv[i-1]*k)%mod;
  171.     }
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.     for(ll i=2;i<=n;i++){
  179.  
  180. 	    if(s[i-1]>s[0]){
  181. 	    	great[1]++;  //start contributing from length 1 to atmost n-i+1
  182. 	    	great[n-i+2]--;
  183. 	    }
  184. 	    else if(s[i-1]<s[0]){
  185. 	    	less[1]++; //start contributing from length 1 to atmost n-i+1
  186. 	    	less[n-i+2]--;
  187. 	    }
  188. 	    else{
  189.  
  190. 	    	equal[1]++;
  191.  
  192. 	    	ll low=i,high=n;
  193.  
  194. 	    	ll ind=i;
  195.  
  196. 	    	while(low<=high){  //fiding the index upto which it is equal to prefix
  197. 	    		ll m=mid(low,high);
  198. 	    		ll hash1=pre[m-i+1];
  199. 	    		ll hash2=(((pre[m]-pre[i-1]+mod)%mod)*inv[i])%mod;
  200. 	    		if(hash1==hash2){
  201. 	    			ind=m;low=m+1;
  202. 	    		}
  203. 	    		else high=m-1;
  204. 	    	}
  205. // 	    	
  206. 	    	equal[ind-i+2]--;  /// now from length 1 to ind-i+1 it will contribute in equal
  207.  
  208. 	    	if(ind+1<=n){
  209. 	    		if(s[ind]>s[0]){
  210. 	    			great[ind+1-i+1]++;  //after that it will contribute in gretaer upto the max length we can get upto n index
  211. 	    			great[n-ind+1]--;
  212. 	    		}
  213. 	    		else{
  214. 	    			less[ind+1-i+1]++;
  215. 	    			less[n-ind+1]--;    			
  216. 	    		}
  217. 	    	}
  218.  
  219.  
  220. 	    }
  221.  
  222.     }
  223.  
  224.  
  225.     for(ll i=1;i<n;i++){
  226.     	great[i]+=great[i-1];
  227.     	less[i]+=less[i-1];
  228.     	equal[i]+=equal[i-1];
  229.     	cout<<great[i]<<" "<<equal[i]<<" "<<less[i]<<endl;
  230.     }
  231.  
  232.  
  233.  
  234.  
  235.  
  236. }
  237.  
  238. int main()
  239. {
  240.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  241. //     
  242.     // #ifndef ONLINE_JUDGE
  243.     // freopen("Error.txt", "w", stderr);
  244.     // #endif
  245.  
  246.      #ifdef ONLINEJUDGE
  247.        freopen("input.txt","r",stdin); //can need to change file . this one for taking input
  248.        freopen("output.txt","w",stdout); // this one for output
  249.      #endif
  250.      auto start1 = high_resolution_clock::now(); 
  251.     //seive();
  252.     ll Tc=1;
  253.     // cin>>Tc;
  254.  
  255.     for(ll tc=1;tc<=Tc;tc++)
  256.     {
  257.         Excuse_Me(tc);
  258.     }
  259.      auto stop1 = high_resolution_clock::now();
  260.     auto duration = duration_cast<microseconds>(stop1 - start1);
  261.     #ifndef ONLINE_JUDGE
  262.     cerr << "Time: " << duration . count() / 1000 << endl;
  263.     #endif    
  264.  
  265. return 0;
  266. }
  267. /*
  268. 1. Initialize all variables! Arrays etc.
  269. 2. Min of Max and Max of Min, such type of problems usually require Binary Search
  270. 3. Use to_string and stoi,atoi for conversions to suitable types.
  271. 4. For setting precision of n digits after decimal, use cout<<fixed;cout<<setprecision(n); before output, or at start of code if all outputs have same precision(include ios and iomanip header files.
  272. 5. Instead os using ceil(a/b), use (a+b-1)/b or (a-1)/b+1.
  273. 6. For char to int, subtract '0', for int to char add'0'
  274. */
  275.  
Success #stdin #stdout 0.01s 5396KB
comments (?)
stdin
copy 
5
abcba
stdout
copy 
3 1 0
3 0 0
2 0 0
1 0 0
https://ideone.com/yytrbC
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!