QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#138951 | #3010. Subsequences in Substrings | karuna# | AC ✓ | 27ms | 14016kb | C++17 | 766b | 2023-08-12 14:49:46 | 2023-08-12 14:49:49 |
Judging History
answer
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 101010;
int pos[26][MAXN], c[26];
string s, t;
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> s >> t;
for (int i = 0; i < 26; i++) c[i] = s.size();
for (int i = (int)s.size() - 1; i >= 0; i--) {
c[s[i] - 'a'] = i;
for (int j = 0; j < 26; j++) pos[j][i] = c[j];
}
long long ans = 0;
for (int l = 0; l < s.size(); l++) {
int r = l;
int p = 0;
while (p < t.size() && r < s.size() && pos[t[p] - 'a'][r] != s.size()) {
r = pos[t[p] - 'a'][r] + 1;
p++;
}
if (p == t.size())
ans += s.size() - r + 1;
}
cout << ans;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 13976kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
5000050000
result:
ok answer is '5000050000'
Test #2:
score: 0
Accepted
time: 23ms
memory: 13840kb
input:
qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
4990154851
result:
ok answer is '4990154851'
Test #3:
score: 0
Accepted
time: 2ms
memory: 13844kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok answer is '99999'
Test #4:
score: 0
Accepted
time: 6ms
memory: 13840kb
input:
zaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
99999
result:
ok answer is '99999'
Test #5:
score: 0
Accepted
time: 5ms
memory: 13800kb
input:
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
25000000
result:
ok answer is '25000000'
Test #6:
score: 0
Accepted
time: 2ms
memory: 13972kb
input:
abcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcd...
output:
4999600009
result:
ok answer is '4999600009'
Test #7:
score: 0
Accepted
time: 12ms
memory: 13084kb
input:
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaab...
output:
2141234561
result:
ok answer is '2141234561'
Test #8:
score: 0
Accepted
time: 23ms
memory: 14016kb
input:
wihvaaqgcpykasskatdribceiwzsmjjuuqjononjknibpawvqtqeumefxkhoafyndgpipsfjxjhbqbfyqsjudqbuimewxmleojthsptiasfdgjtebxiawijflvdxvzohzedotgapzauzimqcjsgrziissrndyglcfftnnlpaoyxkzejlobssdkcbxpipvyebemirndverdgdvvgkdcejuousanpxxkhdtwwmblqmwcyalthjmuynwmxaponazdazeazztkeoxdhhesxdqelnywvqdlcmstmfullktqtvmlsu...
output:
4742431461
result:
ok answer is '4742431461'
Test #9:
score: 0
Accepted
time: 27ms
memory: 13840kb
input:
amplpsqzijrsvjngzzeidkopdzrakreyesiklovfcymebhprmsbrghdljejpizhnzbtsnjfczwlqyytmzjejfxetvjgzzjtsqbpownodtmvakxtqwwklkwuukuqhnwjxakmqgwulsfxzyyhvzsngeclgqmmxonaizvajzgmehgzucqoydxjxuaoctjmarsubzhjkudquwlkefsyutcwhywbvyhbrpccsoswijledgxonogqiwewskgdaxuibtbhjblycupocgvxoyhoeulnzsbyvvwluswwxfrebjuylmeov...
output:
4744748626
result:
ok answer is '4744748626'
Test #10:
score: 0
Accepted
time: 24ms
memory: 14016kb
input:
byqhmrogmrkrkxlopxzyrphkqoflakhnkpjdvojgpwfxndlvuxhjjdsuwudjjpgldwbcuqgffvsgdcykrrqxilxuclgoecxabivddsgyesxorzdgnydiiuhfoestiuyckxovcmuporhstqntgkxfdqrqdhremdaqgmyiuhbcvtfaunwpgkhqapzpfnpqhxxllmptxoueguozeluzxksmzaqnhvjikgvwkjkztqrkpplizyoshavxpnfwbynwquhzushxwckftjvveazomjbyibhynxphhicasishegoxitjo...
output:
4741244687
result:
ok answer is '4741244687'
Test #11:
score: 0
Accepted
time: 5ms
memory: 13864kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
3887366754
result:
ok answer is '3887366754'
Test #12:
score: 0
Accepted
time: 5ms
memory: 13864kb
input:
yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
0
result:
ok answer is '0'
Test #13:
score: 0
Accepted
time: 2ms
memory: 11672kb
input:
aaacccabababacccccbbccaaaaabcacabaaccabccabcacbbccabbbacccabaaaacabbcbaccbabbccaccbcaabcacbaccabcaabcccaaabcabcabccbabcccabbaaccbaccacbcabacccbabacacbabaccaaababababaacbacbaacabbcbcbccccaaaacabcabbbcb caabc
output:
17714
result:
ok answer is '17714'
Test #14:
score: 0
Accepted
time: 3ms
memory: 11860kb
input:
acbdccaaacdbdbccccdddaddbdcbbdbbbadaacbbaddcdbcacaadcddcbdabdbdacadaadbbccaaacbdccabbbaabcbdcbabcdcadaacbdbbddbcccbdbcabacaadddbcaadbcacbdbccccacdddaaacccdddacbbabccbbcacbbbabdcbaddcbddadbbdcdcbcdcabdbdbdacdbabacdbdbcdcdbdcadbbcbbaacddccccdddbbcabcdddccbbdcbcdbdbdcddbdcbcbbbbdccccbbdabdcbbbdabcbbcbc...
output:
1923795
result:
ok answer is '1923795'
Test #15:
score: 0
Accepted
time: 1ms
memory: 11956kb
input:
dcdcaabcbbacccbaacacdeacaaadcdecaeeceecabeecadbdabbcabbadcaaedbcdeabddccdbbcaadabecdcabdebaeacdbccaebadaacdbdedccdcccbcbbeedbaeeabdecccabcbbaaacbcaeeadedeebbdeeebeacdcaddeabddaeedbbdaeeddeaedaeaaeacdceabceaeaceeecacdecdcadceceacdacccdeacdceededaeaadcdcdebbeaacaccccbbcbebddadaaecbabdaedcaabdacccbbdae...
output:
45098892
result:
ok answer is '45098892'
Test #16:
score: 0
Accepted
time: 8ms
memory: 12268kb
input:
haggcbhhacdahgcacdhcgehgcfcecffgecaaeggadfgbgdeedffafhecccgegbagcbahebhaaaaaahbgccffagbggdbcedgbhfaacefcdheabeefghdfdfabcbhhbaeefdbgaaahcfdhfeacgfbehbdhfdehaagfgfgehcdbadecbchgbadaadeaaabgafccaceadhdadhhhadfbddhddfceebbfgcgehdchhbgcfhedafgaebhgbfgdhcdbdbeebcahgfdfefhbcbhdddaadacbhgeahfhcddecfedaeebb...
output:
292904504
result:
ok answer is '292904504'
Test #17:
score: 0
Accepted
time: 2ms
memory: 11840kb
input:
aabb ab
output:
4
result:
ok answer is '4'
Test #18:
score: 0
Accepted
time: 2ms
memory: 11668kb
input:
aabb ba
output:
0
result:
ok answer is '0'
Test #19:
score: 0
Accepted
time: 1ms
memory: 11676kb
input:
abcdabcd ac
output:
14
result:
ok answer is '14'
Test #20:
score: 0
Accepted
time: 2ms
memory: 11668kb
input:
abcdefghijklmnopqrstuvwxyz z
output:
26
result:
ok answer is '26'
Test #21:
score: 0
Accepted
time: 0ms
memory: 11744kb
input:
abcdefghijklmnopqrstuvwxyz za
output:
0
result:
ok answer is '0'
Test #22:
score: 0
Accepted
time: 1ms
memory: 11632kb
input:
a a
output:
1
result:
ok answer is '1'
Test #23:
score: 0
Accepted
time: 0ms
memory: 11804kb
input:
abcdefg abcdefg
output:
1
result:
ok answer is '1'
Test #24:
score: 0
Accepted
time: 2ms
memory: 11672kb
input:
pp p
output:
3
result:
ok answer is '3'