#include<bits/stdc++.h>
using namespace std;
int n, lst[27][100002];
string s;
int L, R, col;
void chk(int st, int dr, int cnt)
{
if(L == 0)
{
L = st;
R = dr;
col = cnt;
}
else
{
long long a = cnt;
long long b = dr - st + 1;
long long c = col;
long long d = R - L + 1;
if(a * d < b * c)
{
L = st;
R = dr;
col = cnt;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
cin >> s;
s = ' ' + s;
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j <= 25; ++j)
lst[j][i] = lst[j][i-1];
lst[s[i] - 'a'][i] = i;
vector<int> v;
for(int j = 0; j <= 25; ++j)
if(lst[j][i] != 0)
v.push_back(lst[j][i]);
v.push_back(0);
sort(v.begin(), v.end());
for(int x = v.size() - 1; x > 0; --x)
chk(v[x - 1] + 1, i, v.size() - x);
}
cout << L << " " << R << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
504 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
504 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
632 KB |
Output is correct |
2 |
Correct |
7 ms |
632 KB |
Output is correct |
3 |
Correct |
7 ms |
632 KB |
Output is correct |
4 |
Correct |
7 ms |
632 KB |
Output is correct |
5 |
Correct |
7 ms |
632 KB |
Output is correct |
6 |
Correct |
7 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
10868 KB |
Output is correct |
2 |
Correct |
26 ms |
10784 KB |
Output is correct |
3 |
Correct |
27 ms |
10868 KB |
Output is correct |
4 |
Correct |
26 ms |
10780 KB |
Output is correct |
5 |
Correct |
25 ms |
10780 KB |
Output is correct |
6 |
Correct |
26 ms |
10868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
10780 KB |
Output is correct |
2 |
Correct |
35 ms |
10868 KB |
Output is correct |
3 |
Correct |
35 ms |
10868 KB |
Output is correct |
4 |
Correct |
34 ms |
10868 KB |
Output is correct |
5 |
Correct |
35 ms |
10868 KB |
Output is correct |
6 |
Correct |
35 ms |
10780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
107 ms |
10868 KB |
Output is correct |
2 |
Correct |
106 ms |
10844 KB |
Output is correct |
3 |
Correct |
105 ms |
10868 KB |
Output is correct |
4 |
Correct |
105 ms |
10868 KB |
Output is correct |
5 |
Correct |
106 ms |
10868 KB |
Output is correct |
6 |
Correct |
114 ms |
10868 KB |
Output is correct |