fork download
  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
stdin
5
abcba
stdout
3 1 0
3 0 0
2 0 0
1 0 0